16.7: Зворот часу в ланцюжках дискретного часу

\(\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}} \)

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

• Новий процес все ж Марков?
• Якщо так, то як нова матриця ймовірностей переходу відноситься до вихідної?
• За яких умов прямий і зворотний процеси стохастично однакові?

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

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

Зворотні ланцюги

Нашою відправною точкою є (однорідний) марковський ланцюг дискретного часу\( \bs X = (X_0, X_1, X_2, \ldots) \) з (зрахунковим) простором стану\( S \) та матрицею ймовірностей переходу\( P \). \( m \)Дозволяти позитивне ціле число, який ми будемо думати як термінальний час або скінченний горизонт часу. Ми не будемо морочитися вказувати на залежність від\( m \) умовно, оскільки в кінцевому підсумку термінальний час не матиме значення. Визначте\( \hat X_n = X_{m-n} \) для\( n \in \{0, 1, \ldots, m\} \). Таким чином, процес вперед у часі, в\( \bs X = (X_0, X_1, \ldots, X_m) \) той час як процес назад у часі\[ \hat{\bs X} = (\hat X_0, \hat X_1, \ldots, \hat X_m) = (X_m, X_{m-1}, \ldots, X_0) \]

Бо\( n \in \{0, 1, \ldots, m\} \), давайте\[ \hat{\mathscr F}_n = \sigma\{\hat X_0, \hat X_1, \ldots, \hat X_n\} = \sigma\{X_{m-n}, X_{m - n + 1}, \ldots, X_m\} \] позначимо\( \sigma \) алгебру подій процесу\( \hat{\bs X} \) до часу\( n \). Отже, звичайно, подія на\( \hat{\bs X} \) час\( n \) - це подія на\( \bs X \) час\( m - n \) вперед. Наш перший результат полягає в тому, що зворотний процес все ще є марковським ланцюгом, але не однорідним часом взагалі.

Процес\( \hat{\bs X} = (\hat X_0, \hat X_1, \ldots, \hat X_m) \) є марковським ланцюгом, але в цілому не є однорідним часом. Одноступінчаста матриця переходу за часом\( n \in \{0, 1, \ldots, m - 1\} \) задається\[ \P(\hat X_{n+1} = y \mid \hat X_n = x) = \frac{\P(X_{m - n - 1} = y)}{\P(X_{m - n} = x)} P(y, x), \quad (x, y) \in S^2\]

Доказ

Нехай\( A \in \hat{\mathscr F}_n \) і\( x, \, y \in S \). Потім\ почати {вирівнювати*}\ P (\ капелюх X_ {n+1} = у\ середина\ капелюх x_n = х, А) & =\ розриву {\ P (\ капелюх X_ {n+1} = у,\ капелюх x_n = х, А)} {\ P (\ капелюх x_n = х, А)} =\ frac {\ P (X_ {m - 1} = у, Х_ {м - п} = х, А)} {\ P (X_ {m - n} = х, А)}\\ & =\ розрив {\ P (А\ середина X_ {м - 1} = у, X_ {м - n} = х)\ P (X_ {m - n} = х\ середина X_ {м - 1} = y)\ Р (X_ {m - n - 1} = y)} {\ P (A\ mid X_ {m - n} = x)\ P (X_ {m - n} = x)}\ end {align*} Але\( A \in \sigma\{X_{m - n}, \ldots, X_m\} \) і так за властивістю Маркова для\( \bs X \),\[ \P(A \mid X_{m - n - 1} = y, X_{m - n} = x) = \P(A \mid X_{m - n} = x) \] За часом однорідності\( \bs X \),\(\P(X_{m - n} = x \mid X_{m - n - 1} = y) = P(y, x)\). Підміна та спрощення дає\[ \P(\hat X_{n+1} = y \mid \hat X_n = x, A) = \frac{\P(X_{m - n - 1} = y)}{\P(X_{m - n} = x)} P(y, x) \]

