16.13: Ланцюги народження та смерті дискретного часу

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

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

Вступ

Припустимо, що\( S \) це інтервал цілих чисел (тобто набір послідовних цілих чисел), або скінченних, або нескінченних. A (дискретний час) ланцюг народження-смерть на\( S \) дискретно-часовому ланцюжку Маркова\( \bs{X} = (X_0, X_1, X_2, \ldots) \) на\( S \) з матрицею\( P \) ймовірностей переходу виду\[ P(x, x - 1) = q(x), \; P(x, x) = r(x), \; P(x, x + 1) = p(x); \quad x \in S \] де\( p \)\( q \), і\( r \) є невід'ємними функціями на\( S \) with\( p(x) + q(x) + r(x) = 1 \) for \( x \in S \).

Якщо інтервал\( S \) має мінімальне значення,\( a \in \Z \) то, звичайно, ми повинні мати\( q(a) = 0 \). Якщо\( r(a) = 1 \), гранична точка\( a \) поглинає і якщо\( p(a) = 1 \),\( a \) то відбиває. Аналогічно, якщо інтервал\( S \) має максимальне значення,\( b \in \Z \) то, звичайно, ми повинні мати\( p(b) = 0 \). Якщо\( r(b) = 1 \), гранична точка\( b \) поглинає і якщо\( p(b) = 1 \),\( b \) то відбиває. Кілька інших спеціальних моделей, які ми вивчили, - це ланцюги народження-смерть; вони досліджуються нижче.

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

Повторення і швидкоплинність

Якщо\( S \) скінченна, класифікація станів ланцюга народження-смерть як рецидивуючі або минущі проста, і залежить тільки від графіка стану. Зокрема, якщо ланцюг нескорочується, то ланцюг позитивна рецидивна. Так ми вивчимо класифікацію ланцюгів народження-смерть коли\( S = \N \). Ми припускаємо, що\( p(x) \gt 0 \) для всіх\( x \in \N \) і що\( q(x) \gt 0 \) для всіх\( x \in \N_+ \) (але, звичайно, ми повинні мати\( q(0) = 0 \)). Таким чином, ланцюг є незвідною.

За цими припущеннями ланцюг народження-смерть\( \N \) на

1. Аперіодичний якщо\( r(x) \gt 0 \) для деяких\( x \in \N \).
2. Періодичні з періодом 2 якщо\( r(x) = 0 \) для всіх\( x \in \N \).

Доказ

1. Якщо\( r(x) \gt 0 \) для деяких\( x \in \N \) то\( P(x, x) \gt 0 \) і, отже, ланцюг є аперіодичним.
2. Якщо\( r(x) = 0 \) для кожного,\( x \in \N \) то чітко ланцюг, що починається,\( x \) може бути в стані\( x \) знову тільки в парні часи.

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

Ланцюг\( \bs{X} \) повторюється тоді і тільки тоді, коли\[ \sum_{x = 0}^\infty \frac{q(1) \cdots q(x)}{p(1) \cdots p(x)} = \infty \]

Доказ

\( P_+ \)Дозвольте позначити обмеження\( P \) до\( \N_+ \times \N_+ \), і визначити\( u_+: \N_+ \to [0, 1] \)\[ u_+(x) = \P(X_1 \gt 0, X_2 \gt 0, \ldots \mid X_0 = x), \quad x \in \N_+ \] So\( u_+(x) \) є ймовірність того, що ланцюг ніколи не досягає 0, починаючи з\( x \in \N_+ \). З нашої загальної теорії ми знаємо, що\( u_+ \) задовольняє\( u_+ = P_+ u_+ \) і є найбільшою такою функцією зі значеннями в\( [0, 1] \). Крім того, ми знаємо, що або\( u_+(x) = 0 \) для всіх,\( x \in \N_+ \) або для цього\( \sup\{u_+(x): x \in [0, 1]\} = 1 \). У першому випадку ланцюг рецидивна, а в другому - перехідна.

