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

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

Стан у дискретному ланцюжку Маркова є періодичним, якщо ланцюг може повернутися до стану тільки при кратних деякому цілому числу більше 1. Періодична поведінка ускладнює вивчення граничного поведінки ланцюга. Як ми побачимо в цьому розділі, ми можемо усунути періодичну поведінку, розглянувши ланцюжок\( d \) -step, де\( d \in \N_+ \) знаходиться період, але тільки за рахунок введення додаткових класів еквівалентності. Таким чином, в певному сенсі ми можемо торгувати однією формою складності на іншу.

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

Визначення та основні результати

Як завжди, нашою відправною точкою є (однорідна за часом) марковський ланцюг дискретного часу\( \bs{X} = (X_0, X_1, X_2, \ldots) \) з (зліченним) простором стану\( S \) та матрицею ймовірностей переходу\( P \).

Період стану\( x \in S \) є\[ d(x) = \gcd\{n \in \N_+: P^n(x, x) \gt 0 \} \] державою\( x \) є аперіодичним якщо\( d(x) = 1 \) і періодичним якщо\( d(x) \gt 1 \).

Таким чином, починаючи з\( x \), ланцюжок може повернутися до\( x \) тільки на кратні періоду\( d \), і\( d \) є найбільшим таким цілим числом. Мабуть, найважливішим результатом є те, що період, як повторення та швидкоплинність, є властивістю класу, що розділяється всіма станами в класі еквівалентності під співвідношенням до та від.

Якщо\( x \leftrightarrow y \) тоді\( d(x) = d(y) \).

Доказ

Припустимо, що\( x \leftrightarrow y \). Результат тривіальний\( x = y \), якщо, так що давайте припустимо, що\( x \neq y \). Нагадаємо, що існують\( j, \, k \in \N_+ \) такі, що\( P^j(x, y) \gt 0 \) і\( P^k(y, x) \gt 0 \). Але потім\( P^{j+k}(x, x) \ge P^j(x, y) P^k(y, x) \gt 0 \) і звідси\( d(x) \mid (j + k) \). Припустимо, тепер, що\( n \) є додатним цілим числом з\( P^n(y, y) \gt 0 \). Потім\( P^{j+k+n}(x, x) \ge P^j(x, y) P^n(y, y) P^k(y, x) \gt 0 \) і звідси\( d(x) \mid (j + k + n) \). З цього випливає\( d(x) \mid n \). З визначення періоду,\( d(y) \mid d(x) \). Змінюючи ролі,\( x \) і\( y \) ми також маємо\( d(x) \mid d(y) \). Звідси\( d(x) = d(y) \).

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

Припустимо, що\( x \in S \). Якщо\( P(x, x) \gt 0 \) тоді\( x \) (а отже, і клас еквівалентності\( x \)) є аперіодичним.

Доказ

За припущенням,\( 1 \in \{n \in \N_+: P^n(x, x) \gt 0\} \) а значить, найбільшим спільним дільником цієї множини є 1.

Зворотне, звичайно, не відповідає дійсності. Простий контрприклад наведено нижче.

Циклічні класи

Припустимо, що тепер\( \bs{X} = (X_0, X_1, X_2, \ldots) \) це не зводиться і є періодичним з періодом\( d \). Немає реальної втрати в загальності в припущенні, що ланцюг є нескорочуваним, бо якби це не так, ми могли б просто обмежити нашу увагу одним з класів нескорочуваної еквівалентності. Наша експозиція буде простіше і чистіше, якщо згадати співвідношення еквівалентності конгруентності по модулю\( d \) на\( \Z \), яке, в свою чергу, засноване на частковому порядку ділення. Для\( n, \, m \in \Z \),\( n \equiv_d m \) якщо і тільки якщо\( d \mid (n - m) \), еквівалентно\( n - m \) є цілим числом кратним\( d \), еквівалентно\( m \) і\( n \) мають однаковий залишок після ділення на\( d \). Основний факт, який нам знадобиться - це те, що\( \equiv_d \) зберігається під сумами і різницями. Тобто якщо\( m, \, n, \, p, \, q \in \Z \) і якщо\( m \equiv_d n \) і\( p \equiv_d q \), то\( m + p \equiv_d n + q \) і\( m - p \equiv_d n - q \).

Тепер, ми фіксуємо еталонний стан\( u \in S \)\( k \in \{0, 1, \ldots, d - 1\} \), і для, визначити\[ A_k = \{x \in S: P^{n d + k}(u, x) \gt 0 \text{ for some } n \in \N\} \] Тобто,\( x \in A_k \) якщо і тільки якщо існує\( m \in \N \) з\( m \equiv_d k \) і\( P^m(u, x) \gt 0 \).

Припустимо, що\( x, \, y \in S \).

1. Якщо\( x \in A_j \) і\( y \in A_k \) для\( j, \, k \in \{0, 1, \ldots, d - 1\} \) того\( P^n(x, y) \gt 0 \) для деяких\( n \equiv_d k - j \)
2. І навпаки, якщо\( P^n(x, y) \gt 0 \) для деяких\( n \in \N \), то існує\( j, \, k \in \{0, 1, \ldots d - 1\} \) таке\( x \in A_j \), що,\( y \in A_k \) і\( n \equiv_d k - j \).
3. \( (A_0, A_1, \ldots, A_{k-1}) \)Розділ наборів\( S \).

