10.4: Поглинаючі ланцюги Маркова

Цілі навчання

У цьому розділі ви навчитеся:

1. Визначте поглинаючі стани і поглинаючі ланцюги
2. Розв'язувати і інтерпретувати поглинаючі ланцюги Маркова.

У цьому розділі ми вивчимо тип ланцюга Маркова, в якому при досягненні певного стану вийти з цього стану неможливо. Такі стани називаються поглинаючими станами, а ланцюг Маркова, що має хоча б один такий стан, називається ланцюгом, що поглинає Маркова.

Припустимо, у вас наступна матриця переходу.

Стан S ₂ є поглинаючим станом, тому що ймовірність переходу зі стану S ₂ в стан S ₂ дорівнює 1. Це ще один спосіб сказати, що якщо ви перебуваєте в стані S ₂, ви залишитеся в стані S ₂.

По суті, це спосіб ідентифікації поглинаючого стану. Якщо ймовірність в рядку\(i\) і стовпці\(i\),\(p_{ii}\), дорівнює 1, то стан S _i є поглинаючим станом.

Приклад\(\PageIndex{1}\)

Розглянемо перехідні матриці A, B, C для ланцюгів Маркова, показаних нижче. Які з наступних ланцюгів Маркова мають поглинаючий стан?

\ [A=\ лівий [\ початок {масив} {lll}
.3 & .7 & 0\\
0 & 1\\ 0 & 0\
.2 & .3 & .5
\ кінець {масив}\ праворуч]\ quad B =\ лівий [\ begin {масив} {lll}

0 & 1\\ 0 & 0 &
1\ 1 & 0
\ кінець {масив}\ праворуч]\ quad C =\ лівий [\ почати {масив} {cccc}
.1 & .3 & .3 & .4 & .2\\
0 & .2 & .1 & .7\\
0 & 0 & 0\ 0 &
0 & 0 & 0 & 0 & 1
\ end {масив}\ праворуч]\ nonumber\]

Рішення

має S ₂ як поглинаючий стан.

Якщо ми знаходимося в стані S ₂, ми не можемо його залишити. З стану S ₂ ми не можемо перейти в стан S ₁ або S ₃; ймовірності 0.
Імовірність переходу зі стану S ₂ в стан S ₂ дорівнює 1.

не має будь-яких поглинаючих станів.

З стану S ₁ ми завжди переходимо в стан S ₂. З стану S ₂ ми завжди переходимо в стан S ₃. З стану S ₃ ми завжди переходимо в стан S ₁. У цій матриці ніколи не можна залишатися в одному стані під час переходу.

має два поглинаючих стану, S ₃ і S ₄.

З стану S ₃ ви можете залишатися тільки в стані S ₃, і ніколи не переходити в будь-які інші стани. Аналогічно з стану S ₄ ви можете залишитися тільки в стані S ₄, і ніколи не переходити в будь-які інші стани.

Підсумовуємо, як визначити поглинаючі стани.

Резюме

Стан S - поглинаючий стан в ланцюжку Маркова в матриці переходу, якщо

• Рядок для стану S має один 1, а всі інші записи 0

І

• Запис, який дорівнює 1, знаходиться на головній діагоналі (рядок = стовпець для цього запису), що вказує на те, що ми ніколи не можемо залишити цей стан після його введення.

Далі визначаємо поглинаючу ланцюг Маркова.

Поглинаюча ланцюг Маркова

Ланцюг Маркова - це поглинаюча ланцюг Маркова, якщо

• Він має принаймні одне поглинаючий стан.

І

• З будь-якого не поглинає стану в ланцюжку Маркова можна з часом перейти в якесь поглинаючий стан (в один або кілька переходів).

Приклад\(\PageIndex{2}\)

Розглянемо перехідні матриці C і D для ланцюгів Маркова, показаних нижче. Яка з наступних ланцюгів Маркова являє собою поглинаючу ланцюг Маркова?

\ [\ mathrm {C} =\ лівий [\ почати {масив} {llll}
.1 & .3 & .3 & .4 & .2\\
0 & .2 & .1 & .7\
0 & 0 & 0\
0 & 0 & 0 & 1
\ кінець {масив}\ праворуч]\ квадратний\ математичний {D} =\ лівий [\ почати {масив} {lllll}
1 & 0 & 0 & 0\ 0\ 0 & 1 &
0 & 0 & 0 & 0\\
.2 & .2 & .2 & .2 & .2 & .2\ .2\
0 & 0 & 0 & .3 & .7\
0 & 0 & 0 & .6 & .4
\ кінець {масив}\ праворуч]\ nonumber\]

