16.6: Стаціонарні та граничні розподіли дискретно-часових ланцюгів

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

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

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

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

Вбудований процес поновлення

Нехай\( y \in S \) і\( n \in \N_+ \). Ми позначимо кількість відвідувань\( y \) протягом перших\( n \) позитивних одиниць часу\[ N_{y,n} = \sum_{i=1}^n \bs{1}(X_i = y) \] Зауважте, що\( N_{y,n} \to N_y \) як\( n \to \infty \), де\[ N_y = \sum_{i=1}^\infty \bs{1}(X_i = y) \] загальна кількість відвідувань в позитивні\( y \) моменти, одна з важливих випадкових величин, яку ми вивчали в розділі про швидкоплинність і рецидиви. Бо\( n \in \N_+ \), позначаємо час\( n \) го візиту,\[ \tau_{y,n} = \min\{k \in \N_+: N_{y,k} = n\} \] куди, як зазвичай, визначаємо\( \min(\emptyset) = \infty \).\( y \) Зверніть увагу, що\( \tau_{y,1} \) це час першого відвідування\( y \), яке ми позначили просто\(\tau_y \) в розділі про швидкоплинність і повторення. Часи відвідувань\( y \) зупиняють час для\( \bs{X} \). Тобто,\( \{\tau_{y,n} = k\} \in \mathscr{F}_k \) для\( n \in \N_+ \) і\( k \in \N \). Нагадаємо також визначення ймовірності удару до стану,\( y \) починаючи в стані\( x \):\[ H(x, y) = \P\left(\tau_y \lt \infty \mid X_0 = x\right), \quad (x, y) \in S^2 \]

Припустимо\( x, \, y \in S \), що, і що\( y \) повторюється і\( X_0 = x \).

1. Якщо\( x = y \), то послідовні візити\( y \) формують процес поновлення.
2. Якщо\( x \ne y \) але\( x \to y \), то послідовні візити\( y \) формують процес відкладеного поновлення.

Доказ

Нехай\( \tau_{y,0} = 0 \) для зручності.

1. Враховуючи\( X_0 = y \), послідовність\( \left(\tau_{y,1}, \tau_{y,2}, \ldots\right) \) - це послідовність часу прибуття процесу оновлення. Кожен раз, коли ланцюг досягає стану\( y \), процес починається спочатку, незалежно від минулого, властивістю Маркова. Таким чином, час міжприбуття\( \tau_{y,n+1} - \tau_{y,n} \) для\( n \in \N \) умовно незалежні, і однаково розподілені, наведено\( X_0 = y \).
2. Якщо\( x \to y \),\( x \ne y \) але, то дано\( X_0 = x \), послідовність\( \left(\tau_{y,1}, \tau_{y,2}, \ldots\right) \) - це послідовність часу прибуття відкладеного процесу поновлення. За тим же аргументом, що і в (а), час інтерприбуття\( \tau_{y,n+1} - \tau_{y,n} \) для умовно\( n \in \N \) незалежні, дані\( X_0 = x \), і всі, але\( \tau_{y,1} \) мають однаковий розподіл.

Як зазначається в доказі,\( \left(\tau_{y,1}, \tau_{y,2}, \ldots\right) \) є послідовністю часу прибуття і\( \left(N_{y,1}, N_{y,2}, \ldots\right) \) є пов'язаною послідовністю підрахунку змінних для вбудованого процесу оновлення, пов'язаного з рекурентним станом\( y \). Відповідна функція оновлення, задана\( X_0 = x \), є функцією,\( n \mapsto G_n(x, y) \) де\[ G_n(x, y) = \E\left(N_{y,n} \mid X_0 = x\right) = \sum_{k=1}^n P^k(x, y), \quad n \in \N \] Таким чином\( G_n(x, y) \), очікувана кількість відвідувань\( y \) в перші\( n \) позитивні одиниці часу, починаючи з стану\( x \). Зверніть увагу, що\( G_n(x, y) \to G(x, y) \) як\( n \to \infty \) де\( G \) знаходиться матриця потенціалу, яку ми вивчали раніше. Ця матриця дає очікувану загальну кількість відвідувань держави\( y \in S \), в позитивні моменти, починаючи з стану\( x \in S \):\[ G(x, y) = \E\left(N_y \mid X_0 = x\right) = \sum_{k=1}^\infty P^k(x, y) \]

Обмеження поведінки

Граничні теореми теорії оновлення тепер можуть бути використані для дослідження граничної поведінки ланцюга Маркова. Нехай\( \mu(y) = \E(\tau_y \mid X_0 = y) \) позначають середній час повернення до стану\( y \), починаючи з\( y \). У наступних результатах може бути так, що\( \mu(y) = \infty \) в цьому випадку ми інтерпретуємо\( 1 / \mu(y) \) як 0.

Якщо\( x, \, y \in S \) і\( y \) є рецидивуючим, то\[ \P\left( \frac{1}{n} N_{n,y} \to \frac{1}{\mu(y)} \text{ as } n \to \infty \biggm| X_0 = x \right) = H(x, y) \]

Доказ

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

Відзначимо, що\( \frac{1}{n} N_{y,n} = \frac{1}{n} \sum_{k=1}^n \bs{1}(X_k = y) \) це середня кількість відвідувань\( y \) в перші\( n \) позитивні одиниці часу.

