فرایند مارکف

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از فرآیند مارکف)
پرش به: ناوبری، جستجو

به فرایندی تصادفی که احتمالات آینده آن از طریق مقادیر اخیر آن محاسبه می‌شود، فرایند مارکف می‌گویند. این فرایند از روی نام ریاضیدان روسی به نام آندری مارکف نامگذاری شده است.

فرایند مارکف: markov process[ویرایش]

دنباله ای از متغیرهای تصادفی را در نظر گرفته و فرض کنید مجموعه مقادیر ممکن که این متغیرها انتخاب میکنند برابر با \ {0,1,...} باشد.اگر \ x_{n} را به عنوان حالتی از یک سیستم در لحظه \ n در نظر گرفته و چنین تفسیر کنیم که سیستم در لحظه \ n در حالت \ i است هرگاه \ x_{n}=i باشد انگاه دنباله متغیرهای تصادفی اصطلاحاً تشکیل یک زنجیر مارکف میدهد.اگر هروقت سیستم در حالت \ i است با احتمال ثابتی که ان را \ p_{ij} می نامیم به حالت \ j تغییر حالت دهد. برای همه مقادیر \ i_0,i_1,... داریم : Pr\{ X_{n+1} = j \mid \ X_{n} =i ,X_{n-1} =i_{n-1} ,...,X_0 =i_0  \}

اگر این احتمال ها را درون یک ماتریس قرار دهیم ماتریسی به شکل زیر بدست میآد که به آن ماتریس احتمال انتقال transition probability matrix و یا ماتریس مارکف گویند. P=[p_{ij} ]اگر به سطر i+۱ ام نگاه کنیدتوزیع احتمالX_{n+۱} را به شرط آنکه X_n =i باشد به شما نشان می دهد از (علیرضا فرداد)

مثال[ویرایش]

۱ - مجموع متغیرهای تصادفی و مستقل همتوزیع (قدم زدن تصادفی کلی ): فر ض کنید i\ge 0, X_i مستقل و همتوزیع باشد Pr\{X_i =j\} =a_j ,  j=0,1,... , \pm 1 باشند اگر فرض کنید S_n= \sum_{i=1}^n X_i    ,S_0=0 آنگاه \{S_n ,n\ge 0\} یک فرایند مارکف است که برای آن P_{ij} = a_{j-i} قدم تصادفی کلی گوییم این نوع قدم زدن در مسایل بسیاری کار برد دارند برای مثال در مدل بندی برد های قمارباز و یا در قیمت های متوالی شرکت معینی که در بازار سهام فهرست شده اند. هم چنین در تحلیل سیستم های صف بندی ورشکستگی کاربرد دارند. ۲-قدم زدن تصادفی ساده: قدم زدن {S_n ,n\ge 0}که در آن

S_n= \sum_{i=1}^n X_i 

را قدم زدن تصادفی ساده گوییم اگر Pیی موجود باشد به قسمی که

                           Pr(X_i =1)=p ,  Pr(X_i =-1)=1-p  ,0 <p <1       

بنابراین در فرایند قدم زدن تصادفی همیشه۱ پله با احتمالP به بالا میرود و با احتمال 1-P به پایین می آید. قضیه: اگر X_n زنجیر مارکف گسسته زمان باشد بعلاوه اگر P ماتریس احتمال انتقال ۱ مرحله ای باشد نشان می دهیم که P^n ماتریس احتمال انتقال n مرحله ای خواهد بود. اثبات: اثبات به روش استقراست ابتدا برای n=۲ ثابت می کنیم


\begin{alignat}{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{alignat}

با توجه به خاصیت مارکف هر مرحله فقط به یکی قبل از خود بستگی دارد 
=\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+۱ ثابت می کنیم.


\begin{alignat}{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^nP=P^{n+1}

\end{alignat}

برابری چپمن – کولموگروف[ویرایش]

اگر احتمال تغییر وضعیت n مرحله ای را برابر P_{ij}^{(n)} بگیریم داریم: P^{(m)} P^{(n)} =P^{(n+m)}

اثبات: با توجه به قضیه بالا داریم: P^{(m)} P^{(n)} = P^m P^n=P^{m+n}= P^{(m+n)}

دسته بندی وضعیت های زنجیر مارکف[ویرایش]

۱- وضعیت های در دسترس (Accessible State)[ویرایش]

وضعیت j   در دسترس وضعیت i نامیم و با
i \longrightarrow j
نشان می دهیم اگر و تنها اگر
\exists n\in {0,1,...} s.t P_{ij}^n \ge 0

اگر \forall n\in{0,1,2,...} P_{ij}^n=0

j در دسترس i است.

۲- وضعیت های مرتبط(Communicate State)[ویرایش]

وضعیت iوj را مرتبط می نامیم اگر وتنها اگر j در دسترس iو iدر دسترس j باشد مرتبط بودن را با نماد\leftrightarrow مشخص می کنیم

قضیه[ویرایش]

مرتیط بودن یک رابطه هم ارزی است.

اثبات: i\in S بدیهی است i\leftrightarrow i چون P_{ii}^0=1>0 مرتبط بودن دارای خاصیت بازتابی است. 

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\leftrightarrow j ,j\leftrightarrow k

\exists n \in \{0,1,..\}P_{ij}^n>0  \exists n_1\in\{0,1,...\} P_{jk}^{n_1}>0

\exists  m\in \{0,1,...\} P_{ji}^m>0 \exists n_2 \in \{0,1,..\} P_{kj}^{n_2}>0
میدانیم
P_{ik}^{n+n_1}= \sum_{l=1}^\infty P_{il}^nP_{lk}^{n_1} \ge P_{ij}^n P_{jk}^{n_1}>0
P_{ki}^{m+n_2}= \sum_{l=1}^\infty  P_{kl}^mP_{li}^{n_2} \ge P_{kj}^m P_{ji}^{n_2}>0

i\leftrightarrow k بنا بر این مرتبط بودن یک کلاس هم ارزی است.

منابع[ویرایش]

  • Weisstein, Eric W. "Markov Process." From MathWorld--A Wolfram Web Resource.

A first course in stochastic processes , samuel karlin academic press1969

فرایند های تصادفی / شلدون .م.راس/ترجمه عین الله پاشا / مرکز نشر دانشگاهی تهران/1385