Рішення

С - поглинаюча ланцюг Маркова, але D - не поглинаюча ланцюг Маркова.

Матриця С має два поглинаючих стану, S ₃ і S ₄, і можна потрапити в стан S ₃ і S ₄ з S ₁ і S ₂.

Матриця D - не поглинаюча ланцюг Маркова. Він має два поглинаючі стани, S ₁ і S ₂, але ніколи не можна дістатися до будь-якого з цих поглинаючих станів або з S ₄ або S ₅. Якщо ви перебуваєте в стані S ₄ або S _5, ви завжди залишаєтеся переходом між станами S ₄ або S _5m і ніколи не можете поглинути ні в один стан S ₁ або S ₂.

В іншій частині цього розділу ми розглянемо поглинання ланцюгів Маркова з двома класичними завданнями: проблемою ходьби випадкового п'яниці та проблемою розорення азартного гравця. І наостанок ми зробимо висновок з поглинаючої моделі Маркова, застосованої до реальної світової ситуації.

Випадкова прогулянка п'яниці

У цьому прикладі ми коротко розглянемо основні ідеї, що стосуються поглинання ланцюгів Маркова.

Приклад\(\PageIndex{3}\)

Чоловік ходить вздовж трьох кварталів головної частини Святого Його будинку знаходиться в одному кінці трьох блокових секцій. Брус знаходиться на іншому кінці секції трьох блоків. Кожен раз, коли він досягає кута, він випадковим чином або йде вперед на один блок, або обертається і повертається назад на один блок. Якщо він дійде додому або до бару, він залишається там. Чотири стани: Головна (H), Кут 1 (C ₁), Кут 2 (C ₂) і Бар (B).

Запишіть матрицю переходу і визначте поглинаючі стани. Знайдіть ймовірності опинитися в кожному поглинаючому стані залежно від початкового стану.

Рішення

Матриця переходу написана нижче.

Будинок і Бар є поглинаючими станами. Якщо чоловік приїжджає додому, він не йде. Якщо чоловік приїжджає в бар, він не йде. Так як можна дістатися додому або бруса з кожного з двох інших кутів на його прогулянці, це поглинає ланцюг Маркова.

Ми можемо підняти матрицю переходу T на велику потужність,\(n\). Після того, як ми знайдемо потужність T ⁿ, яка залишається стабільною, вона скаже нам ймовірність опинитися в кожному поглинаючому стані залежно від початкового стану.

T ⁹¹ = T ⁹⁰; матриця не змінюється, оскільки ми продовжуємо вивчати вищі сили. Ми бачимо, що в довгостроковій перспективі ланцюг Маркова повинна опинитися в поглинаючому стані. Зрештою, чоловік повинен в кінцевому підсумку опинитися або у своєму будинку, або в барі.

Другий ряд говорить нам, що якщо чоловік знаходиться на куті C ₁, то є 2/3 шанс, що він опиниться вдома і 1/3 шанс, що він опиниться в барі.

Третій ряд говорить нам, що якщо чоловік знаходиться на куті C ₂, то є 1/3 шанс, що він опиниться вдома і 2/3 шанс, що він опиниться в барі.

Після того, як він досягає дому чи бару, він ніколи не залишає цього поглинаючого стану.

Відзначимо, що хоча матриця T ⁿ для досить великих\(n\) стала стабільною і не змінюється, вона не представляє рівноважну матрицю. Ряди не всі однакові, як ми виявили в правильних ланцюгах Маркова, які досягли рівноваги.

Ми можемо написати меншу «матрицю рішення», зберігши лише рядки, які відносяться до непоглинаючих станів і зберігши лише стовпці, які відносяться до поглинаючих станів.

Тоді матриця розв'язку матиме рядки C ₁ і C ₂, а стовпці H і B. Матриця рішення дорівнює

Перший рядок матриці рішення показує, що якщо людина знаходиться в куті C ₁, то є 2/3 шанс, що він опиниться вдома і 1/3 шанс, що він опиниться в барі.

Другий ряд матриці рішення показує, що якщо людина знаходиться в кутку С ₂, то є 1/3 шанс, що він опиниться вдома і 2/3 шанс, що він опиниться в барі.

Матриця рішення не показує, що в кінцевому підсумку існує 0 ймовірність опинитися в C1 або C2, або що якщо ви починаєте в поглинаючому стані H або B, ви залишитеся там. Менша матриця рішень передбачає, що ми розуміємо ці результати і не включаємо цю інформацію.

Наступний приклад - ще один класичний приклад поглинає ланцюга Маркова. У наступному прикладі ми розглянемо більше математичних деталей, що лежать в основі концепції матриці розв'язку.