Якщо\( x, \, y \in S \) і\( y \) є рецидивуючим, то\[ \frac{1}{n} G_n(x, y) = \frac{1}{n} \sum_{k=1}^n P^k(x, y) \to \frac{H(x, y)}{\mu(y)} \text{ as } n \to \infty \]

Доказ

Цей результат випливає з елементарної теореми відновлення процесів відновлення.

Зверніть увагу, що\( \frac{1}{n} G_n(x, y) = \frac{1}{n} \sum_{k=1}^n P^k(x, y) \) це очікувана середня кількість відвідувань\( y \) протягом першого\( n \) позитивного часу одиниць, починаючи з\( x \).

Якщо\( x, \, y \in S \) і\( y \) є рецидивуючим і аперіодичним, то\[ P^n(x, y) \to \frac{H(x, y)}{\mu(y)} \text{ as } n \to \infty \]

Доказ

Цей результат випливає з теореми відновлення процесів оновлення.

Відзначимо, що\( H(y, y) = 1 \) за самим визначенням рецидивуючого стану. Таким чином\( x = y \), коли, закон великих чисел вище дає збіжність з ймовірністю 1, а перша і друга теорія оновлення межі вище просто\( 1 / \mu(y) \). На відміну від цього, ми вже знаємо відповідну обмежуючу поведінку\( y \), коли є тимчасовою.

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

1. \( \P\left(\frac{1}{n} N_{y,n} \to 0 \text{ as } n \to \infty \mid X_0 = x\right) = 1 \)
2. \( \frac{1}{n} G_n(x, y) = \frac{1}{n} \sum_{k=1}^n P^k(x, y) \to 0 \text{ as } n \to \infty \)
3. \( P^n(x, y) \to 0 \)як\( n \to \infty \)

Доказ

1. Зверніть увагу, що\(0 \le \frac{1}{n} N_{y,n} \le \frac{1}{n} N_y\). Але\( y \) це перехідний,\( \P(N_y \lt \infty \mid X_0 = x) = 1 \) і,\( \P\left(\frac{1}{n} N_y \to 0 \text{ as } n \to \infty \mid X_0 = x\right) = 1 \) отже, результат випливає з теореми стискання для меж.
2. Аналогічно, зверніть увагу, що\[0 \le \frac{1}{n} \sum_{k=1}^n P^k(x, y) \le \frac{1}{n} \sum_{k=1}^\infty P^k(x, y)\]\( y \) If є тимчасовим,\( G(x, y) = \sum_{k=1}^\infty P^k(x, y) \lt \infty \) а отже і\( \frac{1}{n} G(x, y) \to 0 \) як\( n \to \infty \). Знову результат випливає з теореми стискання для меж.
3. Ще раз, якщо\( y \) є тимчасовим,\( G(x, y) = \sum_{k=1}^\infty P^k(x, y) \lt \infty \) а отже,\( P^n(x, y) \to 0 \) як\( n \to \infty \).

З іншого боку, якщо\( y \) є тимчасовим, то\( \P(\tau_y = \infty \mid X_0 = y) \gt 0 \) за самим визначенням швидкоплинності. Таким чином\( \mu(y) = \infty \), і так результати в частинях (b) і (c) погоджуються з відповідними результатами вище для рецидивуючого стану. Ось короткий зміст.

Для\( x, \, y \in S \),\[ \frac{1}{n} G_n(x, y) = \frac{1}{n} \sum_{k=1}^n P^k(x, y) \to \frac{H(x, y)}{\mu(y)} \text{ as } n \to \infty \] Якщо\( y \) є тимчасовим або якщо\( y \) є рецидивуючим і аперіодичним,\[ P^n(x, y) \to \frac{H(x, y)} {\mu(y)} \text{ as } n \to \infty \]

Позитивний і нульовий повторення

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

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

1. Стан\( x \) позитивний рецидивуючий, якщо\( \mu(x) \lt \infty \).
2. Якщо\( x \) є рецидивуючим, але\( \mu(x) = \infty \) тоді стан\( x \) є нульовим повторюваним.

Неявним у визначенні є наступний простий результат:

Якщо\( x \in S \) позитивний рецидивуючий,\( x \) то рецидивний.

Доказ

Нагадаємо, що якщо\( \E(\tau_x \mid X_0 = x) \lt \infty \) тоді\( \P(\tau_x \lt \infty \mid X_0 = x) = 1 \).

З іншого боку, можна мати, так що рецидивує\( \P(\tau_x \lt \infty \mid X_0 = x) = 1 \), а також\( \E(\tau_x \mid X_0 = x) = \infty \), так що\( x \)\( x \) є нульовим рецидивом. Простіше кажучи, випадкова величина може бути кінцевою з ймовірністю 1, але може мати нескінченне очікуване значення. Класичним прикладом є розподіл Парето з параметром shape\( a \in (0, 1) \).

Подібно до повторення/транзиентності та періоду, властивість null/positive recurrence є властивістю класу.

Якщо\( x \) позитивний рецидивуючий, а\( x \to y \) потім\( y \) позитивний рецидивуючий.

Доказ