Функціональне рівняння\( P_+ u = u \) для функції\( u: \N_+ \to [0, 1] \) еквівалентно такій системі рівнянь:\ begin {align} u (2) - u (1) & =\ frac {q (1)} {p (1)} u (1)\ u (x + 1) - u (x) & =\ frac {q (x)} {p (x)} [u (x) - u (x - 1),\ quad x\ in\ {2, 3,\ ldots\}\ end {align} Розв'язування цієї системи рівнянь для відмінності дає\[ u(x + 1) - u(x) = \frac{q(1) \cdots q(x)}{p(1) \cdots p(x)} u(1), \quad x \in \N_+ \] Рішення цієї нової системи дає\[ u(x) = u(1) \sum_{i=0}^{x-1} \frac{q(1) \cdots q(i)}{p(1) \cdots p(i)}, \quad x \in \N_+ \] Примітка,\( u(x) \) яка збільшується\( x \in \N_+ \) і тому має межу як\( x \to \infty \). Нехай\( A = \sum_{i=0}^\infty \frac{q(1) \cdots q(i)}{p(1) \cdots p(i)} \).

1. Припустимо, що\( A = \infty \). \( x \to \infty \)Введення в відображене рівняння вище для\( u(x) \) показує, що\( u(1) = 0 \) і так\( u(x) = 0 \) для всіх\( x \). Звідси ланцюг рецидивна.
2. Припустимо, що\( A \lt \infty \). Визначте,\( u(1) = 1/A \) а потім більш\[ u(x) = \frac{1}{A} \sum_{i=0}^{x-1} \frac{q(1) \cdots q(i)}{p(1) \cdots p(i)}, \quad x \in \N_+ \] загальне, Функція\( u \) приймає значення в\( (0, 1) \) і задовольняє функціональному рівнянню\( u = P_+ u \). Звідси ланцюг перехідний. Зверніть увагу, що\( u(x) \to 1 \) як\( x \to \infty \) і так насправді\( u = u_+ \), функція, про яку ми говорили вище, дає ймовірність залишитися в\( \N_+ \) протягом усього часу. Ми повернемося до цієї функції нижче в нашому обговоренні поглинання.

Зверніть увагу\( r \), що функція, яка присвоює кожному стану\( x \in \N \) ймовірність негайного повернення до\( x \), не грає прямої ролі в тому, чи є ланцюг перехідним або рецидивуючим. Дійсно, все, що має значення, - це співвідношення\( q(x) / p(x) \) для\( x \in \N_+ \).

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

Припустимо знову, що у нас є ланцюг\( \bs{X} \) народження-смерть\( \N \), з\( p(x) \gt 0 \) для всіх\( x \in \N \) і\( q(x) \gt 0 \) для всіх\( x \in \N_+\). Таким чином ланцюг є незвідною.

Функція,\( g: \N \to (0, \infty) \)\[ g(x) = \frac{p(0) \cdots p(x - 1)}{q(1) \cdots q(x)}, \quad x \in \N \] визначена, є інваріантною для\( \bs{X} \), і є єдиною інваріантною функцією, аж до множення на константи. Отже\( \bs{X} \), позитивна рекуррентна тоді і тільки тоді\( B = \sum_{x = 0}^\infty g(x) \lt \infty \), коли (унікальна) функція інваріантної щільності ймовірності\( f \) задається\( f(x) = \frac{1}{B} g(x) \) for\( x \in \N \).

Доказ

Нагадаємо, що за умовністю, добуток над порожнім набором індексу дорівнює 1. Отже, спочатку\ починаємо {вирівнювати*} (г Р) (0) & = г (0) Р (0, 0) + г (1) Р (1, 0) = г (0) r (0) + г (1) q (1)\\ & = 1 r (0) +\ frac {p (0)} {q (1)} q (1) = [1 - p (0)] + р (0) = 1 = г (0)\ кінець {вирівнювати*} Далі\( y \in \N_+ \), для,\ почати {вирівнювати*} (г Р) (у) & = г (у - 1) Р (у - 1, у) + г (у) Р (у, у) + г (у + 1) Р (у + 1, у)\ & = g (y - 1) р (у - 1) + г (у) р (у) + г (у + 1) q (y + 1)\\ & = g (y - 1) p (y - 1) + g (y) [1 - p (y) - q (y)] + г (y + 1) q (y + 1)\ кінець {вирівнювати*} Але\ почати вирівнювати*} g (y - 1) р (у - 1) & = г (у) q (y) =\ frac {p (0)\ cdots p (y - 1)} {q (1)\ cdots q (y - 1)}\ g (y + 1) q (y + 1) & = г (y) p (y) =\ frac {p (0)\ cdots p (y) {q} 1)\ cdots q ( y)}\ end {align*} так\( (g P)(y) = g(y) \).

