زنجیره مارکوف

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

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

معرفی[ویرایش]

زنجیره مارکوف(Markov Approach modeling) یک فرایند تصادفی گسسته در زمان با خاصیت مارکف است. اگرچه برخی از نویسندگان در مورد فرایندهای پیوسته در زمان هم از اصطلاح زنجیره مارکف استفاده می‌کنند. یک فرایند تصافی گسسته در زمان شامل سیستمی است که در هر مرحله در حالت خاص و مشخصی قرار دارد و به صورت تصادفی در هر مرحله تغییر حالت می‌دهد. مراحل اغلب به عنوان لحظه‌های زمانی در نظر گرفته می‌شوند ولی می‌توان آن‌ها را فاصله فیزیکی یا هر متغیر گسسته دیگری در نظر گرفت.خاصیت مارکف بیان می‌کند که توزیع احتمال شرطی برای سیستم در مرحله بعد فقط به حالت فعلی سیستم بستگی دارد و به حالت‌های قبل بستگی ندارد. چون سیستم به صورت تصادفی تغییر می‌کند به طور کلی پیش بینی حالت زنجیره مارکف در نقطه‌ای خاص در آینده غیر ممکن است. با این حال ویژگی‌های آماری سیستم در آینده قابل پیش بینی است. در بسیاری از کاربردها چیزی که دارای اهمیت است همین ویژگی‌های آماری است.

تغییرات حالات سیستم انتقال نام دارند و احتمال‌هایی که به این تغییر حالت‌ها نسبت داده می‌شوند احتمال انتقال نام دارند. مجموعه‌ای از حالت‌ها و احتمال انتقال‌ها به طور کامل یک زنجیره مارکف را مشخص می‌کنند. طبق قرار داد ما فرض می‌کنیم همیشه حالت بعدی وجود دارد و در نتیجه فرایند تا ابد ادامه پیدا می‌کند.

یکی از معروف ترین زنجیره‌های مارکف که موسوم به «پیاده روی می خواره» است یک پیاده روی تصادفی است که در آن در هر قدم موقعیت با احتمال برابر به اندازه ۱+ یا ۱- تغییر می‌کند. در هر مکان دو انتقال ممکن وجود دارد یکی به عدد صحیح بعدی(۱+) و یکی به عدد صحیح قبلی(۱-). احتمال هر انتقال فقط به حالت کنونی بستگی دارد. برای مثال احتمال انتقال از ۵ به ۶ برابر با احتمال انتقال از ۵ به ۴ است و هر دوی این احتمالات برابر با ۰٫۵ هستند. این احتمالات مستقل از حالت قبلی (که یا ۴ بوده و یا ۶) هستند.

مثالی دیگر عادات غذایی که فقط انگور، پنیر و کاهو می‌خورد و عادات غذایی او از قوانین زیر پیروی می‌کند:

  • او فقط یک بار در روز می‌خورد.
  • اگر امروز پنیر بخورد فردا انگور یا کاهو را با احتمال برابر خواهد خورد.
  • اگر امروز انگور بخورد فردا با احتمال ۰٫۱ انگور، با احتمال ۰٫۴ پنیر و با احتمال ۰٫۵ کاهو خواهد خورد.
  • اگر امروز کاهو بخورد فردا با احتمال ۰٫۴ انگور و با احتمال ۰٫۶ پنیر خواهد خورد.

عادات غذایی این موجود را می‌توان با یک زنجیره مارکف مدل سازی کرد به دلیل این که چیزی که فردا می‌خورد(حالت بعدی) تنها به چیزی که امروز خورده است(حالت فعلی) بستگی دارد. یکی از ویژگی‌های آماری که می‌توان در مورد این زنجیره محاسبه کرد امید ریاضی درصد روزهایی است که انگور خورده است(در یک دوره طولانی).


تعریف رسمی[ویرایش]

یک زنجیره مارکف دنباله‌ای از متغیرهای تصادفی X۱،X۲،X۳،... است که دارای خاصیت مارکف هستند یعنی:

\Pr(X_{n+1}=x|X_1=x_1, X_2=x_2, \ldots, X_n=x_n) = \Pr(X_{n+1}=x|X_n=x_n).\,

