16.4: Перехідність і повторення для дискретних часових ланцюгів

\(\newcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\bs}{\boldsymbol}\)\( \newcommand{\cl}{\text{cl}} \)

Вивчення марковських ланцюгів дискретного часу, зокрема граничної поведінки, критично залежить від випадкових часів між відвідуваннями заданого стану. Природа цих випадкових часів призводить до фундаментальної дихотомії станів.

Основна теорія

Як завжди, наша відправна точка - це простір ймовірності\( (\Omega, \mathscr{F}, \P) \), так що\( \Omega \) це простір\( \mathscr{F} \) вибірки,\( \sigma \) -алгебра подій та\( \P \) міра ймовірності на\( (\Omega, \mathscr{F}) \). Припустимо, що тепер\( \bs{X} = (X_0, X_1, X_2, \ldots) \) це (однорідний) марковський ланцюжок дискретного часу з (зрахунковим) простором стану\( S \) та матрицею ймовірностей переходу\( P \). Так за визначенням,\[ P(x, y) = \P(X_{n+1} = y \mid X_n = x) \] для\( x, \, y \in S \) і\( n \in \N \). Нехай\( \mathscr{F}_n = \sigma\{X_0, X_1, \ldots, X_n\} \),\( \sigma \) -алгебра подій, визначених ланцюгом до часу\( n \in \N \), так що\( \mathfrak{F} = (\mathscr{F}_0, \mathscr{F}_1, \ldots) \) природна фільтрація пов'язана з\( \bs{X} \).

Часи ударів і ймовірності

\( A \)Дозволяти бути непорожнім підмножиною\( S \). Нагадаємо, що час удару до\( A \) є випадковою величиною, яка дає перший позитивний час, що ланцюг знаходиться в\( A \):\[ \tau_A = \min\{n \in \N_+: X_n \in A\} \] Оскільки ланцюг може ніколи не увійти\( A \), випадкова величина\( \tau_A \) приймає значення в\( \N_+ \cup \{\infty\} \) (нагадаємо нашу умовність, що мінімум порожнього набору є\( \infty \)). Нагадаємо також, що\( \tau_A \) це час зупинки для\( \bs{X} \). Тобто,\( \{\tau_A = n\} \in \mathscr{F}_n \) для\( n \in \N_+ \). Інтуїтивно це означає, що ми можемо визначити, чи можна,\( \tau_A = n \) спостерігаючи за ланцюгом до часу\( n \). Це явно так, оскільки явно\[ \{\tau_A = n\} = \{X_1 \notin A, \ldots, X_{n-1} \notin A, X_n \in A\} \] Коли\( A = \{x\} \) для\( x \in S \), ми спростимо позначення до\( \tau_x \). Ця випадкова величина дає перший позитивний час, коли ланцюг знаходиться в стані\( x \). Коли ланцюг входить у набір станів\( A \) вперше, ланцюг повинен відвідати певний стан в\( A \) перший раз, тому зрозуміло, що\[ \tau_A = \min\{\tau_x: x \in A\}, \quad A \subseteq S \] Далі ми визначаємо дві функції\( S \), пов'язані з часом удару.

Для\( x \in S \),\( A \subseteq S \) (непорожній), і\( n \in \N_+ \) визначити

1. \( H_n(x, A) = \P(\tau_A = n \mid X_0 = x)\)
2. \(H(x, A) = \P(\tau_A \lt \infty \mid X_0 = x) \)

Отже\( H(x, A) = \sum_{n=1}^\infty H_n(x, A) \).

Зверніть увагу, що\( n \mapsto H_n(x, A) \) це функція щільності ймовірності\( \tau_A \), задана\( X_0 = x \), за винятком того, що функція щільності може бути дефектною в тому сенсі, що сума\( H(x, A) \) може бути менше 1, в цьому випадку, звичайно,\( 1 - H(x, A) = \P(\tau_A = \infty \mid X_0 = x) \). Знову ж таки\( A = \{y\} \), коли, ми спростимо позначення до\( H_n(x, y) \) і\( H(x, y) \), відповідно. Зокрема,\( H(x, x) \) є ймовірність, починаючи з того\( x \), що ланцюг в кінцевому підсумку повертається до\( x \). Якщо\( x \ne y \),\( H(x, y) \) є ймовірність, починаючи з того\( x \), що ланцюг в кінцевому підсумку досягне\( y \). Просто знання, коли\( H(x, y) \) дорівнює 0, позитивний, а 1 виявиться чималим значенням в загальній структурі і обмежуючому поведінці ланцюга. Як функція на\( S^2 \), ми будемо називати\( H \) як ударну матрицю\( \bs{X} \). Однак зауважте, що на відміну від матриці переходу\( P \), ми не маємо структури ядра. Тобто не\( A \mapsto H(x, A) \) є мірою, тому зокрема, це взагалі не так\( H(x, A) = \sum_{y \in A} H(x, y) \). Ті ж зауваження стосуються і\( H_n \) для\( n \in \N_+ \). Однак існують цікаві зв'язки між матрицею переходу і матрицею ударів.

\( H(x, y) \gt 0 \)якщо і тільки\( P^n(x, y) \gt 0 \) для деяких\( n \in \N_+ \).

Доказ

Відзначимо, що\( \{X_n = y\} \subseteq \{\tau_y \lt \infty\} \) для всіх\( n \in \N_+ \), і\( \{\tau_y \lt \infty\} = \{X_k = y \text{ for some } k \in \N_+\} \). З зростаючої властивості ймовірності та нерівності Буля випливає\( n \in \N_+ \), що для кожного\[ P^n(x, y) \le H(x, y) \le \sum_{k=1}^\infty P^k(x, y) \]

Наступний результат дає базову залежність між послідовністю ударних ймовірностей і послідовністю ймовірностей переходу.