І навпаки, припустимо, що\( h: \N \to \R \) є інваріантним для\( \bs{X} \). Ми покажемо індукцією, що\( h(x) = h(0) g(x) \) для всіх\( x \in \N \). Результат банально вірний\( x = 0 \) з тих пір\( g(0) = 1 \). Далі,\( (h P)(0) = h(0) \) дає\( h(0) P(0, 0) + h(1) P(1, 0) = h(0) \). Але\( P(0, 0) = r(0) = [1 - p(0)] \) і\( P(1, 0) = q(1) \), так заміна і рішення для\( h(1) \) дає\[ h(1) = h(0) \frac{p(0)}{q(1)} = h(0) g(1) \] так результат вірно, коли\( x = 1 \). Припустимо тепер, що\( y \in \N_+ \) і що результат вірний для всіх\( x \in \N \) с\( x \le y \). Потім\( (h P)(y) = h(y) \) дає\[ h(y - 1) P(y - 1, y) + h(y) P(y, y) + h(y + 1) P(y + 1, y) = h(y) \] Але\( P(y - 1, y) = p(y - 1) \)\( P(y, y) = r(y) = 1 - p(y) - q(y) \), і\( P(y + 1, y) = q(y + 1) \). Крім того, за індукційною гіпотезою\( h(y) = h(0) g(y) \) і\( h(y - 1) = h(0) g(y - 1) \) таким чином підставляючи і використовуючи визначення\( g \) дає\ begin {align*} q (y + 1) h (y + 1) & = [p (y) + q (y)] h (0)\ frac {p (0)\ cdots p (y - 1)} {q (1)\ cdots q (y)} - p (y - 1) h (0)\ frac {p (0)\ cdots p (y - 2)} {q (1)\ cdots q (y - 1)}\\ & = h (0) )\ frac {p (0)\ cdots p (y)} {q (1)\ cdots q (y)}\ end {align*} Нарешті, розв'язування дає\[ h(y + 1) = h(0) \frac{p(0) \cdots p(y)}{q(1) \cdots q(y + 1)} = h(0) g(y + 1) \]

Ось короткий виклад класифікації:

Для\( \bs X \) ланцюга народження-смерть визначте\[A = \sum_{x = 0}^\infty \frac{q(1) \cdots q(x)}{p(1) \cdots p(x)}, \quad B = \sum_{x = 0}^\infty \frac{p(0) \cdots p(x - 1)}{q(1) \cdots q(x)}\]

1. \( \bs X \)є тимчасовим, якщо\( A \lt \infty \)
2. \( \bs X \)є нульовим повторюваним, якщо\( A = \infty \) і\( B = \infty \).
3. \( \bs X \)є позитивним рецидивуючим, якщо\( B \lt \infty \).

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

Припустимо тепер, що\( n \in \N_+ \) і що\( \bs X = (X_0, X_1, X_2, \ldots) \) це ланцюг народження-смерть на цілочисельному інтервалі\( \N_n = \{0, 1, \ldots, n\} \). Ми припускаємо, що\( p(x) \gt 0 \) на\( x \in \{0, 1, \ldots, n - 1\} \) деякий час\( q(x) \gt 0 \) для\( x \in \{1, 2, \ldots n\} \). Звичайно, ми повинні мати\( q(0) = p(n) = 0 \). При цих припущеннях,\( \bs X \) є незведеним, а оскільки простір стану є кінцевим, позитивний рецидивуючий. Так що залишається лише знайти інваріантний розподіл. Результат по суті такий же, як і при державному просторі\( \N \).

Інваріантна функція щільності ймовірності\( f_n \) задається\[ f_n(x) = \frac{1}{B_n} \frac{p(0) \cdots p(x - 1)}{q(1) \cdots q(x)} \text{ for } x \in \N_n \text{ where } B_n = \sum_{x=0}^n \frac{p(0) \cdots p(x - 1)}{q(1) \cdots q(x)} \]

Доказ

Визначити\[ g_n(x) = \frac{p(0) \cdots p(x - 1)}{q(1) \cdots q(x)}, \quad x \in \N_n \] Доказ, для якого вони\( g_n \) є інваріантними\( \bs X \), такий же, як і раніше. Постійна\( B_n \) - нормалізує константа.

Зверніть увагу, що\( B_n \to B \) як\( n \to \infty \), і якщо\( B \lt \infty \),\( f_n(x) \to f(x) \) як\( n \to \infty \) для\( x \in \N \). Ми побачимо цей тип поведінки знову. Результати для ланцюга народження-смерть на\( \N_n \) часто сходяться до відповідних результатів для ланцюга народження-смерть на\( \N \) як\( n \to \infty \).

Поглинання

Часто, коли державний простір\( S = \N \), стан ланцюга народження-смерть являє собою популяцію індивідів якогось роду (і тому терміни народження і смерть мають свої звичні значення). У цьому випадку стан 0 поглинає і означає, що популяція вимерла. Зокрема, припустимо, що\( \bs X = (X_0, X_1, X_2, \ldots) \) це ланцюг народження-смерть на\( \N \) з\( r(0) = 1 \) і з\( p(x), \, q(x) \gt 0 \) для\( x \in \N_+ \). Таким чином, стан 0 поглинає і всі позитивні стани ведуть один до одного і до 0. Нехай\( N = \min\{n \in \N: X_n = 0\} \) позначають час до поглинання, де, як зазвичай,\( \min \emptyset = \infty \).

Відбудуться одна з наступних подій:

1. Вимирання населення:\( N \lt \infty \) або еквівалентно,\( X_m = 0 \) для деяких\( m \in \N \) і, отже,\( X_n = 0 \) для всіх\( n \ge m\).
2. Вибух населення:\( N = \infty \) або еквівалентно\( X_n \to \infty \) як\( n \to \infty \).