Припустимо,\( x \) що позитивний рецидивуючий і\( x \to y \). Нагадаємо, що\( y \) є рецидивними і\( y \to x \). Звідси існують\( i, \, j \in \N_+ \) такі, що\( P^i(x, y) \gt 0 \) і\( P^j(y, x) \gt 0 \). Таким чином для кожного\( k \in \N_+ \),\( P^{i+j+k}(y, y) \ge P^j(y, x) P^k(x, x) P^i(x, y) \). Усереднення понад\( k \) від 1 до\( n \) дає\[ \frac{G_n(y, y)}{n } - \frac{G_{i+j}(y, y)}{n} \ge P^j(y, x) \frac{G_n(x, x)}{n} P^i(x, y)\] Дозволити\( n \to \infty \) та використовувати межу теорії поновлення вище дає\[ \frac{1}{\mu(y)} \ge P^j(y, x) \frac{1}{\mu(x)} P^i(x, y) \gt 0 \] Тому\( \mu(y) \lt \infty \) і так\( y \) є також позитивним рецидивом.

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

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

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

Доказ

Виправте стан\( x \in A \) і зауважте, що\( P^k(x, A) = \sum_{y \in A} P^k(x, y) = 1 \) для кожного\( k \in \N_+ \) з тих пір\( A \) закрито. Усереднення більше\( k \) від 1 до\( n \) дає\[ \sum_{y \in A} \frac{G_n(x, y)}{n} = 1 \] для кожного\( n \in \N_+ \). Зауважимо, що зміна порядку підсумовування виправдано, оскільки обидві суми є кінцевими. Припустимо тепер, що всі стани в\( A \) перехідні або нульові повторювані. \( n \to \infty \)Впускання відображеного рівняння дає протиріччя\( 0 = 1 \). Знову ж таки, обмін суми і ліміту виправданий тим, що\( A \) є кінцевим.

Якщо\( A \subseteq S \) кінцевий і замкнутий, то не\( A \) містить нульових повторюваних станів.

Доказ

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

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

Доказ

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

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

Обмеження поведінки, переглянутий

Повертаючись до обмежуючої поведінки, припустимо, що ланцюг\( \bs{X} \) є нескорочуваним, так що або всі стани є перехідними, всі стани є нульовими рецидивними, або всі стани є позитивними рецидивними. З основної граничної теореми вище, якщо ланцюг перехідний або якщо ланцюг рекурентний і аперіодичний, то\[ P^n(x, y) \to \frac{1}{\mu(y)} \text{ as } n \to \infty \text{ for every } x \in S \] зверніть увагу, зокрема, що межа не залежить від початкового стану\( x \). Звичайно, в перехідному випадку і в нульовому рецидивному та аперіодичному випадку межа дорівнює 0. Тільки в позитивному рецидивуючому, аперіодичному випадку є гранично позитивним, що мотивує наше наступне визначення.

Марковський ланцюг\( \bs{X} \), який є незведеним, позитивним рецидивом та аперіодичним, як кажуть, є ергодичним.

У ергодичному випадку, як ми побачимо,\( X_n \) має обмежувальний розподіл, оскільки\( n \to \infty \) це не залежить від початкового розподілу.

Поведінка, коли ланцюг є періодичним з періодом\( d \in \{2, 3, \ldots\} \), трохи складніше, але ми можемо зрозуміти цю поведінку, розглянувши ланцюг\( d \) -step\( \bs{X}_d = (X_0, X_d, X_{2 d}, \ldots) \), який має матрицю переходу\( P^d \). По суті, це дозволяє нам торгувати періодичністю (одна форма складності) на скорочуваність (інша форма складності). Зокрема, нагадайте, що ланцюг\( d \) -step є аперіодичним, але має класи\( d \) еквівалентності\( (A_0, A_1, \ldots, A_{d-1}) \); і це циклічні класи оригінального ланцюга\( \bs{X} \).

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

Середній час повернення до стану\( x \) для ланцюга\( d \) -step\( \bs{X}_d \) дорівнює\( \mu_d(x) = \mu(x) / d \).

Доказ

Зверніть увагу, що кожен крок для ланцюга\( d \) -step відповідає\( d \) крокам для оригінальної ланцюга.

Нехай\( i, \, j, \, k \in \{0, 1, \ldots, d - 1\} \),

1. \( P^{n d + k}(x, y) \to d / \mu(y) \)\( n \to \infty \)ніби\( x \in A_i \) і\( y \in A_j \) і\( j = (i + k) \mod d \).
2. \( P^{n d + k}(x, y) \to 0 \)як\( n \to \infty \) і у всіх інших випадках.

Доказ

Ці результати випливають з попередньої теореми та циклічної поведінки ланцюга.

Якщо\( y \in S \) є нульовим рецидивуючим або перехідним, то незалежно від періоду\( y \),\( P^n(x, y) \to 0 \) як\( n \to \infty \) для кожного\( x \in S \).

Інваріантні дистрибутиви