Припустимо, що\( (x, y) \in S^2 \). Тоді\[ P^n(x, y) = \sum_{k=1}^n H_k(x, y) P^{n-k}(y, y), \quad n \in \N_+ \]

Доказ

Цей результат випливає з кондиціонування\( \tau_y \). Починаючи в стані\( x \), ланцюг знаходиться в стані в\( y \) той час\( n \), коли і тільки в тому випадку, якщо ланцюг\( y \) вперше потрапляє в якийсь попередній час\( k \), а потім повертається\( y \) в інші\( n - k \) кроки. Більш формально,\[ P^n(x, y) = \P(X_n = y \mid X_0 = x) = \sum_{k=0}^\infty \P(X_n = y \mid \tau_y = k, X_0 = x) \P(\tau_y = k \mid X_0 = x) \] Але подія\( \tau_y = k \) має на увазі\( X_k = y \) і знаходиться в\( \mathscr{F}_k \). Звідси і властивість Маркова,\[ \P(X_n = y \mid \tau_y = k, X_0 = x) = \P(X_n = y \mid X_k = y, \tau_y = k, X_0 = x) = \P(X_n = y \mid X_k = y) = P^k(x, y) \] звичайно, за визначенням\( \P(\tau_y = k \mid X_0 = x) = H_k(x, y) \), тому результат слід шляхом підміни.

Припустимо, що\( x \in S \) і\( A \subseteq S \). Тоді

1. \( H_{n+1}(x, A) = \sum_{y \notin A} P(x, y) H_n(y, A) \)для\( n \in \N_+ \)
2. \( H(x, A) = P(x, A) + \sum_{y \notin A} P(x, y) H(y, A) \)

Доказ

Ці результати слідують за формою кондиціонування на\( X_1 \).

1. Починаючи в стані\( x \), ланцюг спочатку входить в\( A \) той час,\( n + 1 \) якщо і тільки в тому випадку, якщо ланцюг переходить в якийсь стан\( y \notin A \) в момент 1, а потім зі стану\( y \), спочатку входить по\( A \)\( n \) кроках. \[ H_{n+1}(x, A) = \P(\tau_A = n + 1 \mid X_0 = x) = \sum_{y \in S} \P(\tau_A = n + 1 \mid X_0 = x, X_1 = y) \P(X_1 = y \mid X_0 = x) \]Але\( \P(\tau_A = n + 1 \mid X_0 = x, X_1 = y) = 0 \) для\( y \in A \). За марківським і часом однорідним властивостям,\( \P(\tau_A = n + 1 \mid X_0 = x, X_1 = y) = \P(\tau_A = n \mid X_0 = y) = H_n(x, A) \) для\( y \notin A \). Звичайно\( \P(X_1 = y \mid X_0 = x) = P(x, y) \). Так що результат випливає за допомогою підміни.
2. Починаючи в стані\( x \), ланцюг з часом входить\( A \) якщо і тільки в тому випадку, якщо вона або входить\( A \) на першому кроці, або переходить в якийсь інший стан\( y \notin A \) на першому кроці, а потім в кінцевому підсумку входить\( A \) з\( y \). \[ H(x, A) = \P(\tau_A \lt \infty \mid X_0 = x) = \sum_{y \in S} \P(\tau_A \lt \infty \mid X_1 =y, X_0 = x) \P(X_1 = y \mid X_0 = x)\]Але\( \P(\tau_A \lt \infty \mid X_1 = y, X_0 = x) = 1\) для\( y \in A \). За марківським і однорідним властивостям,\(\P(\tau_A \lt \infty \mid X_1 = y, X_0 = x) = \P(\tau_A \lt \infty \mid X_0 = y) = H(y, A) \) для\( y \notin A \). Підставляючи у нас\[ H(x, A) = \sum_{y \in A} P(x, y) + \sum_{y \notin A} P(x, y) H(y, A) = P(x, A) + \sum_{y \notin A} P(x, y) H(y, A) \]

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

Нехай\( x \in S \).

1. Стан\( x \) рецидивуючий, якщо\( H(x, x) = 1 \).
2. Стан\( x \) є перехідним, якщо\( H(x, x) \lt 1 \).

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

Підрахунок змінних і потенціалів

Знову ж таки, припустимо, що\( A \) це непорожній набір станів. Природним доповненням до часу удару\( A \) є змінна підрахунку, яка дає кількість відвідувань\( A \) (у позитивні моменти). Таким чином, нехай\[ N_A = \sum_{n=1}^\infty \bs{1}(X_n \in A) \] Примітка, що\( N_A \) приймає значення в\( \N \cup \{\infty\} \). Нас в основному буде цікавити спеціальний випадок\( A = \{x\} \) для\( x \in S \), і в цьому випадку ми спростимо позначення до\( N_x \).

Нехай\( G(x, A) = \E(N_A \mid X_0 = x) \) за\( x \in S \) і\( A \subseteq S \). Потім\( G \) є ядро на\( S \) і\[ G(x, A) = \sum_{n=1}^\infty P^n(x, A) \]

Доказ

Зверніть увагу, що\[ G(x, A) = \E \left(\sum_{n=1}^\infty \bs{1}(X_n \in A) \biggm| X_0 = x\right) = \sum_{n=1}^\infty \P(X_n \in A \mid X_0 = x) = \sum_{n=1}^\infty P^n(x, A) \] обмін суми та очікуваного значення виправданий, оскільки терміни є невід'ємними. Для фіксованого\( x \in S \),\( A \mapsto G(x, A) \) є позитивною мірою на\( S \) так як\( A \mapsto P^n(x, A) \) є міра ймовірності на\( S \) для кожного\( n \in \N_+ \). Зауважте також, що\( A \mapsto N_A \) є випадковою мірою підрахунку\( S \) і, отже,\( A \mapsto G(x, A) \) є (детермінованою) позитивною мірою на\( S \).