Проблема руйнування Гамбера

Приклад\(\PageIndex{4}\)

Азартний гравець має 3000 доларів, і вона вирішує грати в азартні ігри 1,000 доларів за столом Блекджек в казино в Лас-Вегасі. Вона сказала собі, що буде продовжувати грати, поки вона не зламається або не матиме $5,000. Її ймовірність перемоги в «Блек Джек» становить 0,40. Напишіть матрицю переходу, визначте поглинаючі стани, знайдіть матрицю рішення і визначте ймовірність того, що гемблер буде фінансово зруйнований на етапі, коли у неї буде $2000.

Рішення

Матриця переходу написана нижче. Очевидно, що стан 0 і стан 5K є поглинаючими станами. Це має сенс, тому що як тільки гравець досягає 0, вона фінансово зруйнована, і гра закінчена. Аналогічно, якщо гравець досягає $5,000, вона пообіцяла собі кинути і, знову ж таки, гра закінчена. Читач повинен відзначити, що р ₀₀ = 1, а р ₅₅ = 1.

Далі зауважте, що оскільки гравець робить ставку тільки $1,000 за один раз, вона може підняти або знизити свої гроші тільки на $1,000 за один раз. Іншими словами, якщо у неї зараз 2000 доларів, після наступної ставки вона може мати 3000 доларів з ймовірністю 0,40 і 1000 доларів з ймовірністю 0,60.

Щоб визначити довгострокову тенденцію, ми піднімаємо матрицю до вищих сил, поки не поглинаються всі непоглинаючі стани. Це так звана матриця рішення.

Матриця розв'язку часто записується в наступному вигляді, де непоглинаючі стани записуються у вигляді рядків збоку, а поглинаючі стани у вигляді стовпців зверху.

У таблиці перераховані ймовірності поглинання в стані 0 або стані 5K, починаючи з будь-якого з чотирьох непоглинаючих станів. Наприклад, якщо в будь-якій інстанції гравець має 3000 доларів, то її ймовірність фінансового розорення становить 135/211 і її ймовірність досягнення 5K дорівнює 76/211.

Приклад\(\PageIndex{5}\)

Вирішіть проблему розорення азартного гравця,\(\PageIndex{4}\) не піднімаючи матрицю до вищих сил, і визначити кількість ставок, які робить азартний гравець, перш ніж гра закінчиться.

Рішення

При вирішенні поглинаючих станів часто зручно переставляти матрицю так, щоб рядки та стовпці, відповідні поглинаючим станам, були перераховані першими. Це називається Канонічна форма. Матриця переходу Прикладу 1 в канонічному вигляді наведена нижче.

Канонічна форма ділить матрицю переходу на чотири підматриці, як зазначено нижче.

Матриця\(F = (I_n- B)^{-1}\) називається фундаментальною матрицею для поглинаючого ланцюга Маркова, де In - ідентична матриця того ж розміру, що і Б.\(i\),\(j\) -й запис цієї матриці говорить нам про середню кількість разів процес знаходиться в непоглинаючому стані\(j\) до поглинання, якщо він розпочато в неабсорбуючому стані\(i\).

Матриця\(F = (I_n- B)^{-1}\) для нашої проблеми наведена нижче.

Для обчислення матриці F можна скористатися калькулятором, або комп'ютером.

Фундаментальна матриця F допомагає нам визначити середню кількість ігор, зіграних до поглинання.

Згідно з матрицею, запис 1.78 в рядку 3, позиція стовпця 2 говорить про те, що гравець буде грати в гру 1,78 рази, перш ніж вона перейде від $3K до $2K. Запис 2.25 в рядку 3, стовпець 3 говорить, що якщо гравець тепер має $3K, вона матиме $3K в середньому 2,25 рази, перш ніж гра закінчиться.

Ми зараз розглянемо питання про те, скільки ставок їй доведеться зробити, перш ніж вона буде поглинена, якщо азартний гравець починається з $3K?

Якщо додати кількість ігор, які гравець грає в кожному непоглинаючому стані, ми отримаємо середню кількість ігор до поглинання з цього стану. Тому, якщо гравець починається з $3K, середня кількість ігор Black Jack вона буде грати до поглинання

\[1.07 + 1.78 + 2.25 + 0.90 = 6.0 \nonumber \]

Тобто, ми очікуємо, що гравець буде або мати $5,000 або нічого на 7-й ставці.

Нарешті, ми знаходимо матрицю розв'язку, не піднімаючи матрицю переходу до вищих потужностей. Матриця FA дає нам матрицю рішення.