Доказ

Частина (б) випливає із загальної теорії, так як 0 поглинає, а всі позитивні стани ведуть один до одного і до 0. Таким чином, позитивні стани є перехідними, і ми знаємо, що з ймовірністю 1 ланцюг Маркова відвідуватиме перехідний стан лише скінченно часто. Таким\( N = \infty \) чином, еквівалентно\( X_n \to \infty \) як\( n \to \infty \).

Природно, ми хотіли б знайти ймовірність цих взаємодоповнюючих подій, і, на щастя, ми вже зробили це в нашому дослідженні повторення вище. Нехай\[ u(x) = \P(N = \infty) = \P(X_n \to \infty \text{ as } n \to \infty \mid X_0 = x), \quad x \in \N \] так ймовірність поглинання\[v(x) = 1 - u(x) = \P(N \lt \infty) = \P(X_n = 0 \text{ for some } n \in \N \mid X_0 = x), \quad x \in \N \]

Для ланцюга народження-смерть\( \bs X \),\[ u(x) = \frac{1}{A} \sum_{i=0}^{x - 1} \frac{q(1) \cdots q(i)}{p(1) \cdots p(i)} \text{ for } x \in \N_+ \text{ where } A = \sum_{i=0}^\infty \frac{q(1) \cdots q(i)}{p(1) \cdots p(i)} \]

Доказ

Для\( x \in \N_+ \), зверніть увагу на те\( u(x) = \P(X_n \in \N_+ \text{ for all } n \in \N \mid X_0 = x) \), що функція дає ймовірність перебування в позитивних станах за весь час. Доказ теореми про повторення вище не має нічого спільного з ймовірностями переходу в стані 0, тому доказ застосовується і в цьому налаштуванні. У цьому доказі ми показали, що\( u(x) \) як форма наведена вище, де, звичайно, значення 0 if\( A = \infty \). Тривіально,\( u(0) = 0 \).

Так що якщо\( A = \infty \) тоді\( u(x) = 0 \) для всіх\( x \in S \). Якщо\( A \lt \infty \) то\( u(x) \gt 0 \) для всіх\( x \in \N_+ \) і\( u(x) \to 1 \) як\( x \to \infty \). Для ймовірності поглинання,\( v(x) = 1 \) для всіх,\( x \in \N \) якщо\( A = \infty \) і так поглинання є певним. Якщо\( A \lt \infty \) потім\[v(x) = \frac{1}{A} \sum_{i=x}^\infty \frac{q(1) \cdots q(i)}{p(1) \cdots p(i)}, \quad x \in \N \] Далі ми вважаємо середній час до поглинання, так що нехай\( m(x) = \E(N \mid X_0 = x) \) для\( x \in \N_+ \).

Середня функція поглинання задається\[ m(x) = \sum_{j=1}^x \sum_{k=j-1}^\infty \frac{p(j) \cdots p(k)}{q(j) \cdots q(k+1)}, \quad x \in \N \]

Імовірнісний доказ

Кількість кроків, необхідних для переходу від стану\( x \in \N_+ \) до\( x - 1 \) має такий же розподіл, як і кількість кроків, необхідних для переходу від стану 1 до 0, за винятком параметрів\( p(y), \, q(y) \)\( p(y), \, q(y) \) для\( y \in \{x, x + 1, \ldots\} \)\( y \in \{1, 2, \ldots\} \). Таким чином, адитивність очікуваного значення, нам просто потрібно обчислити в\( m(1) \) якості функції параметрів. Починаючи зі стану 1, ланцюг буде поглинена в стані 0 після випадкового числа повернень до стану 1 без поглинання. Всякий раз, коли ланцюг знаходиться в стані 1, поглинання відбувається в наступний раз з ймовірністю,\( q(1) \) тому випливає, що кількість разів, коли ланцюг знаходиться в стані 1 до поглинання, має геометричний розподіл на\( \N_+ \) з параметром успіху\( q(1) \). Середнє значення цього розподілу є\( 1 / q(1) \). З іншого боку, починаючи зі стану 1, кількість кроків, поки ланцюг знову не перебуває у стані 1 (без поглинання), має такий же розподіл, як і час повернення до стану 0, починаючи з стану 0 для незведеного ланцюга народження-смерті,\( \bs{X}^\prime \) розглянутого вище, але з функціями народження та смерті \( p^\prime \)і\( q^\prime \) дається\( p^\prime(x) = p(x + 1) \) за\( x \in \N \) і\( q^\prime(x) = q(x + 1) \) за\( x \in \N_+ \). Таким чином, нехай\[ \mu = \sum_{k=0}^\infty \frac{p(1) \cdots p(k)}{q(2) \cdots q(k+1)} \] Then\( \mu \) - це середній час повернення до стану 0 для ланцюга\( \bs{X}^\prime \). Зокрема, зверніть увагу, що якщо\( \mu = \infty \) тоді\( \bs{X}^\prime \) є або перехідним, або нульовим повторюваним. Якщо\( \mu \lt \infty \) тоді\( 1 / \mu \) є інваріантним PDF на 0. Отже, випливає, що\[ m(1) = \frac{1}{q(1)} \mu = \sum_{k=0}^\infty \frac{p(1) \cdots p(k)}{q(1) \cdots q(k + 1)} \] За нашим аргументом вище, середній час переходу від держави\( x \) до\( x - 1 \)\[ \sum_{k=x-1}^\infty \frac{p(x) \cdots p(k)}{q(x) \cdots q(k + 1)} \]