Таким\( G(x, A) \) чином, очікувана кількість відвідувань\( A \) в позитивні моменти. Як завжди, коли\( A = \{y\} \) для\( y \in S \) ми спрощуємо позначення до\( G(x, y) \), а потім в більш загальному плані маємо\( G(x, A) = \sum_{y \in A} G(x, y) \) для\( A \subseteq S \). Отже, як матриця на\( S \),\( G = \sum_{n=1}^\infty P^n \). \( G \)Матриця тісно пов'язана з потенційною\( R \) матрицею\( \bs{X} \), заданою\( R = \sum_{n=0}^\infty P^n \). Отже\( R = I + G \), і\( R(x, y) \) дає очікувану кількість відвідувань\( y \in S \) в усі часи (не тільки позитивні моменти), починаючи з\( x \in S \). \( G \)Матриця більш корисна для наших цілей в цьому розділі.

Розподіл\( N_y \) має просте уявлення з точки зору ймовірностей удару. Зауважте, що через властивість Маркова та властивість однорідної за часом кожного разу\( y \), коли ланцюг досягає стану, майбутня поведінка не залежить від минулого і стохастично така ж, як ланцюг, що починається в стані в\( y \) момент 0. Це критичне спостереження на доказ наступної теореми.

Якщо\( x, \, y \in S \) тоді

1. \(\P(N_y = 0 \mid X_0 = x) = 1 - H(x, y)\)
2. \( \P(N_y = n \mid X_0 = x) = H(x, y) [H(y, y)]^{n-1}[1 - H(y, y)] \)для\( n \in \N_+ \)

Доказ

Ілюстрація\(\PageIndex{1}\): Візити до держави, що\( y \) починаються в штаті\( x \)

Суть доказу проілюстрована на графіці вище. Товсті лінії призначені як нагадування про те, що це не один крок переходи, а скоріше представляють всі шляхи між заданими вершинами. Зверніть увагу, що в особливому випадку, який\( x = y \) ми маємо\[ \P(N_x = n \mid X_0 = x) = [H(x, x)]^n [1 - H(x, x)], \quad n \in \N \] У всіх випадках підрахункова змінна\( N_y \) має по суті геометричний розподіл, але розподіл цілком може бути дефектним, з деякою часткою ймовірності маси в\( \infty \). Поведінка досить різна залежно від того,\( y \) є тимчасовим чи рецидивуючим.

Якщо\( x, \, y \in S \) і\( y \) є тимчасовим, то

1. \( \P(N_y \lt \infty \mid X_0 = x) = 1 \)
2. \( G(x, y) = H(x, y) \big/ [1 - H(y, y)] \)
3. \( H(x, y) = G(x, y) \big/ [1 + G(y, y)] \)

Доказ

1. Якщо\( y \) є тимчасовим, то\( H(y, y) \lt 1 \). Отже, використовуючи результат вище і геометричний ряд,\[\P(N_y \in \N_+ \mid X_0 = x) = \sum_{n=1}^\infty \P(N_y = n \mid X_0 = x) = H(x, y) [1 - H(y, y)] \sum_{n=1}^\infty [H(y, y)]^{n-1} = H(x, y)\] звідси\ почати {align*}\ P (n_y\ lt\ infty\ mid X_0 = x) & =\ P (n_y\ in\ n\ mid X_0 = x) =\ P (n_y = 0\ середина X_0 = x) +\ P (n_y\ in\ n_+\ середина X_0 = x)\ & = [1 - H (x, y)] + H (x, y) = 1\ кінець {вирівнювати*}
2. Використовуючи похідну геометричного ряду,\ почати {align*} G (x, y) & =\ E (n_y\ середина X_0 = x) =\ sum_ {n=1} ^\ infty n\ P (n_y = n\ mid X_0 = x)\ & = H (x, y) [1 - H (y, y)]\ sum_ {n=1} ^\ infty n [H (y, y)] ^ {n-1} =\ frac {H (x, y)} {1 - H (y, y)}\ end {вирівнювати*}
3. З (б),\( G(y, y) = H(y, y) \big/[1 - H(y, y)] \) так рішення для\( H(y, y) \) дає\( H(y, y) = G(y, y) \big/ [1 + G(y, y)] \). Підставляючи це назад у (b) дає\( G(x, y) = H(x, y)[1 + G(y, y)] \).

якщо\( x, \, y \in S \) і\( y \) є рецидивуючим, то

1. \( \P(N_y = 0 \mid X_0 = x) = 1 - H(x, y) \)і\( \P(N_y = \infty \mid X_0 = x) = H(x, y) \)
2. \( G(x, y) = 0 \)якщо\( H(x, y) = 0 \) і\( G(x, y) = \infty \) якщо\( H(x, y) \gt 0 \)
3. \( \P(N_y = \infty \mid X_0 = y) = 1 \)і\( G(y, y) = \infty \)

Доказ

1. Якщо\( y \)\( H(y, y) = 1 \) рецидивує, і так з результату вище,\( \P(N_y = n \mid X_0 = x) = 0 \) для всіх\( n \in \N_+ \). Звідси\( \P(N_y = \infty \mid X_0 = x) = 1 - \P(N_y = 0 \mid X_0 = x) = 1 - H(x, y) \).
2. Якщо\( H(x, y) = 0 \) тоді\( \P(N_y = 0 \mid X_0 = x) = 1 \), так\( \E(N_y \mid X_0 = x) = 0 \). Якщо\( H(x, y) \gt 0 \) тоді\( \P(N_y = \infty \mid X_0 = x) \gt 0 \) так\( \E(N_y \mid X_0 = x) = \infty \).
3. З результату вище,\( \P(N_y = n \mid X_0 = y) = 0 \) для всіх\( n \in \N \), так\( \P(N_y = \infty \mid X_0 = y) = 1 \).