مقادیر ممکن برای Xi مجموعه قابل شمارشی را می‌سازند که فضای حالت نام دارد.

تعریف دیگری به شرح ذیل عنوان شده است: هرگاه فرایند تعمیرات برای سیستمهای تعمیر پذیر لحظه ای و یا به عبارتی با زمان کوتاه و قابل اغماض در مقایسه با زمان عملکرد سیستم را نتوان مفروض داشت،روشهایی مانند زنجیره ی پیوسته مارکوف برای تحلیل سیستم به کار گرفته میشود. روش مارکوف برای مدلسازی رفتار اتفاقی به صورت پیوسته و نا پیوسته نسبت به زمان و یا در فضای حالت تقسیم بندی میگردد. این تغییرات پیوسته و یا نا پیوسته اتفاقی را اصطلاحاً فرایندهای اتفاقی می نامند. در حقیقت به کارگیری روش مارکوف نیازمند این امر است که سیستم نماینگر فقدان حافظه باشد. یعنی حالت و وضعیت آینده ی سیستم مستقل از وضعیتهای گذشته آن بوده و تنها به آخرین جزء آن وابسته باشد.

زنجیره‌های مارکف ایستا[ویرایش]

زنجیره‌های مارکف ایستا زنجیره‌هایی هستند که در آن‌ها:

\Pr(X_{n+1}=x|X_n=y) = \Pr(X_n=x|X_{n-1}=y)\,

که رابطه بالا برای هر n صحیح است. در واقع احتمال انتقال مستقل از n است.

زنجیره مارکف مرتبه m[ویرایش]

زنجیره مارکف مرتبه m(که در آن m متناهی است) فرایندی است که در آن:

'
\begin{align}
{} &\Pr(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots , X_1=x_1) \\
=  &\Pr(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots, X_{n-m}=x_{n-m})
\text{ for }n> m
\end{align}


به عبارت دیگر حالت بعدی به m حالت قبلی وابسته‌است.

زنجیره مارکف افزاینده[ویرایش]

یک زنجیره مارکف افزاینده مرتبه m با رابطه زیر توصیف می شود:

\Pr(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots, X_{n-m}=x_{n-m}) = \sum_{r=1}^{m} f(x_n,x_{n-r},r) .

زنجیره مارکف[ویرایش]

احتمال تغییر حالت از حالت iام به حالت jام در n حرکت برابر است با

p_{ij}^{(n)} = \Pr(X_n=j\mid X_0=i) \,

این احتمال در یک حرکت برابر است با

p_{ij} = \Pr(X_1=j\mid X_0=i). \,

برای یک زنجیره مارکوف یکنواخت در زمان

p_{ij}^{(n)} = \Pr(X_{k+n}=j \mid X_{k}=i) \,           و              p_{ij} = \Pr(X_{k+1}=j \mid X_k=i) \,. 

در حرکت های n تایی احتمالات بدست آمده برابری چپمن-کولموگروف را ارضا می کنند. پس برای هر k که ۰ <n> k داریم

p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}