Наша наступна мета - побачити, як обмежуюча поведінка пов'язана з інваріантними розподілами. Припустимо, що\( f \) це функція щільності ймовірності на просторі стану\( S \). Нагадаємо, що\( f \) є інваріантним для\( P \) (і для ланцюга\( \bs{X} \)) if\( f P = f \). З цього випливає відразу, що\( f P^n = f \) для кожного\( n \in \N \). Таким чином, якщо\( X_0 \) має функцію щільності ймовірності,\( f \) то\( \bs{X} \) це робить\( X_n \) для кожного\( n \in \N \), а отже, послідовність однаково розподілених випадкових величин. Трохи загалом, припустимо, що\( g: S \to [0, \infty) \) є інваріантним для\( P \), і нехай\( C = \sum_{x \in S} g(x) \). Якщо\( 0 \lt C \lt \infty \) потім\( f \) визначено\( f(x) = g(x) / C \) for,\( x \in S \) є інваріантною функцією щільності ймовірності.

Припустимо, що\( g: S \to [0, \infty) \) є інваріантним для\( P \) і задовольняє\( \sum_{x \in S} g(x) \lt \infty \). Тоді\[ g(y) = \frac{1}{\mu(y)} \sum_{x \in S} g(x) H(x, y), \quad y \in S \]

Доказ

Згадаймо ще раз, що\( g P^k = g \) для кожного\( k \in \N \) з тих пір\( g \) є інваріантним для\( P \). Усереднення більше\( k \) від 1 до\( n \) дає\( g G_ n / n = g \) для кожного\( n \in \N_+ \). Явно,\[ \sum_{x \in S} g(x) \frac{G_n(x, y)}{n} = g(y), \quad y \in S \] Дозволяючи\( n \to \infty \) і використовуючи граничну теорему вище дає результат. Домінуюча теорема збіжності виправдовує зміну межі з сумою, оскільки члени позитивні\( \frac{1}{n}G_n(x, y) \le 1 \), і\( \sum_{x \in S} g(x) \lt \infty \).

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

Припустимо тепер,\( \bs{X} \) що ланцюг незвідний. Якщо\( \bs{X} \) є перехідним або нульовим рекуррентом, то з попереднього результату єдиними невід'ємними функціями, які є інваріантними для,\( P \) є функції, які задовольняють,\( \sum_{x \in S} g(x) = \infty \) і функція, яка ідентично 0:\( g = \bs{0} \). Зокрема, ланцюг не має інваріантного розподілу. З іншого боку, якщо ланцюг позитивна рецидивна, то\( H(x, y) = 1 \) для всіх\( x, \, y \in S \). Таким чином, з попереднього результату єдиною можливою інваріантною функцією щільності ймовірності є функція,\( f \) задана\( f(x) = 1 / \mu(x) \) for\( x \in S \). Будь-яка інша невід'ємна функція,\( g \) яка є інваріантною для\( P \) і має кінцеву суму, кратна\( f \) (і справді кратна сума значень). Наша наступна мета - показати, що\( f \) насправді є інваріантною функцією щільності ймовірності.

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

Доказ

Нехай\( f(x) = 1 / \mu(x) \) для\( x \in S \), і нехай\( A \) буде кінцева підмножина\( S \). Тоді\( \sum_{y \in A} \frac{1}{n} G_n(x, y) \le 1 \) для кожного\( x \in S \). Дозволяючи\( n \to \infty \) використовувати базовий ліміт вище дає\( \sum_{y \in A} f(y) \le 1 \). Обмін ліміту та суми виправданий, оскільки\( A \) є кінцевим. Так як це вірно для кожного кінцевого\( A \subseteq S \), то випливає, що\( C \le 1 \) де\( C = \sum_{y \in S} f(y) \). Відзначимо також, що\( C \gt 0 \) оскільки ланцюг позитивний рецидивний. Далі зверніть увагу, що\[ \sum_{y \in A} \frac{1}{n} G_n(x, y) P(y, z) \le \frac{1}{n} G_{n+1}(x, z) \] для кожного\( x, \, z \in S \). Здача\( n \to \infty \) дає\( \sum_{y \in A} f(y) P(y, z) \le f(z) \) за кожного\( z \in S \). Потім випливає, що\( \sum_{y \in S} f(y) P(y, z) \le f(z) \) для кожного\( z \in S \). Припустимо, що сувора нерівність тримає для деяких\( z \in S \). Тоді\[ \sum_{z \in S} \sum_{y \in S} f(y) P(y, z) \lt \sum_{z \in S} f(z) \] взаємозміна порядку підсумовування ліворуч у відображеній нерівності дає протиріччя\( C \lt C \). Таким чином\( f \), є інваріантним для\( P \). Звідси\( f / C \) є інваріантна функція щільності ймовірності. За унікальності результату, зазначеним раніше, випливає, що\( f / C = f \) так насправді\( C = 1 \).

Підсумовуючи, незведена, позитивна рекурентна ланцюг Маркова\( \bs{X} \) має унікальну інваріантну функцію щільності ймовірності,\( f \) задану\( f(x) = 1 / \mu(x) \) for\( x \in S \). У нас також тепер є тест на позитивний рецидив. Незведена ланцюг\( \bs{X} \) Маркова позитивна рецидивна тоді і тільки тоді, коли існує позитивна функція\( g \) на\( S \) те, що є інваріантною для\( P \) і задовольняє\( \sum_{x \in S} g(x) \lt \infty \) (і тоді, звичайно, нормалізація\( g \) дала б\( f \)).