Зверніть увагу, що між матрицею\( H \) та матрицею існує оборотний зв'язок\( G \); якщо ми знаємо одну, ми можемо обчислити іншу. Зокрема, ми можемо охарактеризувати швидкоплинність або повторення стану в терміні\( G \). Ось наш підсумок поки що:

Нехай\( x \in S \).

1. \( x \)Стан є перехідним тоді і тільки тоді\( H(x, x) \lt 1 \), коли і тільки якщо\( G(x, x) \lt \infty \).
2. \( x \)Стан повторюється тоді і тільки тоді\( H(x, x) = 1 \), коли і тільки якщо\( G(x, x) = \infty \).

Звичайно, класифікація також стосується матриці потенціалів\( R = I + G \). Тобто стан\( x \in S \) є тимчасовим тоді і тільки тоді, коли\( R(x , x) \lt \infty \) і стан\( x \) рецидивує тоді і тільки якщо\( R(x, x) = \infty \).

Відносини

Імовірності удару свідчать про важливе відношення до державного простору\( S \).

Бо\( (x, y) \in S^2 \), ми говоримо, що\( x \) призводить до\( y \) і ми пишемо,\( x \to y \) якщо\( x = y \) або\( H(x, y) \gt 0 \).

З отриманого вище результату випливає відразу, що\( x \to y \) якщо і тільки\( P^n(x, y) \gt 0 \) для деяких\( n \in \N \). З точки зору графа стану ланцюга,\( x \to y \) якщо і тільки якщо\( x = y \) або є спрямований шлях від\( x \) до\( y \). Зверніть увагу, що призводить до відношення є рефлексивним за визначенням:\( x \to x \) для кожного\( x \in S \). Відносини також мають ще одну важливу властивість.

Веде до відношення є перехідним: Для\( x, \, y, \, z \in S \), якщо\( x \to y \) і\( y \to z \) тоді\( x \to z \).

Доказ

Якщо\( x \to y \) і\( y \to z \), то існують\( j, \, k \in N \) такі, що\( P^j(x, y) \gt 0 \) і\( P^k(y, z) \gt 0 \). Але потім\( P^{j+k}(x, z) \ge P^j(x, y) P^k(y, z) \gt 0 \) так\( x \to z \).

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

Припустимо, що\( A \subseteq S \) це непорожній.

1. \( A \)закривається, якщо\( x \in A \) і\( x \to y \) має на увазі\( y \in A \).
2. \( A \)є нескорочуваним, якщо\( A \) закритий і не має належних замкнутих підмножин.

Припустимо,\( A \subseteq S \) що закрито. Тоді

1. \( P_A \), обмеження\( P \) to\( A \times A\), являє собою матрицю ймовірності переходу на\( A \).
2. \( \bs{X} \)\( A \)limited to - ланцюг Маркова з матрицею ймовірностей переходу\( P_A \).
3. \( (P^n)_A = (P_A)^n \)для\( n \in \N \).

Доказ

1. Якщо\( x \in A \) і\( y \notin A \), то\( x \) не призводить до\( y \) цього зокрема\( P(x, y) = 0 \). Звідси випливає, що\( \sum_{y \in A} P(x, y) = 1 \) для\( x \in A \)\( P_A \) so є матрицею ймовірностей переходу.
2. Це випливає з (а). Якщо ланцюг починається в\( A \), то ланцюг залишається в\( A \) на весь час, і звичайно ж, властивість Маркова все одно тримається.
3. Знову ж таки, це випливає з (а).

Звичайно, весь державний простір\( S \) закрито за визначенням. Якщо він ще й незвідний, то скажемо, що\( \bs{X} \) сама ланцюг Маркова незвідна. Нагадаємо, що для непорожньої\( A \) підмножини\( S \) і for\( n \in \N \) позначення\( P_A^n \) відноситься до\( (P_A)^n \) і ні\( (P^n)_A \). Загалом, це не те ж саме, а насправді для\( x, \, y \in A \), ймовірність\[ P_A^n(x, y) = \P(X_1 \in A, \ldots, X_{n-1} \in A, X_n = y \mid X_0 = x) \] переходити від\( x \) до\( y \)\( n \) кроком, залишаючись на\( A \) весь час. Але якщо\( A \) закритий, то, як зазначається в частині (в), це якраз\( P^n(x, y) \).

Припустимо, що\( A \) це непорожня підмножина\( S \). Тоді\( \cl(A) = \{y \in S: x \to y \text{ for some } x \in A\} \) є найменшим замкнутим набором\( A \), що містить, і називається закриттям\( A \). Тобто,

1. \( \cl(A) \)закритий.
2. \( A \subseteq \cl(A) \).
3. Якщо\( B \) закритий, а\( A \subseteq B \) потім\( \cl(A) \subseteq B \)

Доказ

1. Припустимо, що\( x \in \cl(A) \) і те\( x \to y \). Тоді існує\( a \in A \) таке, що\( a \to x \). За перехідним властивістю,\( a \to y \) а значить\( y \in \cl(A) \).
2. Якщо\( x \in A \) тоді\( x \to x \) так\( x \in \cl(A) \).
3. Припустимо,\( B \) що закрито і що\( A \subseteq B \). Якщо\( x \in \cl(A) \), то існує\( a \in A \) таке, що\( a \to x \). Звідси\( a \in B \) і\( a \to x \). Так як\( B \) закритий, то випливає, що\( x \in B \). Звідси\( \cl(A) \subseteq B \).