Однак зворотний ланцюг буде однорідною за часом, якщо\( X_0 \) має інваріантний розподіл.

Припустимо, що\( \bs X \) є незведеним і позитивним рецидивом, з (унікальною) інваріантною функцією щільності ймовірності\( f \). Якщо\( X_0 \) має інваріантний розподіл ймовірностей, то\( \hat{\bs X} \) є однорідним за часом ланцюгом Маркова з перехідною матрицею,\( \hat P \) заданою\[ \hat P(x, y) = \frac{f(y)}{f(x)} P(y, x), \quad (x, y) \in S^2 \]

Доказ

Це випливає з результату вище. Нагадаємо, що якщо\( X_0 \) є PDF\( f \), то\( X_k \) має PDF\( f \) для кожного\( k \in \N \).

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

Припустимо, що\( \bs X \) це ергодична, з (унікальною) інваріантною функцією щільності ймовірності\( f \). Незалежно від розподілу\( X_0 \),\[\P(\hat X_{n+1} = y \mid \hat X_n = x) \to \frac{f(y)}{f(x)} P(y, x) \text{ as } m \to \infty\]

Доказ

Це випливає з умовної ймовірності вище і нашого дослідження граничної поведінки ланцюгів Маркова. Так\( \bs X \) як ергодичний,\( \P(X_k = x) \to f(x) \) як\( k \to \infty \) для кожного\( x \in S \).

Ці три результати є мотивацією до наступного визначення. Ми можемо узагальнити, визначивши розворот незведеного ланцюга Маркова, доки існує позитивна, інваріантна функція. Нагадаємо, що позитивна інваріантна функція визначає позитивну міру на\( S \), але, звичайно, не взагалі розподіл ймовірностей.

Припустимо, що\( \bs X \) це незведена ланцюг Маркова з матрицею переходу\( P \), і що\( g: S \to (0, \infty) \) є інваріантним для\( \bs X \). Розворот відносно ланцюга\( \hat{\bs X} = (\hat X_0, \hat X_1, \ldots) \) Маркова\( \bs X \) з матрицею ймовірності переходу,\( \hat P \) визначеною\( g \)\[\hat P(x, y) = \frac{g(y)}{g(x)} P(y, x), \quad (x, y) \in S^2\]

Доказ

Ми повинні показати, що\( \hat P \) це дійсна матриця ймовірності переходу, так що визначення має сенс. Так як\( g \) є інваріантним для\( \bs X \),\[\sum_{y \in S} \hat P(x, y) = \frac{1}{g(x)} \sum_{y \in S} g(y) P(y, x) = \frac{g(x)}{g(x)} = 1, \quad x \in S\]

Нагадаємо, що якщо\( g \) є позитивною інваріантною функцією,\( \bs X \) то так є\( c g \) для кожної позитивної константи\( c \). Зверніть увагу, що\( g \) і\( c g \) генеруйте таку ж зворотну ланцюжок. Отже, розглянемо випадки:

Припустимо, що\( \bs X \) це незведена ланцюг Маркова на\( S \).

1. Якщо\( \bs X \) є рецидивуючим, то\( \bs X \) завжди має позитивну інваріантну функцію, яка є унікальною аж до множення на позитивні константи. Отже, розворот повторюваного ланцюга\( \bs X \) завжди існує і є унікальним, і тому ми можемо посилатися на розворот\( \bs X \) без посилання на інваріантну функцію.
2. Ще краще, якщо\( \bs X \) позитивний рекуррент, то існує унікальна інваріантна функція щільності ймовірності, а розворот\( \bs X \) може бути інтерпретований як час розвороту (щодо термінального часу), коли\( \bs X \) має інваріантний розподіл, як у мотивуючому вправи вище.
3. Якщо\( \bs X \) є перехідним, то може існувати або не існувати додатна інваріантна функція, а якщо така існує, вона може бути не унікальною (аж до множення на позитивні константи). Таким чином, перехідний ланцюг може не мати розворотів або більше одного.