Розглянемо тепер загальну ланцюжок Маркова\( \bs{X} \) на\( S \). Якщо не\( \bs{X} \) має позитивних рецидивуючих станів, то, як зазначалося раніше, інваріантних розподілів немає. Таким чином, припустимо, що\( \bs{X} \) має колекцію позитивних рекурентних класів еквівалентності,\( (A_i: i \in I) \) де\( I \) є непорожнім, підрахунковим набором індексів. Ланцюг, обмежений до,\( A_i \) є незведеним і позитивним рекуррентом для кожного\( i \in I \), і, отже, має унікальну інваріантну функцію щільності ймовірності\( f_i \) на\( A_i \) задану\[ f_i(x) = \frac{1}{\mu(x)}, \quad x \in A_i \] We\( f_i \) поширюється на,\( S \) визначаючи\( f_i(x) = 0 \) для\( x \notin A_i \), так що\( f_i \) це функція щільності ймовірності на\( S \). Всі інваріантні функції щільності ймовірності для\( \bs{X} \) є сумішами цих функцій:

\( f \)є інваріантною функцією щільності ймовірності для\( \bs{X} \) if і тільки тоді, коли\( f \) має вигляд,\[ f(x) = \sum_{i \in I} p_i f_i(x), \quad x \in S \] де\( (p_i: i \in I) \) є функція щільності ймовірності на множині індексу\( I \). Тобто,\( f(x) = p_i f_i(x) \) для\( i \in I \) і\( x \in A_i \), і\( f(x) = 0 \) інакше.

Доказ

Нехай\( A = \bigcup_{i \in I} A_i \), сукупність позитивних рецидивуючих станів. Припустимо, що\( f \) має форму, наведену в теоремі. Оскільки\( f(x) = 0 \) для\( x \notin A \) нас є\[(f P)(y) = \sum_{x \in S} f(x) P(x, y) = \sum_{i \in I} \sum_{x \in A_i} p_i f_i(x) P(x, y)\] Припустимо, що\( y \in A_j \) для деяких\( j \in I \). Оскільки\( P(x, y) = 0 \) якщо\( x \in A_i \) і\( i \ne j \), остання сума стає\[(f P)(y) = p_j \sum_{x \in A_j} f_j(x) P(x, y) = p_j f_j(y) = f(y)\] тому, що\( f_j \) є інваріантною для\( P \) обмеженого до\( A_j \). Якщо\( y \notin A \) тоді\( P(x, y) = 0 \) для\( x \in A \) цього сума вище стає\( (f P)(y) = 0 = f(y) \). Звідси\( f \) є інваріантним. Крім того,\[\sum_{x \in S} f(x) = \sum_{i \in I} \sum_{x \in A_i} f(x) = \sum_{i \in I} p_i \sum_{x \in A_i} f_i(x) = \sum_{i \in I} p_i = 1\] так\( f \) це PDF на\( S \). І навпаки, припустимо, що\( f \) це інваріантний PDF для\( \bs{X} \). Ми знаємо, що\( f \) концентрується на позитивних рецидивних станах, тому\( f(x) = 0 \) для\( x \notin A\). Бо\( i \in I \) і\( y \in A_i \)\[\sum_{x \in A_i} f(x) P(x, y) = \sum_{x \in S} f(x) P(x, y) = f(y)\] так як\( f \) є інваріантним для\( P \) і з тих пір, як зазначалося раніше,\( f(x) P(x, y) = 0 \) якщо\( x \notin A_i \). Звідси випливає, що\( f \) обмежений до\( A_i \) є інваріантним для ланцюга, обмеженим\( A_i \) для кожного\( i \in I \). Нехай\( p_i = \sum_{x \in A_i} f(x) \), нормалізує константа для\( f \) обмеженого до\( A_i \). За єдиністю обмеження\( f / p_i \) to\( A_i \) повинно бути\( f_i \), так\( f \) має форму, наведену в теоремі.

інваріантні заходи