در این رابطه S فضای حالت زنجیره مارکوف است. توزیع حاشیه ای (Pr( Xn = x مربوط به حرکت nام است. توزیع اولیه برابر است با (Pr( X۰ = x. تعمیم یافته این توزیع برای حرکت های بعدی به شکل

 \Pr(X_{n}=j) = \sum_{r \in S} p_{rj} \Pr(X_{n-1}=r) = \sum_{r \in S} p_{rj}^{(n)} \Pr(X_0=r).

نمایش داده می شود که در آن n زیروند است و نه توان.

تقلیل پذیری[ویرایش]

حالت jام را قابل دسترسی از حالت iام می نامند (i → j) اگر در سیستمی که از حالت iام شروع شود با احتمال غیر ۰ در نهایت به حالت jام برسد. در واقع اگر عدد صحیح n ≥ ۰ وجود داشته باشد که

 \Pr(X_{n}=j | X_0=i) = p_{ij}^{(n)}> 0.\,

تساوی n با ۰ به معنای در دسترس بودن همه حالات از حالت iام است. حالت iام را مرتبط با حالت jام می نامند (i ↔ j) اگر هر دو رابطه i → j و j → i برقرار باشند. جموعه حالات C را کلاس مرتبظ می نامند اگر هر یک از اعضای آن با هر عضو دیگر این مجموعه مرتبط باشد و هیچ یک از اعضای C با حالتی که عضو آن نیست مرتبط نباشد. می توان نشان داد که ارتباط همان هم ارزی است و کلاس های مرتبط در واقع کلاس های هم ارزی هستند. یک کلاس هم ارزی را بسته می نامند اگر احتمال خروج از این کلاس ۰ باشد. به عبارت دیگر اگر حالت i در 'C باشد و حالت j در C نباشد، j قابل دسترسی از i نیست. حالت i را ضروری می نامند اگر به ازای همه jهایی که i → j، رابطه j → i نیز برقرار باشد. حالت i را غیر ضروری می نامند اگر ضروری نباشد. اگر فضای حالت یک زنجیره مارکوف از تنها یک کلاس مرتبط تشکیل شده باشد، به آن تقلیل ناپذیر می گویند. در این زنجیره ها از هر حالت می توان به هر حالتی رسید.

تناوب[ویرایش]

حالت i دارای دوره تناوب k است اگر هر مسیر بازگشت به حالت i به طول مضارب k باشد. به زبان دیگر دوره تناوب یک حالت برابر است با

 k = \operatorname{gcd}\{ n: \Pr(X_n = i | X_0 = i)> 0\}

که در آن gcd {{بزرگترین مقسوم علیه مشترک]] است. اگر یک حالت دوره تناوب k داشته باشد ممکن است نتوان به این حالت با k حرکت رسید. به طور مثال اگر بتوان به حالت i در {6, 8, 10, 12, ...} حرکت بازگشت، در این صورت دوره تناوب برابر 2 خواهد بود حتی اگر 2 در مقادیر ذکر شده نباشد. اگر k = 1 باشد، در این صورت به حالت مد نظر غیر متناوب می گویند و بازگشت به حالت i در حرکت های غیر منظم انجام خواهد گرفت. در غیر این صورت (k > 1)، حالت iدارای دوره تناوب k و متناوب می باشد.

بازگشت پذیری[ویرایش]

حالت i را گذرا می نامند که اگر سیستم از حالت i شروع به کار کند، احتمال این که دیگر به این حالت بازنگردد غیر صفر باشد. با در نظر گرفتن متعیر تصادفی Ti، زمان اولین بازگشت به حالت i، داریم

 T_i = \inf \{ n\ge1: X_n = i | X_0 = i\}.

عدد  f_{ii}^{(n)} = \Pr(T_i = n) احتمال بازگشت سیستم به حالت i برای اولین بار در حرکت nام است. در نتیجه حالت i گذرا است اگر

 \Pr(T_i <{\infty}) = \sum_{n=1}^{\infty} f_{ii}^{(n)} <1

حالت غیر گذرای i را لحظه ای یا مانا می نامند. اگر حالت i احظه ای باشد احتمال اولین بازگشت به این حالت در زمان متناهی برابر 1 است.

متوسط زمان بازگشت[ویرایش]

اگر زمان اولین بازگشت به حالت i با احتمال 1 متناهی باشد، نمی توان نتیجه گرفت که امید ریاضی این زمان متناهی است. امید ریاضی زمان بازگشت به حالت i همان متوسط زمان بازگشت است که از رابطه

 M_i = E[T_i]=\sum_{n=1}^{\infty} n\cdot f_{ii}^{(n)}.\,

محاسبه می شود.

متوسط تعداد بازگشتها[ویرایش]

می توان نشان داد که حالت i لحظه ای است اگر و تنها اگر متوسط تعداد بازگشت ها به این حالت نامتناهی باشد. یعنی

\sum_{n=0}^{\infty} p_{ii}^{(n)} = \infty.

حالت های مانا[ویرایش]

حالت i را جذب کننده یا مانا می نامند اگر با ورود به این حالت خروج از آن غیر ممکن باشد. در نتیجه حالت i مانا است اگر و تنها اگر

 p_{ii} = 1\text{ and }p_{ij} = 0\text{ for }i \not= j.

اگر هر حالت در یک سیستم به حالت مانایی برسد زنجیره مارکوف را زنجیره مارکوف مانا می نامند.

تجزیه و تحلیل حالت ثابت و محدود کردن توزیع ها[ویرایش]

اگر یک زنجیره مارکف را بتوان با یک ماتریس مستقل از زمان p_{ij} توصیف کرد آنگاه بردار \boldsymbol{\pi} یک" توزیع ثابت" نامیده می شود اگر \pi_j ها نامنفی و جمع آن ها برابر 1 شود و نیز در رابطه زیر صدق کنند:

\pi_j = \sum_{i \in S} \pi_i p_{ij}.

یک زنجیره غیر قابل تقلیل یک توزیع ثابت دارد اگر و فقط اگر همه حالت های آن مثبت باشند دز این صورت π یکتاست و مربوط به زمان بازگشت مورد انتظار است:

\pi_j = \frac{1}{M_j}.\,

اگر زنجیره غیر تقلیل پذیر و غیر متناوب باشد آن گاه برای هر i و j داریم:

\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{1}{M_j}.

لازم به ذکر است که هیچ شرطی روی نقطه شروع توزیع وجود ندارد یعنی زنجیره صرف نظر از نقطه شروع به توزیع ثابت میل می کند.این π "توزیع تعادل" زنجیره نامیده می شود.اگر زنجیره بیش از یک کلاس مرتبط بسته داشته باشد توزیع ثابت آن یکتا نخواهد بود.

در هر صورت اگر حالت j ام غیر متناوب باشد آن گاه:

\lim_{n \rarr \infty} p_{jj}^{(n)} = \frac{1}{M_j}

و برای هر حالت i دیگر اگر fij احتمال این باشد که زنجیره در حالت j قرار گیرد در صورتی که شروع زنجیره از حالت i باشد خواهیم داشت:

\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{f_{ij}}{M_j}.

اگر حالت i متناوب باشد با دوره تناوب k > 1 آنگاه حد

\lim_{n \rarr \infty} p_{ii}^{(n)}

وجود ندارد و نیز حد

\lim_{n \rarr \infty} p_{ii}^{(kn+r)}

برای هر r صحیح وجود ندارد.

کاربردها[ویرایش]

فیزیک[ویرایش]

سیستم های مارکفی در ترمودینامیک و مکانیک آماری بسیار ظاهر می شوند،جایی که احتمال برای نشان دادن ویژگی های ناشناخته سیستم به کار می رود،اگر بتوان فرض کرد که دینامیک مستقل از زمان است و احتیاجی به بررسی پیشینه تاریخی آن نیست.

علم اطلاعات[ویرایش]

زنجیره مارکف در نظریه اطلاعات کاربرد دارد.مقاله معروف کلود شانون در سال 1948 با "نظریه ریاضی ارتباطات" که پایه گذار نظریه اطلاعات شد با معرفی آنتروپی از طریق مدل سازی مارکف از زبان انگلیسی آغاز می شود.چنین مدل های ایده‌آلی بسیاری از قواعد آماری سیستم را به دست می دهند.حتی بدون داشتن ساختار کامل سیستم این گونه مدل سازی ها فشرده سازی موثر داده ها را ممکن می سازند.

زنجیره های مارکف پایه و اساس مدل پنهان مارکف است که این مدل یکی از ابزارهای مهم در زمینه های گوناگون مثل شبکه های تلفن (برای تصحیح خطا)،تشخیص گفتار و هم چنین بیوانفورماتیک است.

نظریه صف[ویرایش]

زنجیره های مارکف اساس رفتار تحلیلی صف ها(نظریه صف) می باشد و این امر وجود آن ها را برای بهینه سازی عملکرد شبکه های مخابراتی حیاتی می سازد.جایی که پیام ها برای منابع محدود(مانند پهنای باند) رقابت می کنند.

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

  • مشارکت‌کنندگان ویکی‌پدیا، «Markov chain»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۶ ژوئیهٔ ۲۰۱۲).

پیوند به بیرون[ویرایش]