Аналітичний доказ

Кондиціонування і використання нерухомості Маркова, у нас\[ m(x) = 1 + p(x) m(x + 1) + q(x) m(x - 1) + r(x) m(x), \quad x \in \N_+ \] з початковим станом\( m(0) = 0 \). Аналогічно,\[ m(x + 1) - m(x) = \frac{q(x)}{p(x)}[m(x) - m(x - 1)] - \frac{1}{p(x)}, \quad x \in \N_+ \] Рішення дає\[ m(x + 1) - m(x) = \frac{q(1) \cdots q(x)}{p(1) \cdots p(x)} m(1) - \sum_{y=1}^x \frac{q(y+1) \cdots q(x)}{p(y) \cdots p(x)}, \quad x \in \N_+ \] Next,\( m(x) = \sum_{y=0}^{x-1} [m(y+1) - m(y)] \) для\( x \in \N \) якого дає\[ m(x) = m(1) \sum_{y=0}^{x-1} \frac{q(1) \cdots q(y)}{p(1) \cdots p(y)} - \sum_{y=0}^{x-1} \sum_{z=1}^y \frac{q(z + 1) \cdots q(y)}{p(z) \cdots p(y)}, \quad x \in \N \] Finally,\( m(1) \) дається як у першому доказі. Вираз для\( m(x) \) різне, але рівнозначне, звичайно.

Далі ми розглянемо ланцюг народження-смерть на скінченному цілочисельному інтервалі з поглинаючими обома кінцевими точками. Наш інтерес полягає в ймовірності поглинання в одній кінцевій точці, а не в іншій, і в середньому часі до поглинання. Таким чином, припустимо, що\( n \in \N_+ \) і що\( \bs X = (X_0, X_1, X_2, \ldots) \) є ланцюгом народження-смерть на\( \N_n = \{0, 1, \ldots, n\} \) з\( r(0) = r(n) = 1 \) і з\( p(x) \gt 0 \) і\( q(x) \gt 0 \) для\( x \in \{1, 2, \ldots, n - 1\} \). Таким чином, кінцеві точки 0 і\( n \) поглинають, а всі інші стани ведуть один до одного і до кінцевих точок. Нехай\( N = \min\{n \in \N: X_n \in \{0, n\}\} \), час до поглинання, а для\( x \in S \) нехай\( v_n(x) = \P(X_N = 0 \mid X_0 = x) \) і\( m_n(x) = \E(N \mid X_0 = x) \). Визначення мають сенс, оскільки\( N \) є кінцевим з ймовірністю 1.

Функція ймовірності поглинання для стану 0 задається\[ v_n(x) = \frac{1}{A_n} \sum_{i=x}^{n-1} \frac{q(1) \cdots q(i)}{p(1) \cdots p(i)} \text{ for } x \in \N_n \text{ where } A_n = \sum_{i=0}^{n-1} \frac{q(1) \cdots q(i)}{p(1) \cdots p(i)} \]

Доказ

Кондиціонування та використання властивості Маркова,\( v_n \) задовольняє лінійне різницеве рівняння другого порядку\[ v_n(x) = p(x) v_n(x + 1) + q(x) v_n(x - 1) + r(x) v_n(x), \quad x \in \{1, 2, \ldots, n - 1\} \] з граничними умовами\( v_n(0) = 1 \),\( v_n(n) = 0 \). Як ми бачили раніше, різницеве рівняння можна переписати як\[v_n(x + 1) - v_n(x) = \frac{p(x)}{q(x)} [v_n(x) - v_n(x - 1)], \quad x \in \{1, 2, \ldots, n - 2\}\] Розв'язування та застосування граничних умов дає результат.

Зауважте, що\( A_n \to A \) як\( n \to \infty \) де\( A \) - константа вище для ймовірності поглинання при 0 з нескінченним простором стану\( \N \). Якщо\( A \lt \infty \) тоді\( v_n(x) \to v(x) \) як\( n \to \infty \) для\( x \in \N \).