Доказ

Припустимо спочатку, що\( x \in A_k \). За визначенням,\( u \) призводить до\( x \)\( m \) кроків для деяких\( m \equiv_d k \). Так як ланцюг нескоротна,\( x \) веде назад\( u \), скажімо\( p \) по кроках. Звідси випливає, що\( u \) веде назад\( m + p \) по\( u \) кроках. Але оскільки\( u \) має період\( d \), ми повинні мати\( m + p \equiv_d 0\) і, отже,\( p \equiv_d -k \).

Далі припустимо, що\( x \in A_j \) і\( y \in A_k \). Ми знаємо, що\( u \) призводить до\( x \)\( m \) кроків для деяких\( m \equiv_d j \), і тепер ми знаємо, що\( y \) призводить до\( u \)\( p \) кроків для деяких\( p \equiv_d -k \). Так як ланцюг нескоротна,\( x \) призводить\( y \), скажімо\( n \) по кроках. Звідси випливає, що\( u \) веде назад\( m + n + p \) по\( u \) кроках. Знову ж таки, оскільки\( u \) має період\( d \),\( m + n + p \equiv_d 0 \) і з цього випливає, що\( n \equiv_d k - j \)

Далі зауважте, що оскільки ланцюг є нескорочуваним, а оскільки\(\{0, 1, \ldots, d - 1\}\) є набором усіх залишків по модулю\( d \), ми повинні мати\( \bigcup_{i=0}^{d-1} A_i = S \). Припустимо, що\( x, y \in S \) і\( P^n(x, y) \gt 0 \) для деяких\( n \in \N \). Потім\( x \in A_j \) і\( y \in A_k \) для деяких\(j, \, k \in \{0, 1, \ldots\}\). За тим же аргументом, що і останній абзац, ми повинні мати\( n \equiv_d k - j \).

Залишається лише показати, що набори є неспільними, і це знову дорівнює тому ж старому аргументу. Припустимо, що\( x \in A_j \cap A_k \) для деяких\( j, \, k \in \{0, 1, \ldots, d - 1\} \). Потім\( u \) призводить до\( x \)\( m \) кроків для деяких\( m \equiv_d j \) і\( x \) призводить до\( u \)\( n \) кроків для деяких\( n \equiv_d - k \). Звідси\( u \) призводить до\( u \)\( m + n \) кроків. Оскільки ланцюг має період,\( d \) який ми маємо\( m + n \equiv_d 0 \) і тому\( j - k \equiv_d 0 \). З\( j, \, k \in \{0, 1, \ldots, d - 1\} \) цього випливає\( j = k \).

\( (A_0, A_1, \ldots, A_{d-1}) \)класи еквівалентності для\( d \) -step до та від відношення\( \underset{d}{\leftrightarrow} \), що керує\( d \) ланцюгом -step\( (X_0, X_d, X_{2 d}, \ldots) \), що має матрицю переходу\( P^d \).

\( (A_0, A_1, \ldots, A_{d-1}) \)Множини відомі як циклічні класи. Основна структура ланцюга показана на діаграмі стану нижче:

Малюнок\(\PageIndex{1}\): Циклічні класи ланцюга з періодом\( d \)

Приклади та особливі випадки

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

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

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

1. Намалюйте графік стану і покажіть, що ланцюг незведена.
2. Покажіть, що ланцюжок аперіодична.
3. Зверніть увагу, що\( P(x, x) = 0 \) для всіх\( x \in S \).

Відповідь

1. Граф стану має набір ребер\( E = \{(a, b), (a, c), (b, c), (b, a)\} \).
2. Зверніть увагу, що\( P^2(a, a) \gt 0 \) і\( P^3(a, a) \gt 0 \). Отже,\( d(a) = 1 \) оскільки 2 і 3 є відносно простими. Так як ланцюг нескоротна, вона носить аперіодичний характер.

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

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

1. Намалюйте графік стану і покажіть, що ланцюг незведена.
2. Знайдіть період\( d \).
3. Знайти\( P^d \).
4. Визначте циклічні класи.

Відповідь

1. Граф стану

   

2. Період 3
3. \( P^3 = \left[ \begin{matrix} \frac{71}{192} & \frac{121}{192} & 0 & 0 & 0 & 0 & 0 \\ \frac{29}{72} & \frac{43}{72} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{7}{18} & \frac{1}{12} & \frac{19}{36} & 0 & 0 \\ 0 & 0 & \frac{19}{48} & \frac{3}{32} & \frac{49}{96} & 0 & 0 \\ 0 & 0 & \frac{13}{32} & \frac{7}{64} & \frac{31}{64} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{157}{299} & \frac{131}{288} \\ 0 & 0 & 0 & 0 & 0 & \frac{37}{64} & \frac{27}{64} \end{matrix} \right] \)
4. Циклічні класи:\( \{1, 2\} \),\( \{3, 4, 5\} \),\( \{6, 7\} \)

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

Перегляньте визначення базової ланцюга Еренфест. Покажіть, що цей ланцюжок має період 2, і знайдіть циклічні класи.

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

Перегляньте визначення простої випадкової ходьби далі\( \Z^k \). Покажіть, що ланцюг є періодичним з періодом 2, і знайдіть циклічні класи.