Нагадаємо, що для фіксованого натурального цілого числа\( k \), також\( P^k \) є матрицею ймовірності переходу, а фактично керує \( k \)ланцюгом Маркова -step\( (X_0, X_k, X_{2 k}, \ldots) \). Звідси випливає, що ми могли б розглянути призводить до відношення для цього ланцюга, і всі результати вище все одно будуть триматися (відносно, звичайно, ланцюга\( k \) -step). Зрідка нам потрібно буде розглядати це співвідношення, яким ми будемо позначати\( \underset{k} \to \), особливо в нашому дослідженні періодичності.

Припустимо, що\( j, \, k \in \N_+ \). Якщо\( x \, \underset{k}\to \, y \) і\( j \mid k \) тоді\( x \, \underset{j}\to \, y \).

Доказ

Якщо\( x \, \underset{k}\to \, y \) тоді існує\( n \in \N \) таке, що\( P^{n k}(x, y) \gt 0 \). Якщо\( j \mid k \), існує\( m \in \N_+ \) таке, що\( k = m j \). Звідси\( P^{n m j}(x, y) \gt 0 \) і так\( x \, \underset{j}\to \, y \).

Поєднуючи призводить до відношення\( \to \) з його зворотним, походить від відношення\( \leftarrow \), ми можемо отримати ще одне дуже корисне відношення.

Бо\( (x, y) \in S^2 \), ми говоримо, що\( x \) до і від\( y \) і пишемо,\( x \leftrightarrow y \) якщо\( x \to y \) і\( y \to x \).

За визначенням це відношення симетричне: якщо\( x \leftrightarrow y \) тоді\( y \leftrightarrow x \). З нашої роботи вище вона також є рефлексивною і перехідною. Таким чином, відношення до і від - це відношення еквівалентності. Як і всі відносини еквівалентності, він розділяє простір на взаємно неспільні класи еквівалентності. Клас еквівалентності стану\( x \in S \) ми будемо позначити\[ [x] = \{y \in S: x \leftrightarrow y\} \] таким чином, для будь-яких двох станів\( x, \, y \in S\),\( [x] = [y] \) або, і\( [x] \cap [y] = \emptyset \), крім того,\( \bigcup_{x \in S} [x] = S \).

Рисунок\(\PageIndex{2}\): Розділ співвідношення еквівалентності\( S \) на взаємно незв'язані класи еквівалентності

Два негативних результату:

1. Закрита множина не обов'язково є класом еквівалентності.
2. Клас еквівалентності не обов'язково закритий.

Приклад

Розглянемо тривіальний ланцюжок Маркова з простором стану\( S = \{0, 1\} \) і матрицею переходу\( P = \left[\begin{matrix} 0 & 1 \\ 0 & 1\end{matrix}\right] \). Таким чином, стан 0 призводить детерміновано до 1 за один крок, тоді як стан 1 поглинає. Для призводить до відносин єдиними відносинами є\( 0 \to 0 \)\( 0 \to 1 \), і\( 1 \to 1 \). Таким чином, класи еквівалентності є\( \{0\} \) і\( \{1\} \).

1. Весь простір стану\( S \) замкнутий, але не є класом еквівалентності.
2. \( \{0\} \)є класом еквівалентності, але не закритий.

З іншого боку, ми маємо наступний результат:

Якщо\( A \subseteq S \) є нескорочуваним, то\( A \) це клас еквівалентності.

Доказ

Fix\( x \in A \) (нагадаємо, що закриті множини не є порожніми за визначенням). Так як\( A \) закритий випливає, що\( [x] \subseteq A \). Так як\( A \) є нескоротним,\( \cl(y) = A \) для кожного\( y \in A \) і зокрема,\( \cl(x) = A \). Звідси випливає, що\( x \leftrightarrow y \) для кожного\( y \in A \). Звідси\( A \subseteq [x] \).

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

Перехідні та рецидивуючі класи

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

Якщо\( x \) є рецидивуючим станом, а\( x \to y \) потім\( y \) рецидивуючим і\( H(x, y) = H(y, x) = 1 \).

Доказ

Результат тривіально тримає якщо\( x = y \), так ми припускаємо\( x \ne y \). Нехай\( \alpha(x, y) \) позначають ймовірність, починаючи з того\( x \), що ланцюг досягає\( y \) без проміжної віддачі до\( x \). Це повинно бути так, що\( \alpha(x, y) \gt 0 \) з тих пір\( x \to y \). З точки зору графіка\( \bs{X} \), якщо є шлях від\( x \) до\( y \), то існує шлях від\( x \) до\( y \) без циклів. Починаючи з\( x \), ланцюг міг не повернутися\( x \), спочатку досягнувши\( y \) без проміжного повернення\( x \), а потім з\( y \) ніколи не досягаючи\( x \). З маркова і часу однорідних властивостей випливає, що\( 1 - H(x, x) \ge \alpha(x, y)[1 - H(y, x)] \ge 0 \). Але\( H(x, x) = 1 \) так випливає, що\( H(y, x) = 1 \). Отже, ми тепер знаємо, що існують позитивні цілі числа\( j, \, k \) такі, що\( P^j(x, y) \gt 0 \) і\( P^k(y, x) \gt 0 \). Отже, для кожного\( n \in \N \),\[ P^{j + k + n}(y, y) \ge P^k(y, x) P^n(x, x) P^j(x, y) \] нагадайте, що\( G(x, x) = \infty \) так як\( x \) повторюється. Таким чином, підсумовування\( n \) в відображеному рівнянні дає\( G(y, y) = \infty \). Звідси\( y \) і рецидивний. Нарешті, змінюючи ролі\( x \) і\( y \), якщо випливає, що\( H(x, y) = 1 \)

З останньої теореми відзначимо, що якщо\( x \) рецидивний, то всі стани в\( [x] \) також рецидивні. Таким чином, для кожного класу еквівалентності або всі стани є перехідними, або всі стани рекурентні. Тому ми можемо посилатися на перехідні або повторювані класи, а також стани.