Середній час поглинання задається тим,\[ m_n(x) = m_n(1) \sum_{y=0}^{x-1} \frac{q(1) \cdots q(y)}{p(1) \cdots p(y)} - \sum_{y=0}^{x-1} \sum_{z=1}^y \frac{q(z+1) \cdots q(y)}{p(z) \cdots p(y)}, \quad x \in \N_n \] де, з,\( A_n \) як і в попередній теоремі,\[ m_n(1) = \frac{1}{A_n} \sum_{y=1}^{n-1} \sum_{z=1}^y \frac{q(z+1) \cdots q(y)}{p(z) \cdots p(y)} \]

Доказ

Ймовірнісний доказ вище з простором стану\( \N \) та поглинанням 0 тут не працює, але перша частина аналітичного доказу робить. Отже,\[ m_n(x) = m_n(1) \sum_{y=0}^{x-1} \frac{q(1) \cdots q(y)}{p(1) \cdots p(y)} - \sum_{y=0}^{x-1} \sum_{z=1}^y \frac{q(z + 1) \cdots q(y)}{p(z) \cdots p(y)}, \quad x \in \{1, 2, \ldots, n\} \] підставляючи\( x = n \) і застосовуючи\( m_n(n) = 0 \) граничну умову, дає результат для\( m_n(1) \) теореми.

Час розвороту

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

Припустимо, що\( \bs X = (X_0, X_1, X_2, \ldots) \) це незведена, повторювана ланцюг народження-смерть на цілочисельному інтервалі\( S \). Потім\( \bs X \) є оборотним.

Доказ

Потрібно показати, що умова циклу Колмогорова виконана. Тобто, для кожної послідовності станів\((x_0, x_1, x_2, \ldots, x_n) \) з\( x_0 = x_n \),\[ P(x_0, x_1) P(x_1, x_2) \cdots P(x_{n-1}, x_n) = P(x_n, x_{n-1}) P(x_{n-1}, x_{n-2}) \cdots P(x_1, x_0) \] Ми можемо обмежити нашу увагу послідовності де\( x_{i+1} \in \{x_i, x_i - 1, x_i + 1\} \) для кожного\( i \in \{1, 2, \ldots, n\} \). Для таких послідовностей умова циклу тривіально задовольняється.

Якщо\( S \) скінченна і ланцюг\( \bs X \) нескоротна, то, звичайно,\( \bs X \) є рецидивуючою (насправді позитивний рецидивуючий), тому за попереднім результатом,\( \bs X \) оборотний. У цьому\( S = \N \) випадку ми можемо використовувати інваріантну функцію вище, щоб показати безпосередньо, що ланцюг є оборотним.

Припустимо, що\( \bs X = (X_0, X_1, X_2, \ldots) \) це ланцюг народження-смерть на\( \N \) з\( p(x) \gt 0 \) for\( x \in \N \) і\( q(x) \gt 0 \) for\( x \in \N_+ \). Потім\( \bs X \) є оборотним.

Доказ

З функцією,\( g \) визначеною вище, досить показати умову оборотності\( g(x)P(x, y) = g(y) P(y, x) \) для всіх\( x, \, y \in \N \). Потім випливає, що\( g \) є інваріантним для\( \bs{X} \) і що\( \bs{X} \) є оборотним щодо\( g \). Але оскільки\( g \) є єдиною позитивною інваріантною функцією для\( \bs{X} \), аж до множення на позитивні константи, ми можемо опустити кваліфікаційну фразу щодо\( g \). Бо\( x \in \N \) і\( y = x + 1 \) ми маємо\[g(x) P(x, y) = g(y) P(y, x) = \frac{p(0) \cdots p(x)}{q(1) \cdots q(x)}\]\( x \in \N_+ \) For і\( y = x - 1 \) ми маємо\[ g(x) P(x, y) = g(y) P(y, x) = \frac{p(0) \cdots p(x - 1)}{q(1) \cdots q(x - 1)} \] У всіх інших випадках умова оборотності тривіально задовольняється.

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

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

Як завжди, обов'язково спробуйте проблеми самостійно, перш ніж дивитися на рішення.

Постійні ймовірності народження та смерті

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

Припустимо,\( \bs X = (X_0, X_1, X_2, \ldots) \) що ланцюг народження-смерть на\( \N \) з постійною ймовірністю народження\( p \in (0, \infty) \) на\( \N \) і постійною ймовірністю смерті\( q \in (0, \infty) \) на\( \N_+ \), с\( p + q \le 1 \). Тоді

1. \( \bs X \)є тимчасовим, якщо\( q \lt p \)
2. \( \bs X \)є нульовим повторюваним, якщо\( q = p \)
3. \( \bs X \)є додатним рекуррентним if\( q \gt p \), а інваріантним розподілом є геометричний розподіл по параметру\( \N \) with\( p / q \)\[ f(x) = \left( 1 - \frac{p }{q} \right) \left( \frac{p}{q} \right)^x, \quad x \in \N \]