Тим не менш, загальне визначення є природним, оскільки більшість важливих властивостей зворотного ланцюга випливають з рівняння балансу між матрицями переходу\( P \) і\( \hat P \), а інваріантна функція\( g \):\[ g(x) \hat P(x, y) = g(y) P(y, x), \quad (x, y) \in S^2 \] Ми побачимо, що це рівняння балансу повторюється з іншими об'єктами, пов'язаними з ланцюгами Маркова.

Припустимо, що\( \bs X \) це незведена ланцюг Маркова з інваріантною функцією\( g: S \to (0, \infty) \), і що\( \hat{\bs X} \) є\( \bs X \) розворотом щодо\( g \). Для\( x, \, y \in S \),

1. \( \hat P(x, x) = P(x, x) \)
2. \( \hat P(x, y) \gt 0 \)якщо і тільки якщо\( P(y, x) \gt 0 \)

Доказ

Ці результати випливають відразу з рівняння балансу\( g(x) \hat P(x, y) = g(y) P(y, x) \) для\( (x, y) \in S^2 \).

З частини (б) випливає, що графіки стану\( \bs X \) і\( \hat{\bs X} \) є зворотними один від одного. Тобто, щоб перейти від графіка стану одного ланцюга до графіка стану іншого, просто зворотний напрямок кожного ребра. Ось більш складний (але еквівалентний) варіант рівняння балансу для ланцюгів станів:

Припустимо ще раз, що\( \bs X \) є незведеним ланцюгом Маркова з інваріантною функцією\( g: S \to (0, \infty) \), і що\( \hat{\bs X} \) є\( \bs X \) розворотом щодо\( g \). Для кожної\( n \in \N_+ \) послідовності станів\( (x_1, x_2, \ldots, x_n, x_{n+1}) \in S^{n+1} \),\[ g(x_1) \hat P(x_1, x_2) \hat P(x_2, x_3) \cdots \hat P(x_n, x_{n+1}) = g(x_{n+1}) P(x_{n+1}, x_n) \cdots P(x_3, x_2) P(x_2, x_1) \]

Доказ

Це випливає з багаторазових застосувань основного рівняння. Коли\( n = 1 \), ми маємо рівняння балансу саме:\[g(x_1) \hat P(x_1, x_2) = g(x_2) P(x_2, x_1)\] Для\( n = 2 \),\[g(x_1) \hat P(x_1, x_2) \hat P(x_2, x_3) = g(x_2)P(x_2, x_1)\hat P(x_2, x_3) = g(x_3)P(x_3, x_2)P(x_2, x_1)\] Продовжуючи таким чином (або використовуючи індукцію) дає загальний результат.

Рівняння балансу має значення для степенів матриці переходу:

Припустимо ще раз, що\( \bs X \) є незведеним ланцюгом Маркова з інваріантною функцією\( g: S \to (0, \infty) \), і що\( \hat{\bs X} \) є\( \bs X \) розворотом щодо\( g \). Для кожного\( (x, y) \in S^2 \) і\( n \in \N \),\[ g(x) \hat P^n(x, y) = g(y) P^n (y, x) \]

Доказ

Коли\( n = 0 \), ліва і права сторони,\( g(x) \) якщо\( x = y \) і 0 в іншому випадку. Коли\( n = 1 \), ми маємо базове рівняння балансу:\( g(x) \hat P(x, y) = g(y) P(y, x) \). Загалом, для\( n \in \N_+ \), за попереднім результатом ми маємо\ begin {align*} g (x)\ капелюх p^n (x, y) &=\ sum_ {(x_1,\ ldots, x_ {n-1})\ in S^ {n-1}} г (x)\ капелюх P (x, x_1)\ капелюх P (x_1, x_2)\ cdots\ капелюх P (x_ {n-1}, y)\\ &=\ sum_ {(x_1,\ ldots, x_ {n-1})\ в S^ {n-1}} г (y) Р (y, x_ {n-1}) Р (x_ {n-1}, x_ {n-2})\ cdots P (x_1, x) = г (у) p^n (y, x)\ end {вирівнювати*}