Якщо\( A \) є повторюваним класом еквівалентності\( A \), то є незменшеним.

Доказ

Припустимо, що\( x \in A \) і те\( x \to y \). Оскільки\( x \) є рецидивуючим,\( y \) є також рецидивуючим і\( y \to x \). Звідси\( x \leftrightarrow y \) і так\( A \),\( y \in A \) оскільки є класом еквівалентності. Припустимо,\( B \subseteq A \) що закрито. Оскільки\( B \) це непорожній за визначенням, існує\( x \in B \) і так\( x \in A \) само. Для кожного\( y \in A \),\( x \leftrightarrow y \) так\( y \in B \) з тих пір\( B \) закритий. Таким чином\( A \),\( A = B \) так є нескоротним.

Якщо\( A \) кінцевий і закритий, то\( A \) має рецидивуючий стан.

Доказ

Виправити\( x \in A \). Так як\( A \) закритий, то випливає, що\( \P(N_A = \infty \mid X_0 = x) = 1 \). Оскільки\( A \) є кінцевим, то випливає, що\( \P(N_y = \infty \mid X_0 = x) \gt 0 \) для деяких\( y \in A \). Але потім\( y \) повторюється.

Якщо\( A \) скінченний і нескоротний, то\( A \) є повторюваним класом еквівалентності.

Доказ

Зауважте, що\( A \) це клас еквівалентності за результатом вище, і\( A \) має повторюваний стан за попереднім результатом. Звідси випливає, що всі стани в\( A \) рецидивні.

Таким чином, ланцюжок Маркова\( \bs{X} \) матиме колекцію (можливо, порожню) рекурентних класів еквівалентності,\( \{A_j: j \in J\} \) де\( J \) є лічильний набір індексів. Кожен\( A_j \) нескоротний. Дозвольте\( B \) позначити множину всіх перехідних станів. Множина\( B \) може бути порожньою або складатися з ряду класів еквівалентності, але структура класів\( B \) зазвичай не важлива для нас. Якщо ланцюг починається\( A_j \) для деяких,\( j \in J \) то ланцюг залишається в\( A_j \) назавжди, відвідуючи кожен стан нескінченно часто з ймовірністю 1. Якщо ланцюг починається\( B \), то ланцюг може залишитися\( B \) назавжди (але тільки якщо\( B \) нескінченний) або може увійти в один з повторюваних класів\( A_j \), ніколи не втекти. Однак у будь-якому випадку ланцюг відвідає даний перехідний стан лише скінченно багато разів з ймовірністю 1. Ця основна структура відома як канонічне розкладання ланцюга і показана в графічному вигляді нижче. Краї від\( B \) мають сірий колір, щоб вказувати на те, що цих переходів може не існувати.

Ілюстрація\(\PageIndex{3}\): Канонічна декомпозиція державного простору

Перебування ймовірності та класифікаційний тест

Припустимо, що\( A \) це належна підмножина\( S \). Тоді

1. \(P_A^n(x, A) = \P(X_1 \in A, X_2 \in A, \ldots, X_n \in A \mid X_0 = x) \)для\( x \in A \)
2. \( \lim_{n \to \infty} P_A^n(x, A) = \P(X_1 \in A, X_2 \in A \ldots \mid X_0 = x) \)для\( x \in A \)

Доказ

Нагадаємо, що\( P_A^n \) означає\( P_A \),\( (P_A)^n \) де знаходиться обмеження\( P \) до\( A \times A \).

1. Це наслідок властивості Маркова, і є ймовірність того, що ланцюг затримується\( A \) хоча б через час\( n \), починаючи в\( x \in A \).
2. Це випливає з (а) і теореми неперервності для спадних подій. Це ймовірність того, що ланцюг залишиться\( A \) назавжди, починаючи з\( x \in A \).

Давайте\( g_A \) позначимо функцію, визначену частиною (b), так що\[ g_A(x) = \P(X_1 \in A, X_2 \in A, \ldots \mid X_0 = x), \quad x \in A \] Функція ймовірності перебування\( g_A \) є цікавим доповненням до матриці ударів, вивченої вище. Наступний результат характеризує цю функцію і надає метод, який може бути використаний для її обчислення, принаймні в деяких випадках.

For\( A \subset S \),\( g_A \) є найбільшою функцією\( A \), яка приймає значення в\( [0, 1] \) і задовольняє\( g = P_A g \). Причому, або\( g_A = \bs{0}_A \) або\( \sup\{g_A(x): x \in A\} = 1 \).

Доказ

Зверніть увагу, що\( P_A^{n+1} \bs{1}_A = P_A P_A^n \bs{1}_A\) для\( n \in \N \). Прийняття межі як\( n \to \infty \) і використання теореми обмеженої збіжності дає\( g_A = P_A g_A \). Припустимо, що тепер\( g \) це функція на\( A \) що приймає значення в\( [0, 1] \) і задовольняє\( g = P_A g \). Тоді\( g \le \bs{1}_A \) і значить\( g \le P_A^n \bs{1}_A \) для всіх\( n \in \N \). Нехай\( n \to \infty \) випливає, що\( g \le g_A \). Далі нехай\( c = \sup\{g_A(x): x \in A\} \). Потім\( g_A \le c \, \bs{1}_A \) і значить\( g_A \le c \, P_A^n \bs{1}_A \) для кожного\( n \in \N \). Здача\( n \to \infty \) дає\( g_A \le c \, g_A \). Звідси випливає, що\( g_A = \bs{0}_A \) або або\( c = 1 \).

Зауважте, що характеристика в останньому результаті включає в себе нуль-один закон роду: або ймовірність того, що ланцюг залишається\( A \) назавжди дорівнює 0 для кожного початкового стану\( x \in A \), або ми можемо знайти стани, в\( A \) яких ймовірність довільно близька до 1. Наступні два результати досліджують взаємозв'язок між функцією перебування та повторенням.