Далі ми розглянемо випадкову прогулянку на\( \N \) з 0 поглинанням. Як і в обговоренні поглинання вище,\( v(x) \) позначається ймовірність\( m(x) \) поглинання і середній час до поглинання, починаючи в стані\( x \in \N \).

Припустимо,\( \bs X = (X_0, X_1, \ldots) \) що ланцюг народження-смерть на\( \N \) з постійною ймовірністю народження\( p \in (0, \infty)\) на\( \N_+ \) і постійною ймовірністю смерті\( q \in (0, \infty) \) на\( \N_+ \), с\( p + q \le 1 \). Припустимо також\( r(0) = 1 \), що, так що 0 поглинає.

1. Якщо\( q \ge p \) то\( v(x) = 1 \) для всіх\( x \in \N \). Якщо\( q \lt p \) тоді\( v(x) = (q/p)^x\) для\(x \in \N \).
2. Якщо\( q \le p \) то\( m(x) = \infty \) для всіх\( x \in \N_+ \). Якщо\( q \gt p \) тоді\( m(x) = x / (q - p)\) для\(x \in \N\).

Доказ

1. Це випливає із загального результату вище для ймовірності поглинання.
2. Це також випливає із загального результату вище для середнього часу поглинання, але ми наведемо прямий доказ, використовуючи ті ж ідеї. Якщо\( q \lt p \) то\( \P(N = \infty \mid X_0 = x) \gt 0 \) і значить\( m(x) = \infty \) для\( x \in \N_+ \). Так що припустимо, що\( q \ge p \) так\( \P(N \lt \infty \mid X_0 = x) = 1 \) для\( x \in \N \). Через просторову однорідність час, необхідний для досягнення стану, що\( x - 1 \) починається в стані,\( x \in \N_+ \) має такий же розподіл, як і час, необхідний для досягнення стану 0, починаючи з стану 1. За адитивності очікуваної величини випливає, що\( m(x) = x \, m(1) \) для\( x \in \N \). Так що нам залишається обчислити\( m(1) \). Починаючи з стану 1, ланцюг буде поглинатися в стан 0 після випадкового числа проміжних повернень в стан 1 з поглинанням. У стані 1 ймовірність поглинання на наступному етапі дорівнює\( q \), тому кількість разів, коли ланцюг знаходиться в стані 1 до поглинання, має геометричний розподіл на\( \N_+ \) з параметром успіху\( q \). Отже, середня кількість відвідувань є\( 1 / q \). У стані 1 кількість кроків перед поверненням до кроку 1 без поглинання має такий же розподіл, як і час повернення до стану 0, починаючи з 0, для повторного ланцюга, розглянутого в попередній вправі. Середнє значення цього розподілу\( \infty \) if\( q = p \) і is\( 1 / f(0) \) if\( q \gt p \), were\( f \) - інваріантний розподіл. Звідси випливає, що\[ m(1) = \frac{1}{q} \frac{1}{1 - p / q} = \frac{1}{q - p}\]

Цей ланцюг по суті є ланцюгом розорення азартного гравця. Розглянемо азартного гравця, який робить ставку на послідовність самостійних ігор, де\( p \) і\( q \) є ймовірності виграшу і програшу відповідно. Азартний гравець отримує одну грошову одиницю, коли вона виграє гру, і повинен заплатити одну одиницю, коли вона програє гру. Так\( X_n \) само і стан азартного гравця після гри в\( n \) ігри.

Далі розглянемо випадкові прогулянки на скінченному інтервалі.

Припустимо,\( \bs X = (X_0, X_1, \ldots) \) що ланцюг народження-смерть на\( \N_n = \{0, 1, \ldots, n\} \) з постійною ймовірністю народження\( p \in (0, \infty) \) на\( \{0, 1, \ldots, n - 1\} \) і постійною ймовірністю смерті\( q \in (0, \infty) \) на\( \{1, 2, \ldots, n\} \), с\( p + q \le 1 \). Потім\( \bs X \) позитивний рекуррент і інваріантна функція щільності ймовірності\( f_n \) задається наступним чином:

1. Якщо\( p \ne q \) тоді\[ f_n(x) = \frac{(p/q)^x (1 - p/q)}{1 - (p/q)^{n+1}}, \quad x \in \N_n\]
2. Якщо\( p = q \) тоді\( f_n(x) = 1 / (n + 1) \) для\( x \in \N_n \).

Зауважимо, що якщо\( p \lt q \) тоді інваріантний розподіл є усіченим геометричним розподілом, а\( f_n(x) \to f(x) \)\( x \in \N \) де\( f \) - інваріантна функція щільності ймовірності ланцюга народження-смерть на\( \N \) розглянутому вище. Якщо\( p = q \), інваріантний розподіл рівномірний на\( \N_n \), безумовно, розумний результат. Далі розглядаємо ланцюг з обома кінцевими точками поглинання. Як і раніше,\( v_n \) це функція, яка дає ймовірність поглинання в стані 0, в той час як\( m_n \) це функція, яка дає середній час до поглинання.

