16.11: Ланцюг розгалуження дискретного часу

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

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

Вступ

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

• Частинки - це біологічні організми, які розмножуються.
• Частинки є нейтронами в ланцюговій реакції.
• Частинки є електронами в електронному множнику.

Ми припускаємо, що кожна частинка в кінці свого життя замінюється випадковим числом нових частинок, які ми будемо називати дочірніми частинами вихідної частинки. Наше основне припущення полягає в тому, що частинки діють незалежно, кожна з однаковим розподілом потомства\( \N \). \( f \)Дозвольте позначити загальну функцію щільності ймовірності числа потомства частки. Ми також дозволимо\( f^{*n} = f * f * \cdots * f \) позначити потужність згортки\( n \) ступеня\( f \); це функція щільності ймовірності загальної кількості дочірніх\( n \) частинок.

Ми розглянемо еволюцію системи в реальному часі в нашому дослідженні безперервно-часових розгалужених ланцюгів. У цьому розділі ми вивчимо еволюцію системи за час поколінь. Зокрема, частинки, з яких ми починаємо, знаходяться в поколінні 0, і рекурсивно діти частинки в генерації\( n \) знаходяться в генерації\( n + 1 \).

Малюнок\(\PageIndex{1}\): Покоління 0, 1, 2 та 3 розгалуженого ланцюга.

\( X_n \)Дозвольте позначити кількість частинок в генерації\( n \in \N \). Один із способів побудови процесу математично полягає в тому, щоб почати з масиву незалежних випадкових величин\( (U_{n,i}: n \in \N, \; i \in \N_+) \), кожна з яких має функцію щільності ймовірності\( f \). Ми інтерпретуємо\( U_{n,i} \) як кількість дочірніх\( i \) частинок у генерації\( n \) (якщо ця частка існує). Зверніть увагу, що у нас більше випадкових величин, ніж нам потрібно, але це не завдає шкоди, і ми знаємо, що ми можемо побудувати простір ймовірностей, який підтримує такий масив випадкових величин. Тепер ми можемо визначити наші змінні стану рекурсивно\[ X_{n+1} = \sum_{i=1}^{X_n} U_{n,i} \]

\( \bs{X} = (X_0, X_1, X_2, \ldots) \)— дискретний марковський ланцюг на\( \N \) з матрицею ймовірностей переходу,\( P \) заданою ланцюгом. Ланцюжок\( \bs{X} \) - це розгалужений ланцюг з розподілом потомства, що визначається\( f \).\[ P(x, y) = f^{*x}(y), \quad (x, y) \in \N^2 \]

Доказ

Властивість Маркова і форма матриці переходу випливають безпосередньо з побудови змінних стану, наведених вище. Оскільки змінні\( (U_{n,i}: n \in \N, i \in \N_+) \) є незалежними, кожен з PDF\( f \), у нас є\[ \P(X_{n+1} = y \mid X_0 = x_0, \ldots, X_{n-1} = x_{n-1}, X_n = x) = \P\left(\sum_{i=1}^x U_{n,i} = y\right) = f^{*x}(y) \]

Розгалужений ланцюг також відомий як процес Галтона-Уотсона на честь Френсіса Галтона і Генрі Вільяма Уотсона, які вивчали подібні процеси в контексті виживання (аристократичних) прізвищ. Зверніть увагу, що нащадки кожної початкової частинки утворюють розгалужується ланцюжок, і ці ланцюги незалежні. Таким чином, розгалужується ланцюг, що починається\( x \) частинками, еквівалентна\( x \) незалежним копіям ланцюга розгалуження, що починається з 1 частинки. Ці особливості виявляються дуже важливими при аналізі ланцюга. Зауважте також, що 0 - це поглинаючий стан, який відповідає вимиранню. З іншого боку, популяція може зростати до нескінченності, яку іноді називають вибухом. Обчислення ймовірності зникнення - одна з фундаментальних проблем в розгалужених ланцюгах; ми по суті вирішимо цю проблему в наступному підрозділі.

Вимирання і вибух

Поведінка розгалуженого ланцюга в очікуваному значенні легко проаналізувати. Нехай\( m \) позначають середнє значення розподілу потомства, так що\[ m = \sum_{x=0}^\infty x f(x) \] зверніть увагу на те, що\( m \in [0, \infty] \). Параметр\( m \) виявиться принциповим значенням.

Властивості очікуваного значення