\ [\ mathrm {FA} =\ лівий [\ почати {масив} {cccc}
1.54 & .90 & .47\
1.35 & 2.25 & 1.18 & .47\\
1.07 & 1.78 & 2.25 & .90\\
.64 & 1.07 & 1.35 & 1.54
\ кінець {масив}\ праворуч]\ лівий [\ почати {масив} {cc}
.6 & 0\\
0 & 0\\
0 & 0\\
0 & .4
\ кінець {масив}\ праворуч] =\ лівий [\ begin {масив} {cc}
.92 & .08\
.81 & .19\\
.64 & .36\\
.38 & .62
\ end {масив}\ право]\ nonumber\]

яка така ж, як і наступна матриця, яку ми отримали шляхом підняття матриці переходу до вищих потужностей.

Приклад\(\PageIndex{6}\)

У професійній школі студенти повинні пройти і пройти урок англійської письма/мовлення, щоб отримати свій професійний ступінь. Студенти повинні пройти клас протягом першого кварталу, який вони зараховують. Якщо вони не здають клас, вони беруть його знову у другому семестрі. Якщо вони зазнають невдачі двічі, їм не дозволяється перездавати його знову, і тому не зможуть отримати ступінь.

Учні можуть перебувати в одному з 4 станів: пройшли клас (П), зараховані в клас вперше (С), перездають клас (R) або провалилися двічі і не можуть перездавати (F). Досвід показує, що 70% учнів, які беруть клас вперше, проходять і 80% учнів, які беруть клас вдруге.

Запишіть матрицю переходу і визначте поглинаючі стани. Знайдіть ймовірність поглинання в кінцевому підсумку в кожному з поглинаючих станів.

Рішення

Поглинаючі стани - P (прохід) і F (неодноразово виходять з ладу і не можуть перебрати). Матриця переходу T показана нижче.

Якщо підняти матрицю переходу T до високої потужності, ми виявимо, що вона залишається стабільною і дає нам довгострокові ймовірності опинитися в кожному з поглинаючих станів.

З учнів, які зараз беруть клас вперше, 94% врешті-решт здадуть. 6% врешті-решт провалиться двічі і не зможуть отримати ступінь.

З учнів, які зараз беруть клас вдруге, 80% врешті-решт пройдуть. 20% врешті-решт провалиться двічі і не зможуть отримати ступінь.

Матриця рішення містить ту ж інформацію в скороченому вигляді.

Зверніть увагу, що в цій конкретній проблемі нам не потрібно піднімати T до «дуже високої» потужності. Якщо знайти T ², ми бачимо, що він насправді дорівнює T ⁿ для вищих сил\(n\). T ⁿ стає стабільним після двох переходів; це має сенс у цій задачі, тому що після прийняття класу двічі, студент повинен пройти або не дозволяється перездавати його більше. Тому ймовірності більше не повинні змінюватися після двох переходів; до кінця двох переходів кожен учень досяг поглинаючого стану.

Поглинаючі ланцюги Маркова

1. Ланцюг Маркова - це поглинаюча ланцюг Маркова, якщо вона має хоча б одне поглинаючий стан. Стан i є поглинаючим станом, якщо як тільки система досягає стану i, вона залишається в цьому стані; тобто\(p_{ii} = 1\).
2. Якщо перехідна матриця T для поглинаючого ланцюга Маркова піднімається до вищих потужностей, вона досягає поглинаючого стану, званого матрицею розчину, і залишається там. The\(i\),\(j\) -й запис цієї матриці дає ймовірність поглинання в стані\(j\) при запуску в стані\(i\).
3. По черзі матрицю рішення можна знайти наступним чином.
   1. Висловіть матрицю переходу в канонічному вигляді, як показано нижче. \ [\ mathrm {T} =\ left [\ begin {масив} {ll}
      \ mathbf {I} _ {\ mathbf {n}} &\ mathbf {0}\
      \ mathbf {A} &\ mathbf {B}\ end {масив}
      \ право]\ nonumber\] де матриця ідентичності, а 0\(I_n\) - матриця ідентичності, а 0 - матриця всі нулі.
   2. Фундаментальна матриця\(F = (I - B)^{-1}\). Фундаментальна матриця допомагає нам знайти кількість ігор, зіграних до поглинання.
   3. ФА - матриця розв'язку\(i\), у\(j\) якій, -й запис дає ймовірність поглинання в стані\(j\) при запуску в стані\(i\).
4. Сума записів рядка фундаментальної матриці дає нам очікувану кількість кроків до поглинання для непоглинаючого стану, пов'язаного з цим рядком.