Тепер ми можемо узагальнити простий результат вище.

Припустимо ще раз, що\( \bs X \) є незведеним ланцюгом Маркова з інваріантною функцією\( g: S \to (0, \infty) \), і що\( \hat{\bs X} \) є\( \bs X \) розворотом щодо\( g \). Для\( n \in \N \) і\( (x, y) \in S^2 \),

1. \( P^n(x, x) = \hat P^n(x, x) \)
2. \( \hat P^n(x, y) \gt 0 \)якщо і тільки якщо\( P^n(y, x) \gt 0 \)

З точки зору графіків стану частина (b) має очевидне значення: якщо\( x \) в початковому графі стану існує шлях довжиною\( n \) від\( y \) до, то\( y \) в графі зворотного стану існує шлях довжиною\( n \) від\( x \) до. Визначення часового розвороту симетрично по відношенню до двох ланцюгів Маркова.

Припустимо ще раз, що\( \bs X \) є незведеним ланцюгом Маркова з інваріантною функцією\( g: S \to (0, \infty) \), і що\( \hat{\bs X} \) є\( \bs X \) розворотом щодо\( g \). Тоді

1. \( g \)також є інваріантним для\( \hat{\bs X} \).
2. \( \hat{\bs X} \)також є нескоротним.
3. \( \bs X \)є розворот по\( \hat{\bs X} \) відношенню до\( g \).

Доказ

1. Для\( y \in S \), використовуючи рівняння балансу,\[\sum_{x \in S} g(x) \hat P(x, y) = \sum_{x \in S} g(y) P(y, x) = g(y)\]
2. Припустимо\( (x, y) \in S^2 \). Так як\( \bs X \) є нескоротним, існують\( n \in \N \) с\( P^n(y, x) \gt 0 \). Але потім з попереднього результату,\( \hat P^n(x, y) \gt 0 \). \( \hat{\bs X} \)Звідси також нескоротний.
3. Це зрозуміло з симетричного співвідношення в фундаментальному результаті.

Рівняння балансу також має місце для потенційних матриць.

Припустимо, що\( \bs X \) і\( \hat{\bs X} \) є часовими розворотами стосовно інваріантної функції\( g: S \to (0, \infty) \). Для\( \alpha \in (0, 1] \),\( \alpha \) потенційні матриці пов'язані\[ g(x) \hat R_\alpha(x, y) = g(y) R_\alpha(y, x), \quad (x, y) \in S^2 \]

Доказ

Це легко випливає з наведеного вище результату та визначення матриць потенціалів:\ begin {align*} g (x)\ hat R_\ alpha (x, y) & = g (x)\ sum_ {n=0} ^\ infty\ alpha^n\ hat p^n (x, y) =\ sum_ {n=0} ^\ infty\ alpha^n (x)\ hat ^n N (х, у)\\ & =\ сума_ {n=0} ^\ infty\ альфа ^ n г (y) p^n (у, х) = г (у)\ сума_ {n = 0} ^\ infty\ альфа ^ n p^n (у, х) = г (у) R_\ альфа (y, x)\ end {вирівнювати*}

Ланцюги Маркова, які є часовими розворотами, мають багато важливих властивостей:

Припустимо, що\( \bs X \) і\( \hat{\bs X} \) є реверси часу. Тоді

1. \( \bs X \)і\( \hat{\bs X} \) мають один і той же тип (транзиторні, нульові рекурентні або позитивні рецидивні).
2. \( \bs X \)і\( \hat{\bs X} \) мають однаковий період.
3. \( \bs X \)і\( \hat{\bs X} \) мають однаковий середній час повернення\( \mu(x) \) для кожного\( x \in S \).

Доказ

Припустимо, що\( \bs X \) і\( \hat{\bs X} \) є часовими розворотами стосовно інваріантної функції\( g: S \to (0, \infty) \).

