زنجیره مارکوف جذب‌کننده

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

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

مثل زنجیره مارکف عمومی، می‌توان زنجیره مارکوف جاذب پیوسته زمان با فضای حالت نامحدود داشت. در این مقاله بر روی زمان گسسته فضای حالت گسسته متمرکز می‌شویم.

تعریف رسمی

یک زنجیره مارکوف، جاذب است اگر

1. حداقل یک حالت جاذب وجود داشته باشد و
2. رفتن از هر حالتی به حداقل یکی از حالتهای جاذب در تعداد محدودی از مراحل ممکن باشد.

در یک زنجیره مارکوف جاذب، حالتی که جاذب نباشد گذرا (حالت گذرا) نامیده می‌شود.

فرم متعارف

فرض کنید که یک زنجیره مارکوف جاذب با ماتریس انتقال $P$ دارای $t$ حالت گذرا و $r$ حالت جاذب باشد. سپس

$P=\left(\begin{array}{cc}Q& R\\ \mathrm{𝟎}& I_r\end{array}\right),$

که در آن $Q$ ماتریسی $t\times t$، ماتریس $R$ یک ماتریس غیرصفر $t\times r$ و $0$ یک ماتریس صفر $r\times t$ و $I_r$ ماتریس همانی $r\times r$ باشد؛ بنابراین $Q$ احتمال انتقال از یک حالت گذرا به حالت گذرای دیگر در حالی که $R$ احتمال انتقال از حالت گذرا به حالت جاذب را توصیف می‌کند.

ماتریس اساسی

یک ویژگی اصلی در مورد یک زنجیره مارکوف جاذب تعداد مورد انتظار بازدیدهای حالت گذاری $j$ با شروع از حالت گذرای $i$ (قبل از اینکه جذب شود) است. احتمال انتقال از $i$ به $j$ در دقیقاً $k$ مرحله عنصر $(i,j)$ از ماتریس $Q^k$ است. جمع این آرایه برای تمام $k$ (از $0$ تا $\mathrm{\infty }$) ماتریس اساسی $N$ را نشان خواهد داد. اثبات رابطه زیر ساده است:

$N=\sum _{k=0}^{\mathrm{\infty }}{Q}^k=(I_t-Q{)}^{-1},$

که در آن $I_t$ ماتریس همانی $t\times t$ است. درایه $(i,j)$ ماتریس $N$، تعداد مورد انتظار دفعاتی است که زنجیره در حالت $j$ خواهد بود با این شرط که از حالت $i$ شروع شده باشد. با داشتن ماتریس $N$، خواص دیگر زنجیره مارکوف را می‌توان راحت به دست آورد.

واریانس تعداد بازدید

واریانس تعداد بازدیدهای حالت گذرای $j$ با شروع از حالت گذرای $i$ (قبل از اینکه جذب شود) درایه $(i,j)$ ماتریس

$N_2=N(2N_{\mathrm{dg}}-I_t)-N_{\mathrm{sq}},$

است، که در آن $N_{dg}$ ماتریس قطری است با قطر مشابه ماتریس $N$ و $N_{sq}$ حاصل ضرب هادامار $N$ با خودش است (یعنی هر درایه $N$ مربع خواهد شد).

امید تعداد مراحل

امید تعداد مراحل قبل از جذب با شروع از حالت گذرای $i$ برابر است با $t$ امین عنصر بردار

$𝐭=N\mathrm{𝟏},$

که $1$ بردار ستونی با طول $t$ است که تمام عناصرش ۱ می‌باشد.

واریانس تعداد مراحل

واریانس تعداد مراحل قبل از جذب با شروع از حالت گذرای $i$ برابر است با $t$ امین عنصر بردار

$(2N-I_t)𝐭-{𝐭}_{\mathrm{sq}},$

که در آن $t_{sq}$ حاصلضرب هادامار $t$ با خودش است (یعنی هر درایه $t$ مربع خواه شد).

احتمالات گذرا

احتمال بازدید حالت گذرای $j$ با شروع از حالت گذرای $i$ درایه $(i,j)$ ماتریس زیر است:

$H=(N-I_t)N_{\mathrm{dg}}^{-1}.$

احتمالات جذب

ویژگی دیگر احتمال جذب شدن در حالت جاذب $j$ است با فرض شروع از حالت گذرای $i$، که درایه $(i,j)$ ماتریس زیر است:

$B=NR.$

نمونه‌ها

تولید توالی

فرایند پرتاب مکرر یک سکه عادی تا تولید توالی از (H,T,H)ها را در نظر بگیرید. این فرایند را با یک زنجیره مارکوف جاذب مدل می‌کنیم. ماتریس انتقال این زنجیره به این صورت است: الگو:چپ‌چین

$P=\left[\begin{array}{cccc}1/2& 1/2& 0& 0\\ 0& 1/2& 1/2& 0\\ 1/2& 0& 0& 1/2\\ 0& 0& 0& 1\end{array}\right].$

الگو:پایان چپ‌چینحالت اول نشان دهنده توالی تهی است، حالت دوم توالی "H" است، حالت سوم توالی "HT" و حالت چهارم توالی "HTH" می‌باشد. اگر چه در واقعیت، پس از تولید توالی "HTH" پرتاب سکه متوقف می‌شود، زنجیره مارکوف جاذب این است که فرایند به حالت جاذب نمایانگر توالی "HTH" انتقال یافته و نمی‌تواند از این حالت خارج شود.

برای این زنجیره مارکوف جاذب، ماتریس اساسی به این صورت است:

$\begin{array}{cc}N& =(I-Q{)}^{-1}={(\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]-\left[\begin{array}{ccc}1/2& 1/2& 0\\ 0& 1/2& 1/2\\ 1/2& 0& 0\end{array}\right])}^{-1}\\ & ={\left[\begin{array}{ccc}1/2& -1/2& 0\\ 0& 1/2& -1/2\\ -1/2& 0& 1\end{array}\right]}^{-1}=\left[\begin{array}{ccc}4& 4& 2\\ 2& 4& 2\\ 2& 2& 2\end{array}\right].\end{array}$

امید تعداد مراحل با شروع از هر حالت گذرا:

$𝐭=N\mathrm{𝟏}=\left[\begin{array}{ccc}4& 4& 2\\ 2& 4& 2\\ 2& 2& 2\end{array}\right]\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]=\left[\begin{array}{c}10\\ 8\\ 6\end{array}\right].$

بنابراین امید تعداد پرتاب‌های سکه قبل از مشاهده توالی (H,T,H) برابر $10$ است، درایه حالت رشته تهی را نشان می‌دهد.

بازی‌های شانس

احتمال تجمعی پایان یک بازی مار و پله با N نوبت.

بازی‌های کاملاً شانسی را می‌توان با زنجیره مارکوف جاذب مدل کرد. به عنوان مثال بازی تخته‌ای مار و پله هند باستان. نمودار سمت راست جرم احتمال جرم در تنها جذب دولت است که نشان دهنده نهایی مربع به عنوان ماتریس گذار مطرح شده‌است به بزرگتر و بزرگتر قدرت. برای تعیین امید تعداد نوبت‌ها برای اتمام بازی، بردار $t$ را محاسبه کنید و $t_{start}$ را بررسی کنید، که به صورت تقریبی $39.2$ است.

جستارهای وابسته

• توزیع فاز-نوع گسسته
• مجموعه جاذب(سیستم‌های پویای تصادفی)

پیوند به بیرون

• Wolfram Demonstration Project: Absorbing Markov Chain
• Monopoly as a Markov chain