به زبان ساده، فرایند مارکوف یعنی محل بعدی یک متغیر تصادفی بدون حافظه را فقط با دانستن محل فعلی آن می‌توان براورد.
ریاضیدان روسی به نام آندری مارکوف اندیشید که قدم بعدی یک مجنون در یک محوطه باز، فقط به قدم فعلی او وابسته است. سپس فرایند مارکوف را تعریف و کمی سازی کرد.
دنباله‌ای از متغیرهای تصادفی را در نظر گرفته و فرض کنید مجموعه مقادیر ممکن که این متغیرها انتخاب می‌کنند برابر با
0
,
1
,
.
.
.
{\displaystyle \ {0,1,...}}
x
n
{\displaystyle \ x_{n}}
n
{\displaystyle \ n}
n
{\displaystyle \ n}
i
{\displaystyle \ i}
x
n
=
i
{\displaystyle \ x_{n}=i}
i
{\displaystyle \ i}
p
i
j
{\displaystyle \ p_{ij}}
j
{\displaystyle \ j}
i
0
,
i
1
,
.
.
.
{\displaystyle \ i_{0},i_{1},...}
P
r
{
X
n
+
1
=
j
∣
X
n
=
i
,
X
n
−
1
=
i
n
−
1
,
.
.
.
,
X
0
=
i
0
}
{\displaystyle Pr\{X_{n+1}=j\mid \ X_{n}=i,X_{n-1}=i_{n-1},...,X_{0}=i_{0}\}}
اگر این احتمال‌ها را درون یک ماتریس قرار دهیم ماتریسی به شکل زیر بدست میآد که به آن ماتریس احتمال انتقال transition probability matrix یا ماتریس مارکف گویند.
P
=
[
p
i
j
]
{\displaystyle P=[p_{ij}]}
۱ - مجموع متغیرهای تصادفی و مستقل همتوزیع (قدم زدن تصادفی کلی):
فر ض کنید
i
≥
0
,
X
i
{\displaystyle i\geq 0,X_{i}}
P
r
{
X
i
=
j
}
=
a
j
,
j
=
0
,
1
,
.
.
.
,
±
1
{\displaystyle Pr\{X_{i}=j\}=a_{j},j=0,1,...,\pm 1}
S
n
=
∑
i
=
1
n
X
i
,
S
0
=
0
{\displaystyle S_{n}=\sum _{i=1}^{n}X_{i},S_{0}=0}
{
S
n
,
n
≥
0
}
{\displaystyle \{S_{n},n\geq 0\}}
P
i
j
=
a
j
−
i
{\displaystyle P_{ij}=a_{j-i}}
قدم زدن در مسایل بسیاری کار برد دارند برای مثال در مدل بندی بردهای قمارباز یا در قیمت‌های متوالی شرکت معینی که در بازار سهام فهرست شده‌اند. هم چنین در تحلیل سیستم‌های صف بندی ورشکستگی کاربرد دارند.
۲-قدم زدن تصادفی ساده: قدم زدن
S
n
,
n
≥
0
{\displaystyle {S_{n},n\geq 0}}
S
n
=
∑
i
=
1
n
X
i
{\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}}
را قدم زدن تصادفی ساده گوییم اگر Pیی موجود باشد به قسمی که
P
r
(
X
i
=
1
)
=
p
,
P
r
(
X
i
=
−
1
)
=
1
−
p
,
0
<
p
<
1
{\displaystyle Pr(X_{i}=1)=p,Pr(X_{i}=-1)=1-p,0<p<1}
بنابراین در فرایند قدم زدن تصادفی همیشه۱ پله با احتمال
P
{\displaystyle P}
1
−
P
{\displaystyle 1-P}
X
n
{\displaystyle X_{n}}
گسسته زمان باشد به‌علاوه اگر P ماتریس احتمال انتقال ۱ مرحله‌ای باشد نشان می‌دهیم که
P
n
{\displaystyle P^{n}}
P
i
j
(
2
)
=
P
r
{
X
k
+
2
∣
X
k
=
i
}
=
P
r
{
X
k
+
2
,
X
k
=
i
}
P
r
{
X
k
=
i
}
=
∑
l
=
1
∞
P
r
{
X
k
+
2
=
j
,
X
k
+
1
=
l
,
X
k
=
i
}
P
r
{
X
k
=
i
}
=
∑
l
=
1
∞
P
r
{
X
k
+
2
=
j
,
X
k
+
1
=
l
,
X
k
=
i
}
P
r
{
X
k
+
1
=
l
,
X
k
=
i
}
×
P
r
{
X
k
+
1
=
l
,
X
k
=
i
}
P
r
{
X
k
=
i
}
{\displaystyle {\begin{alignedat}{3}P_{ij}^{(2)}&=Pr\{X_{k+2}\mid \ X_{k}=i\}={\frac {Pr\{X_{k+2},X_{k}=i\}}{Pr\{X_{k}=i\}}}\\&={\frac {\sum _{l=1}^{\infty }Pr\{X_{k+2}=j,X_{k+1}=l,X_{k}=i\}}{Pr\{X_{k}=i\}}}\\&=\sum _{l=1}^{\infty }{\frac {Pr\{X_{k+2}=j,X_{k+1}=l,X_{k}=i\}}{Pr\{X_{k+1}=l,X_{k}=i\}}}\times {\frac {Pr\{X_{k+1}=l,X_{k}=i\}}{Pr\{X_{k}=i\}}}\\\end{alignedat}}}
با توجه به خاصیت مارکف هر مرحله فقط به یکی قبل از خود بستگی دارد
=
∑
l
=
1
∞
P
r
{
X
k
+
2
=
j
∣
X
k
+
1
=
l
}
×
P
r
{
X
k
+
1
=
l
∣
X
k
=
i
}
=
∑
l
=
1
∞
P
i
l
P
l
j
=
P
i
j
(
2
)
{\displaystyle =\sum _{l=1}^{\infty }{Pr\{X_{k+2}=j\mid \ X_{k+1}=l\}}\times {Pr\{X_{k+1}=l\mid \ X_{k}=i\}}=\sum _{l=1}^{\infty }P_{il}P_{lj}=P_{ij}^{(2)}}
حال اگر فرض کنیم که این رابطه برای n=k درست باشد آن را برای k+۱ ثابت می‌کنیم.
P
n
+
1
=
(
P
i
j
(
n
+
1
)
)
P
i
j
(
n
+
1
)
=
P
r
{
X
n
+
k
+
1
∣
X
k
=
i
}
=
P
r
{
X
n
+
k
+
1
,
X
k
=
i
}
P
r
{
X
k
=
i
}
=
∑
l
=
1
∞
P
r
{
X
n
+
k
+
1
=
j
,
X
k
+
n
=
l
,
X
k
=
i
}
P
r
{
X
k
=
i
}
=
∑
l
=
1
∞
P
r
{
X
n
+
k
+
1
=
j
,
X
k
+
n
=
l
,
X
k
=
i
}
P
r
{
X
k
+
n
=
l
,
X
k
=
i
}
×
P
r
{
X
k
+
n
=
l
,
X
k
=
i
}
P
r
{
X
k
=
i
}
=
∑
l
=
1
∞
P
r
{
X
k
+
n
+
1
=
j
∣
X
k
+
n
=
l
}
×
P
r
{
X
k
+
n
=
l
∣
X
k
=
i
}
=
∑
l
=
1
∞
P
i
l
(
n
)
P
l
j
=
P
(
n
)
P
=
P
n
P
=
P
n
+
1
{\displaystyle {\begin{alignedat}{7}&P^{n+1}=(P_{ij}^{(n+1)})\\&P_{ij}^{(n+1)}=Pr\{X_{n+k+1}\mid \ X_{k}=i\}\\&={\frac {Pr\{X_{n+k+1},X_{k}=i\}}{Pr\{X_{k}=i\}}}\\&={\frac {\sum _{l=1}^{\infty }Pr\{X_{n+k+1}=j,X_{k+n}=l,X_{k}=i\}}{Pr\{X_{k}=i\}}}\\&=\sum _{l=1}^{\infty }{\frac {Pr\{X_{n+k+1}=j,X_{k+n}=l,X_{k}=i\}}{Pr\{X_{k+n}=l,X_{k}=i\}}}\times {\frac {Pr\{X_{k+n}=l,X_{k}=i\}}{Pr\{X_{k}=i\}}}\\&=\sum _{l=1}^{\infty }{Pr\{X_{k+n+1}=j\mid \ X_{k+n}=l\}}\times {Pr\{X_{k+n}=l\mid \ X_{k}=i\}}\\&=\sum _{l=1}^{\infty }P_{il}^{(n)}P_{lj}=P^{(n)}P=P^{n}P=P^{n+1}\end{alignedat}}}
ویرایش
اگر احتمال تغییر وضعیت n مرحله‌ای را برابر
P
i
j
(
n
)
{\displaystyle P_{ij}^{(n)}}
P
(
m
)
P
(
n
)
=
P
(
n
+
m
)
{\displaystyle P^{(m)}P^{(n)}=P^{(n+m)}}
اثبات: با توجه به قضیه بالا داریم:
P
(
m
)
P
(
n
)
=
P
m
P
n
=
P
m
+
n
=
P
(
m
+
n
)
{\displaystyle P^{(m)}P^{(n)}=P^{m}P^{n}=P^{m+n}=P^{(m+n)}}
ویرایش
ویرایش
وضعیت j در دسترس وضعیت i نامیم و با
i
⟶
j
{\displaystyle i\longrightarrow j}
نشان می‌دهیم اگر و تنها اگر
∃
n
∈
0
,
1
,
.
.
.
s
.
t
P
i
j
n
≥
0
{\displaystyle \exists n\in {0,1,...}s.tP_{ij}^{n}\geq 0}
اگر
∀
n
∈
0
,
1
,
2
,
.
.
.
P
i
j
n
=
0
{\displaystyle \forall n\in {0,1,2,...}P_{ij}^{n}=0}
j در دسترس i است.
ویرایش
وضعیت iوj را مرتبط می‌نامیم اگر و تنها اگر j در دسترس iو iدر دسترس j باشد
مرتبط بودن را با نماد
↔
{\displaystyle \leftrightarrow }
مرتبط بودن یک رابطه هم‌ارزی است.
اثبات:
i
∈
S
{\displaystyle i\in S}
i
↔
i
{\displaystyle i\leftrightarrow i}
P
i
i
0
=
1
>
0
{\displaystyle P_{ii}^{0}=1>0}
i
↔
j
≡
∃
n
∈
{
0
,
1
,
.
.
.
}
P
i
j
n
>
0
∃
m
∈
{
0
,
1
,
.
.
.
}
P
i
j
m
>
0
≡
j
↔
i
{\displaystyle i\leftrightarrow j\equiv \exists n\in \{0,1,...\}P_{ij}^{n}>0\exists m\in \{0,1,...\}P_{ij}^{m}>0\equiv j\leftrightarrow i}
مرتبط بودن دارای خاصیت تقارنی است.
i
↔
j
,
j
↔
k
{\displaystyle i\leftrightarrow j,j\leftrightarrow k}
∃
n
∈
{
0
,
1
,
.
.
}
P
i
j
n
>
0
∃
n
1
∈
{
0
,
1
,
.
.
.
}
P
j
k
n
1
>
0
{\displaystyle \exists n\in \{0,1,..\}P_{ij}^{n}>0\exists n_{1}\in \{0,1,...\}P_{jk}^{n_{1}}>0}
∃
m
∈
{
0
,
1
,
.
.
.
}
P
j
i
m
>
0
∃
n
2
∈
{
0
,
1
,
.
.
}
P
k
j
n
2
>
0
{\displaystyle \exists m\in \{0,1,...\}P_{ji}^{m}>0\exists n_{2}\in \{0,1,..\}P_{kj}^{n_{2}}>0}
می‌دانیم
P
i
k
n
+
n
1
=
∑
l
=
1
∞
P
i
l
n
P
l
k
n
1
≥
P
i
j
n
P
j
k
n
1
>
0
{\displaystyle P_{ik}^{n+n_{1}}=\sum _{l=1}^{\infty }P_{il}^{n}P_{lk}^{n_{1}}\geq P_{ij}^{n}P_{jk}^{n_{1}}>0}
P
k
i
m
+
n
2
=
∑
l
=
1
∞
P
k
l
m
P
l
i
n
2
≥
P
k
j
m
P
j
i
n
2
>
0
{\displaystyle P_{ki}^{m+n_{2}}=\sum _{l=1}^{\infty }P_{kl}^{m}P_{li}^{n_{2}}\geq P_{kj}^{m}P_{ji}^{n_{2}}>0}
i
↔
k
{\displaystyle i\leftrightarrow k}
Weisstein, Eric W. "Markov Process ." From MathWorld—A Wolfram Web Resource. A first course in stochastic processes , samuel karlin academic press1969
فرایندهای تصادفی / شلدون. م. راس/ترجمه عین‌الله پاشا / مرکز نشر دانشگاهی تهران/۱۳۸۵
![{\displaystyle P=[p_{ij}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c91d28da3d5a45a11e17be957774d4e66224aaf8)