1. Очікувана кількість відвідувань штату\( x \in S \), починаючи з\( x \), однакова для обох ланцюгів:\( \hat R(x, x) = R(x, x) \). Отже, або обидва ланцюга є перехідними (якщо загальний потенціал кінцевий), або обидва ланцюга рекурентні (якщо загальний потенціал нескінченний). Якщо обидва ланцюга є рецидивними, то інваріантна функція\( g \) є унікальною аж до множення на позитивні константи, і обидва є нульовими рекуррентними if\( \sum_{x \in S} g(x) = \infty \) і обидва є додатними рекуррентними if\( \sum_{x \in S} g(x) \lt \infty \).
2. Це випливає, оскільки\( P^n(x, x) = \hat P^n(x, x) \) для всіх\( n \in \N \) і\( x \in S \).
3. Якщо обидва ланцюга перехідні або обидва є нульовими рецидивними, то\( \mu(x) = \hat \mu(x) = \infty \) для всіх\( x \in S \). Якщо обидва ланцюга позитивні повторювані, то для всіх\( n \in \N \) і\( x \in S \), у нас є\[\frac{1}{n} \sum_{k = 1}^n P^k(x, x) = \frac{1}{n} \sum_{k = 1}^n \hat P^k(x, x)\] Ліва сторона сходиться до\( 1 / \mu(x) \) як в\( n \to \infty \) той час як права сторона сходиться до\( 1 / \hat \mu(x) \) як\( n \to \infty \).

Основним моментом наступного результату є те, що нам не потрібно знати а-апріорі, що\( g \) є інваріантним для\( \bs X \), якщо ми можемо здогадатися\( g \) і\( \hat P \).

Припустимо ще раз,\( \bs X \) що незведена з матрицею ймовірностей переходу\( P \). Якщо існує функція\( g: S \to (0, \infty) \) і матриця ймовірності переходу\( \hat P \) така, що\( g(x) \hat P(x, y) = g(y) P(y, x) \) для всіх\( (x, y) \in S^2 \), то

1. \( g \)є інваріантним для\( \bs X \).
2. \( \hat P \)являє собою перехідну матрицю\( \bs X \) розвороту по відношенню до\( g \).

Доказ

1. Оскільки\( \hat P \) це матриця ймовірності переходу, ми маємо ті самі обчислення, які ми бачили раніше:\[g P(x) = \sum_{y \in S} g(y) P(y, x) = \sum_{y \in S} g(x) \hat P(x, y) = g(x), \quad x \in S\]
2. Це випливає з (а) і визначення.

Як наслідок, якщо існує функція щільності ймовірності\( f \) на\( S \) і матриця ймовірності переходу\( \hat P \) така, що\( f(x) \hat P(x, y) = f(y) P(y, x) \) для всіх\( (x, y) \in S^2 \) тоді крім висновків вище, ми знаємо, що ланцюги\( \bs X \) і\( \hat{\bs X} \) є позитивними рекурентними.

Реверсивні ланцюги

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

Ще раз припустимо, що\( \bs X = (X_0, X_1, X_2, \ldots) \) це незведена ланцюг Маркова з матрицею переходу\( P \) і інваріантною функцією\( g: S \to (0, \infty) \). Якщо розворот по відношенню до\( g \) також має перехідну матрицю\( P \), то, як кажуть,\( \bs X \) є оборотним щодо\( g \).\( \bs X \) Тобто\( \bs X \) є оборотним щодо\( g \) якщо і тільки якщо\[ g(x) P(x, y) = g(y) P(y, x), \quad (x, y) \in S^2 \]

Зрозуміло\( \bs X \), що якщо є оборотним щодо\( g: S \to (0, \infty) \) інваріантної функції, то\( \bs X \) є оборотним щодо інваріантної функції\( c g \) для кожного\( c \in (0, \infty) \). Отже, знову ж таки, давайте розглянемо випадки.

Припустимо, що\( \bs X \) це незведена ланцюг Маркова на\( S \).