Припустимо, що\( \bs{X} \) це незведена, повторювана ланцюг з простором стану\( S \). Тоді\( g_A = \bs{0}_A \) для кожного належного\( A \) підмножини\( S \).

Доказ

Виправте\( y \notin A \) і зверніть увагу, що\( 0 \le g_A(x) \le 1 - H(x, y) \) для кожного\( x \in A \). Але\( H(x, y) = 1 \) так як ланцюг нескоротна і рецидивна. Звідси\( g_A(x) = 0 \) для\( x \in A \).

Припустимо, що\( \bs{X} \) це незведена ланцюг Маркова з простором стану\( S \) та матрицею ймовірностей переходу\( P \). Якщо існує\( x \) такий стан, що\( g_A = \bs{0}_A \) де\( A = S \setminus \{x\} \), то\( \bs{X} \) рецидивний.

Доказ

З\( A \), як визначено вище, зверніть увагу, що\(1 - H(x, x) = \sum_{y \in A} P(x, y) g_A(y) \). Отже\( H(x, x) = 1 \), так\( x \) і повторюється. Оскільки\( \bs{X} \) нескоротний, то випливає, що\( \bs{X} \) є рецидивуючим.

Більш загально, припустимо, що\( \bs{X} \) це ланцюг Маркова з простором стану\( S \) та матрицею ймовірностей переходу\( P \). Останні дві теореми можуть бути використані для перевірки того, чи є клас нескорочуваної еквівалентності\( C \) рекурентним або перехідним. Закріплюємо стан\( x \in C \) і встановлюємо\( A = C \setminus \{x\} \). Потім ми спробуємо вирішити рівняння\( g = P_A g \) далі\( A \). Якщо єдине рішення, яке приймає значення в\( [0, 1] \) є\( \bs{0}_A \), то клас\( C \) повторюється за попереднім результатом. Якщо є нетривіальні рішення, то\( C \) є минущим. Часто ми намагаємося вибрати\( x \), щоб зробити обчислення легкими.

Обчислення вражаючих ймовірностей та потенціалів

Ми зараз знаємо зовсім небагато про ланцюги Маркова, і ми часто можемо класифікувати стани і обчислювати цікаві величини. Однак ми поки не знаємо, як обчислити:

• \( G(x, y) \)коли\( x \) і\( y \) є тимчасовими
• \( H(x, y) \)коли\( x \) є минущим і\( y \) є минущим або рецидивуючим.

Ці проблеми пов'язані, через загальну зворотну залежність між матрицею\( H \) і матрицею,\( G \) зазначеної в нашому обговоренні вище. Як завжди, припустимо, що\( \bs{X} \) це ланцюг Маркова з простором стану\( S \), і нехай\( B \) позначимо множину перехідних станів. Наступний результат показує, як обчислюється\( G_B \), матриця\( G \) обмежена перехідними станами. Нагадаємо, що значення цієї матриці кінцеві.

\( G_B \)задовольняє рівнянню\( G_B = P_B + P_B G_B \) і є найменшим невід'ємним розв'язком. Якщо\( B \) кінцевий, то\( G_B = (I_B - P_B)^{-1} P_B \).

Доказ

Спочатку зауважте,\( (P^n)_B = (P_B)^n \) оскільки шлях між двома перехідними станами може проходити лише через інші перехідні стани. Таким чином\( G_B = \sum_{n=1}^\infty P_B^n \). З теореми про монотонну збіжність випливає, що\( P_B G_B = G_B - P_B \). Припустимо, що тепер\( U \) це невід'ємна матриця на\( B \) задоволення\( U = P_B + P_B U \). Потім\( U = \sum_{k=1}^n P_B^k + P_B^{n+1} U \) для кожного\( n \in \N_+\). Отже\( U \ge \sum_{k=1}^n P_B^k \), для кожного\( n \in \N_+ \) і тому\( U \ge G_B \). Звідси випливає, що\( (I_B - P_B)(I_B + G_B) = I_B \). Якщо\( B \) скінченна, матриця\( I_B - P_B \) є оборотною.

Тепер, коли ми можемо обчислити\( G_B \), ми також можемо обчислити,\( H_B \) використовуючи результат вище. Все, що залишається, - це обчислити ймовірність удару,\( H(x, y) \) коли\( x \) є тимчасовим і\( y \) повторюваним. Перше, на що слід звернути увагу, це те, що ймовірність потрапляння - це властивість класу.

Припустимо, що\( x \) це перехідний і\( A \) що рекурентний клас. Тоді\( H(x, y) = H(x, A) \) для\( y \in A \).

Тобто, починаючи в перехідному стані\( x \in S \), ймовірність удару to\( y \) є постійною для\( y \in A \), і є якраз ймовірністю попадання в клас\( A \). Як і раніше, давайте\( B \) позначимо множину перехідних станів і припустимо, що\( A \) це рекурентний клас еквівалентності. Давайте\( h_A \) позначимо функцію на\( B \) що дає ймовірність попадання класу\( A \), і нехай\( p_A \) позначимо функцію на\( B \) що дає ймовірність входу\( A \) на першому кроці:\[ h_A(x) = H(x, A), \; p_A(x) = P(x, A), \quad x \in B \]

\( h_A = p_A + G_B p_A \).

Доказ

Спочатку зверніть увагу, що\( \P(\tau_A = n \mid X_0 = x) = (P_B^{n-1} p_A)(x) \) для\( n \in \N_+ \). Потім результат випливає, підсумовуючи\( n \).

Цей результат є адекватним, якщо ми вже обчислили\( G_B \) (наприклад, використовуючи результат вище). Однак ми можемо просто захотіти обчислити\( h_A \) безпосередньо.