Припустимо, що\( \bs{X} \) це незвідне. У цьому розділі нас цікавлять загальні функції\( g: S \to [0, \infty) \), які є інваріантними для\( \bs{X} \), так що\( g P = g \). Функція\( g: S \to [0, \infty) \) визначає\( \nu \) позитивну міру\( S \) за простим правилом,\[ \nu(A) = \sum_{x \in A} g(x), \quad A \subseteq S \] тому в цьому сенсі ми зацікавлені в інваріантних позитивних заходах, оскільки\( \bs{X} \) це не може бути мірами ймовірності. Технічно,\( g \) це функція щільності\( \nu \) щодо вимірювання підрахунку\( \# \) на\( S \).

З нашої роботи вище, Ми знаємо ситуацію, якщо\( \bs{X} \) позитивно повторюється. У цьому випадку існує унікальна інваріантна функція щільності ймовірності,\( f \) яка є додатною\( S \), а будь-яка інша невід'ємна інваріантна функція\( g \) є невід'ємною кратною\( f \). Зокрема\( g = \bs{0} \), або нульова функція\( S \) включена, або\( g \) позитивна\( S \) і задовольняє\( \sum_{x \in S} g(x) \lt \infty \).

Ми можемо узагальнити до ланцюжків, які є просто повторюваними, або нульовими або позитивними. Ми покажемо, що існує додатна інваріантна функція, яка є унікальною, аж до множення на позитивні константи. Щоб налаштувати позначення, нагадайте, що\( \tau_x = \min\{k \in \N_+: X_k = x\} \) це перший позитивний момент, коли ланцюг знаходиться в стані\( x \in S \). Зокрема, якщо ланцюг починається,\( x \) то\( \tau_x \) це час першого повернення до\( x \). Для\( x \in S \) ми визначаємо функцію\( \gamma_x \)\[ \gamma_x(y) = \E\left(\sum_{n=0}^{\tau_x - 1} \bs{1}(X_n = y) \biggm| X_0 = x\right), \quad y \in S \] таким чином, що\( \gamma_x(y) \) очікувана кількість відвідувань\( y \) перед першим поверненням до\( x \), починаючи з\( x \). Ось результат існування.

Припустимо, що\( \bs X \) це рецидивний. Для\( x \in S \),

1. \( \gamma_x(x) = 1 \)
2. \( \gamma_x \)є інваріантним для\( \bs X \)
3. \( \gamma_x(y) \in (0, \infty) \)для\( y \in S \).

Доказ

1. За визначенням,\( X_0 = x \) наведеним, у нас є\( X_0 = x \) але\( X_n \ne x \) для\( n \in \{1, \ldots, \tau_x - 1\} \). Звідси\( \gamma_x(x) = 1 \).
2. Так як ланцюг рецидивна, з ймовірністю 1 ми маємо\( \tau_x \lt \infty \) і\( X_{\tau_x} = x \). Звідси для\( y \in S \),\[ \gamma_x(y) = \E\left(\sum_{n=0}^{\tau_x - 1} \bs{1}(X_n = y) \biggm| X_0 = x\right) = \E\left(\sum_{n=1}^{\tau_x} \bs{1}(X_n = y) \biggm| X_0 = x\right) \] (Зверніть увагу, що якщо\( x = y \) тоді з ймовірністю 1,\( n = 0 \) термін у першій сумі та\( n = \tau_x \) термін у другій сумі дорівнюють 1, а решта - 0. Якщо\( x \ne y \)\( n = 0 \) термін у першій сумі та член у\( n = \tau_x \) другій сумі дорівнюють 0 з ймовірністю 1, тому знову дві суми однакові.) Звідси\[ \gamma_x(y) = \E\left(\sum_{n=1}^\infty \bs{1}(X_n = y, \tau_x \ge n) \biggm| X_0 = x\right) = \sum_{n=1}^\infty \P(X_n = y, \tau_x \ge n \mid X_0 = x) \] Далі ми розділимо на значення\( X_{n-1} \) в сумі, щоб отримати\ begin {align*}\ gamma_x (y) & =\ sum_ {n=1} ^\ infty\ sum_ {z\ in S}\ P (x_n = y, X_ {n-1} = z,\ tau_x\ ge n\ середина X_0 = x)\\ & =\ sum_ {n=1}} ^\ infty\ sum_ {z\ in S}\ P (x_n = у\ середина X_ {n-1} = z,\ tau_x\ ge n, X_0 = х)\ P (X_ {n-1} = z,\ tau_x\ ge n\ mid X_0 = x)\ end {align*} Але\( \{X_0 = x, \tau_x \ge n\} \in \mathscr{F}_{n-1} \) (тобто події залежать тільки від\( (X_0, \ldots, X_{n-1})) \). Отже, за властивістю Маркова перший множник в останньому відображеному рівнянні просто\( \P(X_n = y \mid X_{n-1} = z) = P(z, y) \). Підстановка та повторна індексація суми дає\ begin {align*}\ gamma_x (y) & =\ sum_ {n=1} ^\ infty\ sum_ {z\ in S} P (z, y)\ P (X_ {n-1} = z,\ tau_x\ ge n\ середина X_0 = x) =\ sum_ {z\ in S} P (z, y))\ E\ ліворуч (\ sum_ {n=1} ^ {\ tau_x}\ bs {1} (X_ {n-1} = z)\ bigm| X_0 = х\ праворуч)\\ & =\ sum_ {z\ in S} P (z, y)\ Е\ ліво (\ сума {m = 0} ^ {\\ tau_x - 1}\ bs {1} (x_m = z)\ бігм| X_0 = х\ вправо) =\ sum_ {z\ in S} P (z, y)\ gamma_x (z) =\ gamma_x P (y)\ кінець {align*}
3. За інваріантності в частині (b),\( \gamma_x = \gamma_x P^n \) для кожного\( n \in \N \). Нехай\(y \in S \). Так як ланцюг нескоротна, існує\( j \in \N \) таке, що\( P^j(x, y) \gt 0 \). Отже,\[ \gamma_x(y) = \gamma_x P^j(y) \ge \gamma_x(x) P^j(x, y) = P^j(x, y) \gt 0 \ \] подібним чином існує\( k \in \N \) таке, що\( P^k(y, x) \gt 0 \). Звідси\[ 1 = \gamma_x(x) = \gamma_xP^k(x) \ge \gamma_x(y) P^k(y, x) \] і тому\( \gamma_x(y) \le 1 / P^k(y, x) \lt \infty \).

Далі йде результат унікальності.

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

Доказ