1. Якщо\( \bs X \) рецидивна, існує додатна інваріантна функція, яка є унікальною аж до множення на позитивні константи. Так\( \bs X \) що або оборотний або ні, і ми не повинні посилатися на інваріантну функцію\( g \).
2. Якщо\( \bs X \) позитивний рецидив, то існує унікальна інваріантна функція щільності ймовірності\( f: S \to (0, 1) \), і знову ж таки, або\( \bs X \) оборотна, або ні. Якщо\( \bs X \) оборотна, то\( P \) це матриця переходу\( \bs X \) вперед або назад в часі, коли ланцюг має інваріантний розподіл.
3. Якщо\( \bs X \) є перехідним, можуть існувати або не існувати позитивні інваріантні функції. Якщо є дві або більше позитивних інваріантних функцій, які не множаться один на одного,\( \bs X \) можуть бути оборотними щодо однієї функції, але не інших.

Несиметрична проста випадкова прогулянка по\( \Z \) потрапляє в останній випадок. Використовуючи останній результат у попередньому підрозділі, ми можемо визначити, чи\( \bs X \) є оборотним щодо,\( g \) не знаючи а-апріорі, що\( g \) є інваріантним.

Припустимо ще раз,\( \bs X \) що незведена з матрицею переходу\( P \). Якщо існує\( g: S \to (0, \infty) \) така функція, що\( g(x) P(x, y) = g(y) P(y, x) \) для всіх\( (x, y) \in S^2 \), то

1. \( g \)є інваріантним для\( \bs X \).
2. \( \bs X \)є оборотним щодо\( g \)

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

Припустимо ще раз, що\( \bs X \) є незвідним і що\( g: S \to (0, \infty) \). Тоді\( g \) є інваріантним і\( \bs X \) є оборотним щодо\( g \) якщо і тільки якщо для кожної\( n \in \N_+ \) послідовності станів\( (x_1, x_2, \ldots x_n, x_{n+1}) \in S^{n+1} \),\[ g(x_1) P(x_1, x_2) P(x_2, x_3) \cdots P(x_n, x_{n+1}) = g(x_{n+1}) P(x_{n+1}, x_n), \cdots P(x_3, x_2) P(x_2, x_1) \]

Припустимо ще раз, що\( \bs X \) є незвідним і що\( g: S \to (0, \infty) \). Тоді\( g \) є інваріантним і\( \bs X \) є оборотним щодо\( g \) якщо і тільки якщо для кожного\( (x, y) \in S^2 \) і\( n \in \N_+ \),\[ g(x) P^n(x, y) = g(y) P^n(y, x) \]

Ось умова оборотності з точки зору потенційних матриць.

Припустимо ще раз, що\( \bs X \) є незвідним і що\( g: S \to (0, \infty) \). Тоді\( g \) є інваріантним і\( \bs X \) є оборотним щодо\( g \) якщо і тільки якщо\[ g(x) R_\alpha(x, y) = g(y) R_\alpha(y, x), \quad \alpha \in (0, 1], \, (x, y) \in S^2 \]

У додатному рекуррентному випадку (найважливіший випадок) наступна теорема дає умову оборотності, яка безпосередньо не посилається на інваріантний розподіл. Стан відомий як умова циклу Колмогорова, і названий на честь Андрія Колмогорова

Припустимо, що\( \bs X \) є нескоротним і позитивним рецидивом. Тоді\( \bs X \) є оборотним, якщо і тільки якщо для кожної послідовності станів\( (x_1, x_2, \ldots, x_n) \),\[ P(x_1, x_2) P(x_2, x_3) \cdots P(x_{n-1}, x_n) P(x_n, x_1) = P(x_1, x_n) P(x_n, x_{n-1}) \cdots P(x_3, x_2) P(x_2, x_1) \]

Доказ