\( h_A \)задовольняє рівнянню\( h_A = p_A + P_B h_A \) і є найменшим невід'ємним розв'язком. Якщо\( B \) скінченно,\( h_A = (I_B - P_B)^{-1} p_A \).

Доказ

По-перше, кондиціонування на\( X_1 \) дає\( h_A = p_A + P_B h_A \). Далі припустимо, що\( h \) є ненегативним і задовольняє\( h = p_A + P_B h \). Потім\( h = p_A + \sum_{k=1}^{n-1} P_B^k p_A + P_B^n h \) для кожного\( n \in \N_+ \). Звідси\( h \ge p_A + \sum_{k=1}^{n-1} P_B^k p_A \). Здача\( n \to \infty \) дає\( h \ge h_A \). Представлення, коли\( B \) є кінцевим, випливає з наведеного вище результату.

Приклади і застосування

скінченні ланцюги

Розглянемо ланцюжок Маркова з простором стану\( S = \{a, b, c, d\} \) та матрицею переходу,\( P \) наведеною нижче:

\[ P = \left[ \begin{matrix} \frac{1}{2} & \frac{2}{3} & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \end{matrix} \right] \]

1. Намалюйте графік стану.
2. Знайдіть еквівалентні класи і класифікуйте кожен як перехідний або рекурентний.
3. Обчислити матрицю\( G \).
4. Обчислити матрицю\( H \).

Відповідь

1. Граф стану

   

2. \( \{a, b\} \)рецидивний;\( \{c\} \) рецидивуючий;\( \{d\} \) минущий.
3. \( G = \left[ \begin{matrix} \infty & \infty & 0 & 0 \\ \infty & \infty & 0 & 0 \\ 0 & 0 & \infty & 0 \\ \infty & \infty & \infty & \frac{1}{3} \end{matrix} \right] \)
4. \( H = \left[ \begin{matrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \frac{2}{3} & \frac{2}{3} & \frac{1}{3} & \frac{1}{4} \end{matrix} \right] \)

Розглянемо ланцюжок Маркова з простором стану\( S = \{1, 2, 3, 4, 5, 6\} \) та матрицею переходу,\( P \) наведеною нижче:

\[ P = \left[ \begin{matrix} 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \frac{1}{4} & 0 & \frac{1}{2} & 0 & \frac{1}{4} & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{3} & 0 & \frac{2}{3} & 0 \\ 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} \end{matrix} \right] \]

1. Намалюйте граф стану.
2. Знайдіть класи еквівалентності та класифікуйте кожен як рекурентний або перехідний.
3. Обчислити матрицю\( G \).
4. Обчислити матрицю\( H \).

Відповідь

1. Граф стану

   

2. \( \{1, 3, 5\} \)рецидивний;\( \{2, 6\} \) минущий;\( \{4\} \) рецидивуючий.
3. \( G = \left[ \begin{matrix} \infty & 0 & \infty & 0 & \infty & 0 \\ \infty & \frac{1}{2} & \infty & \infty & \infty & 2 \\ \infty & 0 & \infty & 0 & \infty & 0 \\ 0 & 0 & 0 & \infty & 0 & 0 \\ \infty & 0 & \infty & 0 & \infty & 0 \\ \infty & \frac{1}{2} & \infty & \infty & \infty & 1 \end{matrix} \right] \)
4. \( H = \left[ \begin{matrix} 1 & 0 & 1 & 0 & 1 & 0 \\ \frac{1}{2} & \frac{1}{3} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ \frac{1}{2} & \frac{1}{3} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \end{matrix} \right] \)

Розглянемо ланцюжок Маркова з простором стану\( S = \{1, 2, 3, 4, 5, 6\} \) та матрицею переходу,\( P \) наведеною нижче:

\[ P = \left[ \begin{matrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 \\ \frac{1}{4} & \frac{3}{4} & 0 & 0 & 0 & 0 \\ \frac{1}{4} & 0 & \frac{1}{2} & \frac{1}{4} & 0 & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{matrix} \right] \]

1. Намалюйте граф стану.
2. Знайдіть класи еквівалентності та класифікуйте кожен як рекурентний або перехідний.
3. Обчислити матрицю\( G \).
4. Обчислити матрицю\( H \).

Відповідь

1. Граф стану

   

2. \( \{1, 2\} \)рецидивний;\( \{3, 4\} \) минущий;\( \{5, 6\} \) рецидивуючий.
3. \( G = \left[ \begin{matrix} \infty & \infty & 0 & 0 & 0 & 0 \\ \infty & \infty & 0 & 0 & 0 & 0 \\ \infty & \infty & \frac{7}{5} & \frac{4}{5} & \infty & \infty \\ \infty & \infty & \frac{4}{5} & \frac{3}{5} & \infty & \infty \\ 0 & 0 & 0 & 0 & \infty & \infty \\ 0 & 0 & 0 & 0 & \infty & \infty \end{matrix} \right] \)
4. \( H = \left[ \begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ \frac{4}{5} & \frac{4}{5} & \frac{7}{12} & \frac{1}{2} & \frac{1}{5} & \frac{1}{5} \\ \frac{3}{5} & \frac{3}{5} & \frac{1}{3} & \frac{3}{8} & \frac{2}{5} & \frac{2}{5} \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \end{matrix} \right] \)

Спеціальні моделі

Прочитайте ще раз визначення ланцюгів Еренфеста та ланцюгів Бернуллі-Лапласа. Зауважте, що оскільки ці ланцюги є нескорочуваними і мають скінченні простори стану, вони є рецидивними.

Прочитайте обговорення рецидивів у розділі про ланцюги надійності.

Прочитайте дискусію про випадкові прогулянки далі\( \Z^k \) в розділі про випадкові прогулянки на графіках.

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

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

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