1. \( \E(X_{n+1}) = m \E(X_n) \)для\( n \in \N \)
2. \( \E(X_n) = m^n \E(X_0) \)для\( n \in \N \)
3. \( \E(X_n) \to 0 \)\( n \to \infty \)ніби\( m \lt 1 \).
4. \( \E(X_n) = \E(X_0) \)для кожного\( n \in \N \) якщо\( m = 1 \).
5. \( \E(X_n) \to \infty \)\( n \to \infty \)ніби\( m \gt 1 \) і\( \E(X_0) \gt 0 \).

Доказ

Для частини (а) ми використовуємо аргумент кондиціонування та конструкцію вище. Для\( x \in \N \),\[ \E(X_{n+1} \mid X_n = x) = \E\left(\sum_{i=1}^x U_{n,i} \biggm| X_n = x\right) = \E\left(\sum_{i=1}^x U_{n,i}\right) = m x \] Тобто,\( \E(X_{n+1} \mid X_n) = m X_n \) так\( \E(X_{n+1}) = \E\left[\E(X_{n+1} \mid X_n)\right] = m \E(X_n) \) Частина (b) випливає з (а), а потім частини (c), (d), і (е) слідують з (б).

Частина (c) - це вимирання в середньому; частина (d) - стабільність у середньому; а частина (е) - вибух у середньому.

Нагадаємо, що стан 0 поглинає (немає частинок), а отже\( \{X_n = 0 \text{ for some } n \in \N\} = \{\tau_0 \lt \infty\} \), і подія вимирання (де, як\( \tau_0 \) зазвичай, - час першого повернення до 0). Нас в першу чергу хвилює ймовірність згасання, як функції початкового стану. Однак спочатку ми зробимо кілька простих спостережень і усунемо деякі банальні випадки.

Припустимо\( f(1) = 1 \), що так, що кожна частинка заміщається однією новою частинкою. Тоді

1. Кожен стан поглинає.
2. Класи еквівалентності - це одноелетні множини.
3. З ймовірністю 1,\( X_n = X_0 \) для кожного\( n \in \N \).

Доказ

Ці властивості очевидні, так як\( P(x, x) = 1 \) для кожного\( x \in \N \).

Припустимо, що\( f(0) \gt 0 \) так, що з позитивною ймовірністю частка загине без потомства. Тоді

1. Кожен стан призводить до 0.
2. Кожен позитивний стан є тимчасовим.
3. З імовірністю 1 або\( X_n = 0 \) для деяких\( n \in \N \) (вимирання)\( X_n \to \infty \), або як\( n \to \infty \) (вибух).

Доказ

1. Зверніть увагу, що\( P(x, 0) = [f(0)]^x \gt 0 \) for\( x \in \N \), тому кожен стан призводить до 0 за один крок.
2. Це випливає з (а). Якщо\( x \in \N_+ \), то\( x \) призводить до поглинаючого стану 0 з позитивною ймовірністю. Отже, повернення до\( x \), починаючи з\( x \), не може мати ймовірність 1.
3. Це випливає з (а) і (b). З імовірністю 1 кожен позитивний стан відвідується лише скінченно багато разів. Звідси єдині можливості є\( X_n = 0 \) для деяких\( n \in \N \) або\( X_n \to \infty \) як\( n \to \infty \).

Припустимо\( f(1) \lt 1 \), що\( f(0) = 0 \) і, щоб кожна частка замінилася хоча б однією частинкою, а з позитивною ймовірністю більше однієї. Тоді

1. Кожен позитивний стан є тимчасовим.
2. \( \P(X_n \to \infty \text{ as } n \to \infty \mid X_0 = x) = 1 \)для кожного\( x \in \N_+ \), щоб вибух був впевнений, починаючи хоча б з однієї частинки.

Доказ

1. Нехай\( x \in \N_+ \). За припущеннями про\( f \), стан\( x \) призводить до якогось стану,\( y \gt x \) але\( y \) не призводить назад до\( x \). Отже, з позитивною ймовірністю ланцюг,\( x \) що починається, не повернеться до\( x \).
2. Це випливає з (а) і що той факт, що позитивні стани не призводять до 0.

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

1. Кожен стан призводить до 0.
2. Кожен позитивний стан є тимчасовим.
3. З імовірністю 1,\( X_n = 0 \) для деяких\( n \in \N \), так вимирання є певним.

Доказ

1. Як і раніше,\( P(x, 0) = [f(0)]^x \gt 0 \) for\( x \in \N \), так\( x \) призводить до 0 за один крок.
2. Це випливає з (а) і того, що 0 поглинає.
3. За припущеннями про\( f \), стан\( x \) призводить до стану\( y \) тільки якщо\( y \le x \). Отже, це випливає з (а) і (b).