Нехай\( S_x = S - \{x\} \) і нехай\( y \in S \). Оскільки\( g \) є інваріантним,\[ g(y) = g P(y) = \sum_{z \in S} g(z) P(z, y) = \sum_{z \in S_x} g(z) P(z, y) + g(x) P(x, y) \] зверніть увагу, що останній термін є\( g(x) \P(X_1 = y, \tau_x \ge 1 \mid X_0 = x) \). Повторення аргументу для\( g(z) \) в сумі вище дає\[ g(y) = \sum_{z \in S_x} \sum_{w \in S_x} g(w) P(w, z)P(z, y) + g(x) \sum_{z \in S_x} P(x, z) P(z, y) + g(x) P(x, y) \] Останні два члени\[ g(x) \left[\P(X_2 = y, \tau_x \ge 2 \mid X_0 = x) + \P(X_1 = y, \tau_x \ge 1 \mid X_0 = x)\right] \] Продовжуючи таким чином показує, що для кожного\( n \in \N_+ \),\[ g(y) \ge g(x) \sum_{k=1}^n \P(X_k = y, \tau_x \ge k \mid X_0 = x) \] Дозволяючи\( n \to \infty \) потім показує, що\( g(y) \ge g(x) \gamma_x(y) \). Далі зауважте, що функція\(h = g - g(x) \gamma_x \) є інваріантною, оскільки вона є різницею двох інваріантних функцій, і, як тільки що було показано, є невід'ємною. Також,\( h(x) = g(x) - g(x) \gamma_x(x) = 0 \). Нехай\( y \in S \). Так як ланцюг нескоротна, існує\( j \in \N \) таке, що\( P^j(y, x) \gt 0 \). Звідси\[ 0 = h(x) = hP^j(x) \ge h(y) P^j(y, x) \ge 0 \] З\( P^j(y, x) \gt 0 \) цього випливає, що\( h(y) = 0 \).

Таким чином, припустимо, що\( \bs{X} \) це нульовий повторюваний. Тоді існує інваріантна функція\( g \), яка є позитивною\( S \) і задовольняє\( \sum_{x \in S} g(x) = \infty \). Кожна інша невід'ємна інваріантна функція є невід'ємною кратною\( g \). Зокрема\( g = \bs{0} \), або нульова функція\( S \) включена, або\( g \) позитивна\( S \) і задовольняє\( \sum_{x \in S} g(x) = \infty \). У розділі про ланцюги надійності наведено приклад інваріантної функції для нульового рекурентного ланцюга.

Ситуація ускладнюється\( \bs{X} \), коли є тимчасовою. У цьому випадку можуть існувати або не існувати невід'ємні інваріантні функції, які не однаково 0. Коли вони існують, вони можуть бути не унікальними (аж до множення на невід'ємні константи). Але ми все ще знаємо, що немає інваріантних функцій щільності ймовірності, так що якщо\( g \) це невід'ємна функція, яка є інваріантною для\( \bs{X} \) то або\( g = \bs{0} \) або\( \sum_{x \in S} g(x) = \infty \). У розділі про випадкові прогулянки на графах наведено безліч прикладів перехідних ланцюгів з нетривіальними інваріантними функціями. Зокрема, несиметрична випадкова прогулянка по\( \Z \) має двовимірний простір інваріантних функцій.

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

Кінцеві ланцюги

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

1. Знайдіть інваріантний розподіл.
2. Знайдіть середній час повернення до кожного стану.
3. Знайдіть\( \lim_{n \to \infty} P^n \) без необхідності йти до проблеми діагоналізації\( P \), як ми це робили у вступі до дискретних ланцюжків часу.

Відповідь

1. \( f = \left(\frac{q}{p + q}, \frac{p}{p + q} \right) \)
2. \( \mu = \left( \frac{p + q}{q}, \frac{p + q}{p} \right) \)
3. \( P^n \to \frac{1}{p + q} \left[ \begin{matrix} q & p \\ q & p \end{matrix} \right] \)як\( n \to \infty \).

