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

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

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

تعریف رسمی

یک زنجیره مارکوف، جاذب است اگر^[۱]^[۲]

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

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

فرم متعارف

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

P=\left({\begin{array}{cc}Q&R\\\mathbf {0} &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$ تا $\infty$ ) ماتریس اساسی $N$ را نشان خواهد داد. اثبات رابطه زیر ساده است:

N=\sum _{k=0}^{\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_{\operatorname {dg} }-I_{t})-N_{\operatorname {sq} },

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

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

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

\mathbf {t} =N\mathbf {1} ,

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

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

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

(2N-I_{t})\mathbf {t} -\mathbf {t} _{\operatorname {sq} },

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

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

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

H=(N-I_{t})N_{\operatorname {dg} }^{-1}.

احتمالات جذب

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

B=NR.

نمونه‌ها

تولید توالی

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

P={\begin{bmatrix}1/2&1/2&0&0\\0&1/2&1/2&0\\1/2&0&0&1/2\\0&0&0&1\end{bmatrix}}.

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

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

{\begin{aligned}N&=(I-Q)^{-1}=\left({\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}-{\begin{bmatrix}1/2&1/2&0\\0&1/2&1/2\\1/2&0&0\end{bmatrix}}\right)^{-1}\\[4pt]&={\begin{bmatrix}1/2&-1/2&0\\0&1/2&-1/2\\-1/2&0&1\end{bmatrix}}^{-1}={\begin{bmatrix}4&4&2\\2&4&2\\2&2&2\end{bmatrix}}.\end{aligned}}

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

\mathbf {t} =N\mathbf {1} ={\begin{bmatrix}4&4&2\\2&4&2\\2&2&2\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}={\begin{bmatrix}10\\8\\6\end{bmatrix}}.

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

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

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

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

منابع

↑ ^۱٫۰ ^۱٫۱ Grinstead, Charles M.; Snell, J. Laurie (July 1997). "Ch. 11: Markov Chains" (PDF). Introduction to Probability. American Mathematical Society. ISBN 978-0-8218-0749-1. Archived from the original (PDF) on 3 March 2016. Retrieved 19 January 2017. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «Grin» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
↑ ^۲٫۰ ^۲٫۱ Kemeny, John G.; Snell, J. Laurie (July 1976) [1960]. "Ch. 3: Absorbing Markov Chains". In Gehring, F. W.; Halmos, P. R. (eds.). Finite Markov Chains (Second ed.). New York Berlin Heidelberg Tokyo: Springer-Verlag. pp. 224. ISBN 978-0-387-90192-3. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «Kem» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
↑ Based on the definition found in S. C. Althoen; L. King; K. Schilling (March 1993). "How Long Is a Game of Snakes and Ladders?". The Mathematical Gazette. The Mathematical Gazette, Vol. 77, No. 478. 78 (478): 71–76. doi:10.2307/3619261. JSTOR 3619261.

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

[Grin-1] ۱٫۰ ^۱٫۱ Grinstead, Charles M.; Snell, J. Laurie (July 1997). "Ch. 11: Markov Chains" (PDF). Introduction to Probability. American Mathematical Society. ISBN 978-0-8218-0749-1. Archived from the original (PDF) on 3 March 2016. Retrieved 19 January 2017. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «Grin» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).

[Kem-2] ۲٫۰ ^۲٫۱ Kemeny, John G.; Snell, J. Laurie (July 1976) [1960]. "Ch. 3: Absorbing Markov Chains". In Gehring, F. W.; Halmos, P. R. (eds.). Finite Markov Chains (Second ed.). New York Berlin Heidelberg Tokyo: Springer-Verlag. pp. 224. ISBN 978-0-387-90192-3. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «Kem» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).

[3] Based on the definition found in S. C. Althoen; L. King; K. Schilling (March 1993). "How Long Is a Game of Snakes and Ladders?". The Mathematical Gazette. The Mathematical Gazette, Vol. 77, No. 478. 78 (478): 71–76. doi:10.2307/3619261. JSTOR 3619261.

[۱]

[۲]

[۳]