Припустимо,\( \bs X = (X_0, X_1, \ldots) \) що ланцюг народження-смерть на\( \N_n = \{0, 1, \ldots, n\} \) з постійною ймовірністю народження\( p \in (0, 1) \) і ймовірністю смерті\( q \in (0, \infty) \) на\( \{1, 2, \ldots, n - 1\} \), де\( p + q \le 1 \). Припустимо також те\( r(0) = r(n) = 1 \), що, щоб\( 0 \) і\( n \) поглинали.

1. Якщо\( p \ne q \) тоді\[ v_n(x) = \frac{(q/p)^x - (q/p)^n}{1 - (q/p)^n}, \quad x \in \N_n \]
2. Якщо\( p = q \) тоді\( v_n(x) = 1 - x / n \) для\( x \in \N_n \)

Зверніть увагу, що якщо\( q \lt p \) тоді\( v_n(x) \to v(x) \) як\( n \to \infty \) для\( x \in \N \).

Припустимо знову,\( \bs X = (X_0, X_1, \ldots) \) що ланцюг народження-смерть на\( \N_n = \{0, 1, \ldots, n\} \) з постійною ймовірністю народження\( p \in (0, 1) \) і ймовірністю смерті\( q \in (0, \infty) \) на\( \{1, 2, \ldots, n - 1\} \), де\( p + q \le 1 \). Припустимо також те\( r(0) = r(n) = 1 \), що, щоб\( 0 \) і\( n \) поглинали.

1. Якщо\( p \ne q \) тоді\[ m_n(x) = \frac{n}{p - q} \frac{1 - (q/p)^x}{1 - (q/p)^n} + \frac{x}{q - p}, \quad x \in \N_n \]
2. Якщо\( p = q \) тоді\[ m_n(x) = \frac{1}{2p}x(n - x), \quad x \in \N_n \]

Спеціальні ланцюги народження-смерті

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

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

1. Мережа Еренфест.
2. Модифікована ланцюг Еренфест.
3. Ланцюг Бернуллі-Лаплас
4. Проста випадкова прогулянка далі\( \Z \).

Відповідь

1. Ланцюг Ehrenfest з параметром\( m \in \N_+ \) - це ланцюг смерті народження на\( S = \{0, 1, \ldots, m\} \) з\( q(x) = \frac{x}{m} \) і\( p(x) = \frac{m - x}{m} \) за\( x \in S \).
2. Модифікована ланцюг Еренфеста з параметром\( m \in \N_+ \) - це ланцюжок смерті народження на\( S = \{0, 1, \ldots, m\} \) с\( q(x) = \frac{x}{2 m} \)\( r(x) = \frac{1}{2} \), і\( p(x) = \frac{m - x}{2 m} \) для\( x \in S \).
3. Ланцюг Бернуллі-Лапласа з параметрами\( j, \, k, \, r \in \N_+ \) з\(r \lt j + k \) - це ланцюг народження-смерть на\( S = \{\max\{0, r - j\}, \ldots, \min\{k, r\}\} \) с\( q(x) = \frac{(j - r + x) x}{j k} \)\( r(x) = \frac{(r - x) x + (j - r + x)(k - x)}{j k} \), і\( p(x) = \frac{(r - x)(k - x)}{j k} \) для\( x \in S \).
4. Проста випадкова прогулянка по\( \Z \) параметру\( p \in (0, 1) \) - це ланцюг народження-смерть на\( \Z \) з\( p(x) = p \) і\( q(x) = 1 - p \) для\( x \in \Z \).

Інші приклади

Розглянемо процес народження-смерті на\( \N \) с\( p(x) = \frac{1}{x + 1} \)\( q(x) = 1 - p(x) \), і\( r(x) = 0 \) для\( x \in S \).

1. Знайдіть інваріантну функцію\( g \).
2. Класифікувати ланцюжок.

Відповідь

1. Зверніть увагу, що\( p(0) \cdots p(x - 1) = \frac{1}{x!} \) і\( q(1) \cdots q(x) = \frac{1}{x + 1} = p(x) \) для\( x \in \N \). Звідси\( g(x) = \frac{x + 1}{x!} \).
2. Зверніть увагу, що\[ \sum_{x = 0}^\infty g(x) = \sum_{x = 1}^\infty \frac{1}{(x - 1)!} + \sum_{x = 0}^\infty \frac{1}{x!} = 2 e \] Таким чином, ланцюжок є позитивним рецидивом, з\( f \) інваріантним PDF, заданим\[ f(x) = e^{-2} \frac{(x + 1)}{x!}, \quad x \in \N \] також, ланцюжок є періодичним з періодом 2.