Розглянемо ланцюжок Маркова з простором стану\( S = \{a, b, c, d\} \) та матрицею переходу,\( P \) наведеною нижче:\[ P = \left[ \begin{matrix} \frac{1}{3} & \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. Знайти всі інваріантні функції щільності ймовірностей.
4. Знайдіть середній час повернення до кожного стану.
5. Знайти\( \lim_{n \to \infty} P^n \).

Відповідь

1. Граф стану

   

2. \( \{a, b\} \)рецидивний;\( \{c\} \) рецидивуючий;\( \{d\} \) минущий.
3. \( f = \left( \frac{3}{5} p, \frac{2}{5} p, 1 - p, 0 \right) \),\( 0 \le p \le 1 \)
4. \( \mu = \left(\frac{5}{3}, \frac{5}{2}, 1, \infty \right) \)
5. \( P^n \to \left[ \begin{matrix} \frac{3}{5} & \frac{2}{5} & 0 & 0 \\ \frac{3}{5} & \frac{2}{5} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \frac{2}{5} & \frac{4}{15} & \frac{1}{3} & 0 \end{matrix} \right] \)як\( n \to \infty \)

Розглянемо ланцюжок Маркова з простором стану\( 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. Знайти всі інваріантні функції щільності ймовірностей.
4. Знайдіть середній час повернення до кожного стану.
5. Знайти\( \lim_{n \to \infty} P^n \).

Відповідь

1. Граф стану

   

2. \( \{1, 3, 5\} \)рецидивний;\( \{2, 6\} \) минущий;\( \{4\} \) рецидивуючий.
3. \( f = \left(\frac{2}{19}p, 0, \frac{8}{19} p, 1 - p, \frac{9}{19}p, 0\right), \quad 0 \le p \le 1 \)
4. \( \mu = \left(\frac{19}{2}, \infty, \frac{19}{8}, 1, \frac{19}{8}, \infty\right) \)
5. \( P^n \to \left[ \begin{matrix} \frac{2}{19} & 0 & \frac{8}{19} & 0 & \frac{9}{19} & 0 \\ \frac{1}{19} & 0 & \frac{4}{19} & \frac{1}{2} & \frac{9}{38} & 0 \\ \frac{2}{19} & 0 & \frac{8}{19} & 0 & \frac{9}{19} & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ \frac{2}{19} & 0 & \frac{8}{19} & 0 & \frac{9}{19} & 0 \\ \frac{1}{19} & 0 & \frac{4}{19} & \frac{1}{2} & \frac{9}{38} & 0 \\ \end{matrix} \right] \)як\( n \to \infty \).

Розглянемо ланцюжок Маркова з простором стану\( 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. Знайти всі інваріантні функції щільності ймовірностей.
4. Знайдіть середній час повернення до кожного стану.
5. Знайти\( \lim_{n \to \infty} P^n \).

Відповідь

1. Граф стану

   

2. \( \{1, 2\} \)рецидивний;\( \{3, 4\} \) минущий;\( \{5, 6\} \) рецидивуючий.
3. \( f = \left(\frac{1}{3} p, \frac{2}{3} p, 0, 0, \frac{1}{2}(1 - p), \frac{1}{2}(1 - p) \right), \quad 0 \le p \le 1 \)
4. \( \mu = \left(3, \frac{3}{2}, \infty, \infty, 2, 2 \right) \)
5. \( P^n \to \left[ \begin{matrix} \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 & 0 \\ \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 & 0 \\ \frac{4}{15} & \frac{8}{15} & 0 & 0 & 0 & 0 \\ \frac{1}{5} & \frac{2}{5} & 0 & 0 & \frac{1}{5} & \frac{1}{5} \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{matrix} \right] \)як\( n \to \infty \)

Розглянемо ланцюжок Маркова з простором стану\( 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. Намалюйте диграф стану, і покажіть, що ланцюг не зводиться з періодом 3.
2. Визначте циклічні класи.
3. Знайдіть інваріантну функцію щільності ймовірності.
4. Знайдіть середній час повернення до кожного стану.
5. Знайти\( \lim_{n \to \infty} P^{3 n} \).
6. Знайти\( \lim_{n \to \infty} P^{3 n + 1} \).
7. Знайти\( \lim_{n \to \infty} P^{3 n + 2} \).

Відповідь

1. Граф стану

   

2. Циклічні класи:\( \{1, 2\} \),\( \{3, 4, 5\} \),\( \{6, 7\} \)
3. \( f = \frac{1}{1785}(232, 363, 237, 58, 300, 333, 262) \)
4. \( \mu = 1785 \left( \frac{1}{232}, \frac{1}{363}, \frac{1}{237}, \frac{1}{58}, \frac{1}{300} \frac{1}{333}, \frac{1}{262} \right) \)
5. \( P^{3 n} \to \frac{1}{585} \left[ \begin{matrix} 232 & 363 & 0 & 0 & 0 & 0 & 0 \\ 232 & 363 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 237 & 58 & 300 & 0 & 0 \\ 0 & 0 & 237 & 58 & 300 & 0 & 0 \\ 0 & 0 & 237 & 58 & 300 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 333 & 262 \\ 0 & 0 & 0 & 0 & 0 & 333 & 262 \\ \end{matrix} \right] \)як\( n \to \infty \)
6. \( P^{3 n + 1} \to \frac{1}{585} \left[ \begin{matrix} 0 & 0 & 237 & 58 & 300 & 0 & 0 \\ 0 & 0 & 237 & 58 & 300 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 333 & 262 \\ 0 & 0 & 0 & 0 & 0 & 333 & 262 \\ 0 & 0 & 0 & 0 & 0 & 333 & 262 \\ 232 & 363 & 0 & 0 & 0 & 0 & 0 \\ 232 & 363 & 0 & 0 & 0 & 0 & 0 \end{matrix} \right] \)як\( n \to \infty \)
7. \( P^{3 n + 2} \to \frac{1}{585} \left[ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 333 & 262 \\ 0 & 0 & 0 & 0 & 0 & 333 & 262 \\ 232 & 363 & 0 & 0 & 0 & 0 & 0 \\ 232 & 363 & 0 & 0 & 0 & 0 & 0 \\ 232 & 363 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 237 & 58 & 300 & 0 & 0 \\ 0 & 0 & 237 & 58 & 300 & 0 & 0 \end{matrix} \right] \)як\( n \to \infty \)

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

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

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

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

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

Прочитайте обговорення позитивних повторень і для ланцюжків черг.

Прочитайте обговорення позитивних повторювань та обмежувальних розподілів для випадкових прогулянок на графіках.