Припустимо, що\( \bs X \) є оборотним. Застосування результату ланцюга вище до послідовності\( (x_1, x_2, \ldots, x_n, x_1) \) дає умову циклу Колмогорова. І навпаки, припустимо, що умова циклу Колмогорова тримає, і давайте\( f \) позначимо інваріантну функцію щільності ймовірності\( \bs X \). З умови циклу ми маємо\( P(x, y) P^k(y, x) = P(y, x)P^k(x, y) \) для кожного\( (x, y) \in S \) і\( k \in \N_+ \). Усереднення\( k \) від 1 до\( n \) дає\[ P(x, y) \frac{1}{n} \sum_{k=1}^n P^k(y, x) = P(y, x) \frac{1}{n} \sum_{k = 1}^n P^k(x, y), \quad (x, y) \in S^2, \; n \in \N_+ \] Letting\( n \to \infty \) дає\(f(x) P(x, y) = f(y) P(y, x) \) для\( (x, y) \in S^2 \), так\( \bs X \) є оборотним.

Відзначимо, що умова циклу Колмогорова говорить про те, що ймовірність відвідування\( (x_2, x_3, \ldots, x_n, x_1) \) станів\( x_1 \) послідовно, починаючи в стані, така ж, як ймовірність відвідування\( (x_n, x_{n-1}, \ldots, x_2, x_1) \) станів послідовно, починаючи з стану\( x_1 \). Умова циклу також відома як рівняння балансу для циклів.

Малюнок\(\PageIndex{1}\): Умова циклу Колмогорова

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

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

Згадаймо загальну двостанову ланцюжок\( \bs X \) на\( S = \{0, 1\} \) з матрицею ймовірностей переходу\( p, \, q \in (0, 1) \),\[ P = \left[ \begin{matrix} 1 - p & p \\ q & 1 - q \end{matrix} \right] \] де знаходяться параметри. Ланцюг\( \bs X \) є оборотним і інваріантною функцією щільності ймовірності є\( f = \left( \frac{q}{p + q}, \frac{p}{p + q} \right) \).

Доказ

Все, що нам потрібно зробити, це зазначити, що\[\left[\begin{matrix} q & p \end{matrix}\right] \left[ \begin{matrix} 1 - p & p \\ q & 1 - q \end{matrix} \right] = \left[\begin{matrix} q & p \end{matrix}\right]\]

Припустимо, що\( \bs X \) це ланцюг Маркова на скінченному просторі стану\( S \) з симетричною матрицею ймовірностей переходу\( P \). Таким чином\( P(x, y) = P(y, x) \) для всіх\( (x, y) \in S^2 \). Ланцюг\( \bs X \) оборотний і що рівномірний розподіл на\( S \) є інваріантним.

Доказ

Все, що нам потрібно зробити, це відзначити,\( \bs{1} \) що\( \bs{1}(x) P(x, y) = \bs{1}(y) P(y, x) \) де постійна функція 1 на\( S \).

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

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

1. Намалюйте графік стану\( \bs X \) і зверніть увагу на те, що ланцюжок є незведеним.
2. Знайдіть інваріантну функцію щільності ймовірності\( f \).
3. Знайдіть середній час повернення до кожного стану.
4. Знайти матрицю ймовірності переходу\( \hat P \) ланцюга, що обертається часом\( \hat{\bs X} \).
5. Намалюйте графік стану\( \hat{\bs X} \).

Відповідь

1. Граф стану\( \bs X \)

   

2. \( f = \left( \frac{6}{17}, \frac{6}{17}, \frac{5}{17}\right) \)
3. \( \mu = \left( \frac{17}{6}, \frac{17}{6}, \frac{17}{5} \right) \)
4. \( \hat P = \left[ \begin{matrix} \frac{1}{4} & \frac{1}{3} & \frac{5}{12} \\ \frac{1}{4} & \frac{1}{3} & \frac{5}{12} \\ \frac{3}{5} & \frac{2}{5} & 0 \end{matrix} \right] \)

5. Граф стану\( \hat{\bs X} \)

   

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

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

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

Прочитайте обговорення оборотності для випадкових прогулянок на графіках.

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

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