Таким чином, цікавий випадок, коли\( f(0) \gt 0 \) і\( f(0) + f(1) \lt 1 \), так що з позитивною ймовірністю, частка загине без потомства, а також з позитивною ймовірністю частка буде замінена більш ніж однією новою частинкою. Ці умови ми візьмемо на себе до кінця нашого обговорення. За державною класифікацією вище всіх станів призводять до 0 (вимирання). Вірогідність згасання ми позначимо, починаючи з однієї частинки, по\[ q = \P(\tau_0 \lt \infty \mid X_0 = 1) = \P(X_n = 0 \text{ for some } n \in \N \mid X_0 = 1) \]

Безліч позитивних станів\( \N_+ \) є класом перехідної еквівалентності, а ймовірність згасання, починаючи з\( x \in \N \) частинок, дорівнює\[ q^x = \P(\tau_0 \lt \infty \mid X_0 = x) = \P(X_n = 0 \text{ for some } n \in \N \mid X_0 = x) \]

Доказ

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

Нагадаємо, що розгалужується ланцюг, що починається з\( x \in \N_+ \) частинок, діє як\( x \) незалежні ланцюги розгалуження, що починаються з однієї частинки. Таким чином, ймовірність зникнення, починаючи з\( x \) частинок, є\( q^x \).

Параметр\( q \) задовольняє рівнянню\[ q = \sum_{x = 0}^\infty f(x) q^x \]

Доказ

Цей результат випливає з кондиціонування на першому стані. \[ q = \P(\tau_0 \lt \infty \mid X_0 = 1) = \sum_{x = 0}^\infty \P(\tau_0 \lt \infty \mid X_0 = 1, X_1 = x) \P(X_1 = x \mid X_0 = 1) \]Але за марківським властивістю і попереднім результатом,\[ \P(\tau_0 \lt \infty \mid X_0 = 1, X_1 = x) = \P(\tau_0 \lt \infty \mid X_1 = x) = q^x \] і звичайно\( \P(X_1 = x \mid X_0 = 1) = P(1, x) = f(x) \).

Таким чином, ймовірність вимирання, що\( q \) починається з 1 частинки, є фіксованою точкою\( \Phi \) ймовірнісно-генеруючої функції розподілу потомства:\[ \Phi(t) = \sum_{x=0}^\infty f(x) t^x, \quad t \in [0, 1] \] Крім того, із загального обговорення ймовірностей ударів у розділі про рецидиви та швидкоплинність,\( q \) є найменшим таким числом в інтервалі\( (0, 1] \). Якщо функція, що генерує ймовірність,\( \Phi \) може бути обчислена в замкнутому вигляді, то іноді\( q \) може бути обчислена вирішенням рівняння\( \Phi(t) = t \).

\( \Phi \)задовольняє наступним властивостям:

1. \( \Phi(0) = f(0) \).
2. \( \Phi(1) = 1 \).
3. \( \Phi^\prime(t) \gt 0 \)для\( t \in (0, 1) \) цього\( \Phi \) в збільшенні на\( (0, 1) \).
4. \( \Phi^{\prime \prime}(t) \gt 0 \)бо\( t \in (0, 1) \) так\( \Phi \) у увігнутому вгору на\( (0, 1) \).
5. \( m = \lim_{t \uparrow 1} \Phi^\prime(t) \).

Доказ

Це основні властивості функції, що генерує ймовірність. Нагадаємо, що ряд, який визначає,\( \Phi \) є степеневим рядом близько 0 з радіусом збіжності\( r \ge 1 \). Функція, визначена степеневим рядом, нескінченно диференційовна в межах відкритого інтервалу збіжності, а похідні можуть бути обчислені терміном за терміном. Так\ почати {вирівнювати*}\ Phi^\ прайм (t) &=\ sum_ {x = 1} ^\ infty x f (x) t^ {x-1}\ gt 0,\ квад t\ in (0, 1)\\ Phi^ {\ прайм\ прайм} (t) &=\ sum_ {x = 2} ^\ infty x (x - 1) f (x) ^ (x - 1) f (x) ^ (x) {x - 2}\ gt 0,\ quad t\ in (0, 1)\ end {align*} Якщо\( r \gt 1 \) тоді\( m = \Phi^\prime(1) \). Якщо\( r = 1 \), лімітний результат є найкращим, що ми можемо зробити.

Наш основний результат наступний, і пов'язує ймовірність вимирання\( q \) і середнє значення розподілу потомства\( m \).

Імовірність вимирання\( q \) і середнє значення розподілу потомства\( m \) пов'язані наступним чином:

1. Якщо\( m \le 1 \) тоді\( q = 1 \), так вимирання точно.
2. Якщо\( m \gt 1 \) тоді\( 0 \lt q \lt 1 \), так є позитивна ймовірність згасання і позитивна ймовірність вибуху.

Доказ

Малюнок\(\PageIndex{2}\): Випадок певного вимирання.

Малюнок\(\PageIndex{3}\): Випадок можливого згасання і можливого вибуху.

Обчислювальні вправи

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

1. Матриця переходу\( P \).
2. Середнє\( m \) значення розподілу потомства.
3. Генеруюча функція\( \Phi \) розподілу потомства.
4. Імовірність вимирання\( q \).

Відповідь

Зверніть увагу, що змінна потомства має вигляд,\( 2 I \) де\( I \) є індикаторна змінна з параметром\( p \).

1. Для\( x \in \N \),\( f^{* x} \) є PDF\( 2 U \) де\( U \) має біноміальний розподіл з параметрами\( x \) і\( p \). Звідси\[ P(x, y) = f^{* x}(y) = \binom{x}{y/2} p^{y/2} (1 - p)^{x - y/2}, \quad y \in \{0, 2, \ldots, 2x\} \]
2. \( m = 2 p \).
3. \(\Phi(t) = p t^2 + (1 - p)\)для\( t \in \R \).
4. \( q = 1 \)якщо\(0 \lt p \le \frac{1}{2} \) і\( q = \frac{1 - p}{p} \) якщо\( \frac{1}{2} \lt p \lt 1 \).

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( p = \frac{1}{3} \)

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( p = \frac{2}{3} \)

Розглянемо розгалужений ланцюг, розподіл потомства якої є геометричним розподілом по параметру\( \N \)\( 1 - p \) with, де\( p \in (0, 1) \). Таким чином\( f(n) = (1 - p) p^n \) для\( n \in \N \). Знайдіть кожне з наступних дій:

1. Матриця переходу\( P \).
2. Середнє\( m \) значення розподілу потомства.
3. Генеруюча функція\( \Phi \) розподілу потомства.
4. Імовірність вимирання\( q \).

Відповідь

1. For\( x \in \N \),\( f^{* x} \) є PDF-файлом негативного біноміального розподілу on\( \N \) with параметр\( 1 - p \). Так\[ P(x, y) = f^{* x}(y) = \binom{x + y - 1}{x - 1} p^y (1 - p)^x, \quad y \in \N \]
2. \( m = \frac{p}{1 - p} \).
3. \(\Phi(t) = \frac{1 - p}{1 - p t}\)для\( \left|t\right| \lt \frac{1}{p} \).
4. \( q = 1 \)якщо\(0 \lt p \le \frac{1}{2} \) і\( q = \frac{1 - p}{p} \) якщо\( \frac{1}{2} \lt p \lt 1 \).

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( p = \frac{1}{3} \)

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( p = \frac{2}{3} \)

Цікаво, що ймовірність вимирання така ж, як і для попередньої проблеми.

Розглянемо розгалужений ланцюг, розподілом потомства якої є розподіл Пуассона з параметром\( m \in (0, \infty) \). Таким чином\( f(n) = e^{-m} m^n / n! \) для\( n \in \N \). Знайдіть кожне з наступних дій:

1. Матриця переходу\( P \).
2. Середнє\( m \) значення розподілу потомства.
3. Генеруюча функція\( \Phi \) розподілу потомства.
4. Приблизна ймовірність вимирання\( q \) коли\( m = 2 \) і коли\( m = 3 \).

Відповідь

1. Для\( x \in \N \),\( f^{* x} \) це PDF розподілу Пуассона з параметром\( m x \). Так\[ P(x, y) = f^{* x}(y) = e^{-m x} \frac{(m x)^y}{y!}, \quad y \in \N \]
2. Параметр\( m \) - це середнє значення розподілу Пуассона, тому позначення узгоджені.
3. \(\Phi(t) = e^{m (t - 1)}\)для\( t \in \R \).
4. \( q = 1 \)якщо\(0 \lt m \le 1 \). Якщо\( m \gt 1 \) тоді\( q \) є розв'язком рівняння,\( e^{m (q - 1)} = q \) яке може бути виражене через спеціальну функцію, відому як \( W \)функція Ламберта:\[ q = -\frac{1}{m} W\left(-m e^{-m}\right) \] For\( m = 2 \),\( q \approx 0.20319 \).\( (0, 1) \) Для\( m = 3 \),\( q \approx 0.059520 \).

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( m = \frac{1}{2} \)

Графіки\( t \mapsto \Phi(t) \) і\( t \mapsto t \) коли\( m = 2 \)