10.2: Розгалуження процесів
- Page ID
- 98379
Історичне передумови
У цьому розділі ми застосуємо теорію генеруючих функцій до вивчення важливого випадкового процесу, який називається
До недавнього часу вважалося, що теорія розгалужених процесів виникла з наступною проблемою, поставленої Френсісом Галтоном в 1873 році. 1
Проблема 4001: Велика нація, про яку ми будемо стосуватися лише дорослих самців,\(N\) за кількістю, і кожен з яких носить окремі прізвища, колонізує район. Їх закон населення такий, що у кожному поколінні\(a_0\) відсоток дорослих чоловіків не мають дітей чоловічої статі, які досягають дорослого життя;\(a_1\) мають одну таку дитину чоловічої статі;\(a_2\) мають двох; і так далі до\(a_5\) тих, хто має п'ять.
Знайдіть (1) яка частка прізвищ вимерла після\(r\) поколінь; і (2) скільки інстанцій одного прізвища буде утримуватися\(m\) особами.
Перша спроба вирішення була дана преподобним Х.Уотсоном. Через помилку в алгебрі він неправильно зробив висновок, що прізвище завжди вимирає з ймовірністю 1. Однак методи, які він застосував для вирішення проблем, були і залишаються основою для отримання правильного рішення.
Хейде і Сенета виявили більш раннє спілкування Біенайме (1845), яке передбачало Галтона і Ватсона на 28 років. Насправді Біенеме показав, що він усвідомлює правильне рішення проблеми Галтона. Хейде і Сенета у своїй книзі 2 дають наступний переклад з статті Біенайме:
Якби... середнє значення кількості дітей чоловічої статі, які замінюють кількість чоловіків попереднього покоління, було б менше, ніж єдність, легко було б зрозуміти, що сім'ї вимирають через зникнення членів, з яких вони складаються. Однак аналіз показує далі, що коли це середнє значення дорівнює єдності сім'ї, як правило, зникають, хоча і менш швидко...
Аналіз також чітко показує, що якщо середнє співвідношення більше одиниці, ймовірність вимирання сімей з плином часу вже не зводиться до визначеності. Він наближається лише до кінцевої межі, яку досить просто обчислити і яка має сингулярну характеристику, яка дається одним із коренів рівняння (в якому кількість поколінь робиться нескінченною), що не має відношення до питання, коли середнє співвідношення менше одиниці. 3
Хоча Біенеме не дає своїх міркувань щодо цих результатів, він вказав, що має намір опублікувати спеціальний документ з цієї проблеми. Папір ніколи не був написаний, або, принаймні, ніколи не був знайдений. У своєму повідомленні Біенеме вказав, що його мотивувала та сама проблема, яка виникла з Галтоном. У вступному абзаці його статті, перекладеному Хейде та Сенетою, йдеться:
Велику увагу було приділено можливому множенню чисельності людства; і останнім часом були опубліковані різні дуже цікаві спостереження за долею, яка нібито нависає над аристократом і середніми класами; сім'ї відомих чоловіків і т.д. ця доля, як стверджується, буде неминуче призводять до зникнення так званих 4
Набагато більш широке обговорення історії розгалужених процесів можна знайти в двох роботах Девіда Кендалла. 5
Розгалужувальні процеси служили не тільки сирої моделлю зростання населення, але й моделями для певних фізичних процесів, таких як хімічні та ядерні ланцюгові реакції.
Проблема вимирання
Перейдемо тепер до першої задачі, поставленої Галтоном (тобто до проблеми знаходження ймовірності зникнення для розгалуженого процесу). Починаємо в 0-му поколінні з 1 батька-чоловіка. У першому поколінні ми матимемо 0, 1, 2, 3,... чоловіче потомство з ймовірностями\(p_0\)\(p_1\),,\(p_2\),\(p_3\),... Якщо в першому поколінні є\(k\) потомство, то в другому поколінні буде\(X_1 + X_2 +\cdots+ X_k\) потомство, де,\(X_1\),...\(X_2\),\(X_k\) є незалежними випадковими величинами, кожна із загальним розподілом\(p_0\),\(p_1\),\(p_2\),... Цей опис дозволяє нам побудувати дерево та міру дерева для будь-якої кількості поколінь.
Приклад\(\PageIndex{1}\)
Припустимо\(p_0 = 1/2\), що\(p_1 = 1/4\),, і\(p_2 = 1/4\). Тоді деревна міра для перших двох поколінь показана на малюнку [рис. 10.1].
Рішення
Зауважимо, що ми використовуємо теорію сум незалежних випадкових величин для присвоєння гілок ймовірностей. Наприклад, якщо в першому поколінні є два потомства, ймовірність того, що в другому поколінні їх буде два, дорівнює
\[\begin{aligned} P(X_1 + X_2 = 2) &=& p_0p_2 + p_1p_1 + p_2p_0 \\ &=& \frac12\cdot\frac14 + \frac14\cdot\frac14 + \frac14\cdot\frac12 = \frac 5{16}\ .\end{aligned}\]
Ми зараз вивчаємо ймовірність того, що наш процес вимирає (тобто, що в якомусь поколінні немає потомства).
Нехай\(d_m\) буде ймовірність того, що процес згасне поколінням.\(m\) Звичайно,\(d_0 = 0\). У нашому\(d_1 = 1/2\) прикладі і\(d_2 = 1/2 + 1/8 + 1/16 = 11/16\) (див. Рис. [рис. 10.1]). Зауважте, що ми повинні додати ймовірності для всіх шляхів, які ведуть до 0\(m\) за поколінням. З визначення зрозуміло, що\[0 = d_0 \leq d_1 \leq d_2 \leq\cdots\leq 1\ .\] Отже,\(d_m\) сходиться до межі\(d\)\(0 \leq d \leq 1\), і\(d\) є ймовірність того, що процес в кінцевому підсумку згасне. Саме цю величину ми і бажаємо визначити. Ми починаємо з вираження цінності з\(d_m\) точки зору всіх можливих результатів на першому поколінні. Якщо є\(j\) потомство в першому поколінні, то щоб вимерти\(m\) го покоління, кожна з цих ліній повинна вимерти\(m - 1\) поколіннями. Так як вони протікають самостійно, така ймовірність є\((d_{m - 1})^j\). Тому
\[d_m = p_0 + p_1d_{m - 1} + p_2(d_{m - 1})^2 + p_3(d_{m - 1})^3 +\cdots\ . \label{eq 10.2.1}\]Дозвольте\(h(z)\) бути звичайною генеруючою функцією для\(p_i\):\[h(z) = p_0 + p_1z + p_2z^2 +\cdots\ .\] Використовуючи цю генеруючу функцію, ми можемо переписати рівняння [eq 10.2.1] у вигляді
\[d_m = h(d_{m - 1})\ . \label{eq 10.2.2}\]
Оскільки\(d_m \to d\) за допомогою Equation [eq 10.2.2] ми бачимо, що значення\(d\), яке ми шукаємо, задовольняє рівнянню
\[d = h(d)\ . \label{eq 10.2.3}\]
Одне з рішень цього рівняння завжди\(d = 1\), оскільки\[1 = p_0 + p_1 + p_2 +\cdots\ .\] саме тут Ватсон зробив свою помилку. Він припустив, що 1 є єдиним рішенням рівняння [ур. 10.2.3]. Щоб більш уважно вивчити це питання, спочатку відзначимо, що рішення Equation [eq 10.2.3] представляють собою перетину графіків\[y = z\] і\[y = h(z) = p_0 + p_1z + p_2z^2 +\cdots\ .\] Таким чином нам потрібно вивчити графік\(y = h(z)\). Відзначимо, що\(h(0) = p_0\). Крім того,\[h'(z) = p_1 + 2p_2z + 3p_3z^2 +\cdots\ , \label{eq 10.2.4}\] і\[h''(z) = 2p_2 + 3 \cdot 2p_3z + 4 \cdot 3p_4z^2 + \cdots\ .\] з цього ми бачимо, що для\(z \geq 0\),\(h'(z) \geq 0\) і\(h''(z) \geq 0\). Таким чином, для ненегативних\(z\),\(h(z)\) є зростаючою функцією і увігнута вгору. Тому графік\(y = h(z)\) може перетинати лінію не більше\(y = z\) ніж у двох точках. Оскільки ми знаємо, що вона повинна перетинати лінію\(y = z\) в\((1,1)\), ми знаємо, що існує лише три можливості, як показано на малюнку [рис. 10.2].
У випадку (а) рівняння\(d = h(d)\) має коріння\(\{d,1\}\) с\(0 \leq d < 1\). У другому випадку (b) він має тільки один корінь\(d = 1\). У випадку (c) він має два корені\(\{1,d\}\) де\(1 < d\). Оскільки ми шукаємо рішення\(0 \leq d \leq 1\), ми бачимо у випадках (b) та (c), що наше єдине рішення - 1. У цих випадках можна зробити висновок, що процес згасне з ймовірністю 1. Однак у випадку (а) ми сумніваємося. Треба вивчити цей випадок уважніше.
З Equation [eq 10.2.4] ми бачимо, що\[h'(1) = p_1 + 2p_2 + 3p_3 +\cdots= m\ ,\] де\(m\) очікувана кількість потомства, виробленого одним батьком. У випадку (а) ми маємо\(h'(1) > 1\), в (b)\(h'(1) = 1\) і в (c)\(h'(1) < 1\). Таким чином наші три випадки відповідають\(m > 1\)\(m = 1\), і\(m < 1\). Тепер ми припускаємо, що\(m > 1\). Нагадаємо\(d_0 = 0\), що\(d_1 = h(d_0) = p_0\),,\(d_2 = h(d_1)\),..., і\(d_n = h(d_{n - 1})\). Ми можемо побудувати ці значення геометрично, як показано на малюнку [рис. 10.3].
Ми бачимо геометрично, як зазначено для\(d_0\),\(d_1\)\(d_2\), і на\(d_3\) малюнку [рис. 10.3], що точки завжди\((d_i,h(d_i))\) будуть лежати над лінією\(y = z\). Значить, вони повинні сходитися до першого перетину кривих\(y = z\) і\(y = h(z)\) (тобто до кореня\(d < 1\)). Це призводить нас до наступної теореми.
[thm 10.3] Розглянемо процес розгалуження з\(h(z)\) генеруючою функцією для кількості потомства даного батька. \(d\)Дозволяти найменший корінь рівняння\(z = h(z)\). Якщо середня кількість\(m\) потомства, виробленого одним батьком\({} \leq 1\), є, то\(d = 1\) і процес згасає з ймовірністю 1. Якщо\(m > 1\) потім\(d < 1\) і процес згасне з ймовірністю\(d\).
Ми часто хочемо знати ймовірність того, що процес розгалуження вимирає певним поколінням, а також межу цих ймовірностей. Нехай\(d_n\) буде ймовірність вимирання з боку\(n\) го покоління. Тоді ми це знаємо\(d_1 = p_0\). Ми знаємо далі,\(h(z)\) що\(d_n = h(d_{n - 1})\) де генеруюча функція для кількості потомства, виробленого одиноким батьком. Це дозволяє легко обчислити ці ймовірності.
Програма Branch обчислює значення\(d_n\). Ми запустили цю програму протягом 12 поколінь для випадку, коли батько може виробляти не більше двох потомств, і ймовірність кількості вироблених є\(p_0 = .2\)\(p_1 = .5\), і\(p_2 = .3\). Результати наведені в табл. [табл. 10.1].
| 1 | .2 | |||||
| 2 | 3.12 | |||||
| 3 | .385203 | |||||
| 4 | .437116 | |||||
| 5 | .475879 | |||||
| 6 | .505878 | |||||
| 7 | 529713 | |||||
| 8 | .549035 | |||||
| 9 | .564949 | |||||
| 10 | .57825 | |||||
| 11 | .589416 | |||||
| 12 | .598931 |
Ми бачимо, що ймовірність вимирання 12 поколінь становить близько 0,6. Ми побачимо в наступному прикладі, що ймовірність врешті-решт вимирання становить 2/3, так що навіть 12 поколінь недостатньо, щоб дати точну оцінку цієї ймовірності.
Тепер ми припустимо, що може бути вироблено максимум два потомства. Тоді\[h(z) = p_0 + p_1z + p_2z^2\ .\] У цьому простому випадку умова\(z = h(z)\) дає рівняння\[d = p_0 + p_1d + p_2d^2\ ,\], яке задовольняється\(d = 1\) і\(d = p_0/p_2\). Таким чином, крім кореня у\(d = 1\) нас є другий корінь\(d = p_0/p_2\). Середня кількість\(m\) нащадків, вироблених одним батьком, становить\[m = p_1 + 2p_2 = 1 - p_0 - p_2 + 2p_2 = 1 - p_0 + p_2\ .\] Таким чином\(p_0 > p_2\), якщо,\(m < 1\) і другий корінь є\({} > 1\). Якщо\(p_0 = p_2\), у нас подвійний корінь\(d = 1\). Якщо\(p_0 < p_2\),\(m > 1\) а другий\(d\) корінь менше 1 і представляє ймовірність того, що процес згасне.
[іспит 10.2.3] Keyfitz 6 зібрав та проаналізував дані про продовження жіночої сімейної лінії серед японських жінок. Його оцінки щодо основного розподілу ймовірностей для кількості дітей жіночої статі, народжених японськими жінками у віці 45—49 років у 1960 році, наведені в таблиці [табл. 10.2].
\[\begin{array}{rl} p_0 &= .2092 \\ p_1 &= .2584 \\ p_2 &= .2360 \\ p_3 &= .1593 \\ p_4 &= .0828 \\ p_5 &= .0357 \\ p_6 &= .0133 \\ p_7 &= .0042 \\ p_8 &= .0011 \\ p_9 &= .0002 \\ p_{10} &= .0000\ \end{array}\]
Очікувана кількість дівчат у сім'ї тоді становить 1,837, тому\(d\) ймовірність зникнення менше 1. Якщо запустити програму Branch, ми можемо оцінити,\(d\) що насправді тільки близько .324.
Розподіл потомства
Поки ми розглянули лише першу з двох порушених Галтоном проблем, а саме ймовірність зникнення. Розглянемо тепер другу проблему, тобто розподіл чисельності\(Z_n\) потомства в\(n\) -му поколінні. Точна форма розподілу невідома хіба що в дуже особливих випадках. Однак ми побачимо, що ми можемо описати обмежуючу поведінку\(Z_n\) як\(n \to \infty\).
Спочатку показано, що\(h_n(z)\) генеруючу функцію розподілу\(Z_n\) можна отримати з\(h(z)\) будь-якого процесу розгалуження.
Нагадаємо, що значення генеруючої функції при значенні\(z\) для будь-якої випадкової величини\(X\) можна записати так, як\[h(z) = E(z^X) = p_0 + p_1z + p_2z^2 +\cdots\ .\] Тобто,\(h(z)\) є очікуваним значенням експерименту, який має результат\(z^j\) з ймовірністю\(p_j\).
Нехай\(S_n = X_1 + X_2 +\cdots+ X_n\) де кожен\(X_j\) має однаковий цілочисельний розподіл\((p_j)\) з генеруючою функцією\(k(z) = p_0 + p_1z + p_2z^2 +\cdots.\)\(k_n(z)\) Дозволяти бути генеруючою функцією\(S_n\). Потім, використовуючи одну з властивостей звичайних генеруючих функцій, розглянутих у розділі [сек 10.1], ми маємо,\[k_n(z) = (k(z))^n\ ,\] оскільки ці\(X_j\) є незалежними і всі мають однаковий розподіл.
Розглянемо тепер процес розгалуження\(Z_n\). \(h_n(z)\)Дозволяти генеруюча функція\(Z_n\). Тоді\[\begin{aligned} h_{n + 1}(z) &=& E(z^{Z_{n + 1}}) \\ &=& \sum_k E(z^{Z_{n + 1}} | Z_n = k) P(Z_n = k)\ .\end{aligned}\] якщо\(Z_n = k\), то\(Z_{n + 1} = X_1 + X_2 +\cdots+ X_k\) де,,...\(X_1\)\(X_2\),\(X_k\) є незалежними випадковими величинами із загальною генеруючою функцією\(h(z)\). Таким чином
\[E(z^{Z_{n + 1}} | Z_n = k) = E(z^{X_1 + X_2 +\cdots+ X_k}) = (h(z))^k\ ,\]
і
\[h_{n + 1}(z) = \sum_k (h(z))^k P(Z_n = k)\ .\]Але\[h_n(z) = \sum_k P(Z_n = k) z^k\ .\]
Таким чином,\[h_{n + 1}(z) = h_n(h(z))\ . \label{eq 10.2.5}\]
Якщо ми диференціюємо рівняння [eq 10.2.5] і використаємо правило ланцюга, яке ми маємо\[h'_{n+1}(z) = h'_n(h(z)) h'(z) .\]
Поклавши\(z = 1\) і використовуючи те\(h(1) = 1\), що\(h'(1) = m\), і\(h_n'(1) = m_n = {}\) середня кількість потомства в\(n\) 'му поколінні, ми маємо\[m_{n + 1} = m_n \cdot m\ .\] Таким чином\(m_2 = m \cdot m = m^2\)\(m_3 = m^2 \cdot m = m^3\),, і взагалі\[m_n = m^n\ .\]
Таким чином, для процесу розгалуження с\(m > 1\), середня кількість потомства зростає в геометричній прогресії зі швидкістю\(m\).
Приклад\(\PageIndex{2}\)
Для процесу розгалуження Приклад [іспит 10.2.1] ми маємо\[\begin{aligned} h(z) &=& 1/2 + (1/4)z + (1/4)z^2\ , \\ h_2(z) &=& h(h(z)) = 1/2 + (1/4)[1/2 + (1/4)z + (1/4)z^2] \\ &=& + (1/4)[1/2 + (1/4)z + (1/4)z^2]^2 \\ &=& 11/16 + (1/8)z + (9/64)z^2 + (1/32)z^3 + (1/64)z^4\ .\end{aligned}\] Імовірності кількості потомства у другому поколінні узгоджуються з тими, що отримані безпосередньо з деревної міри (див. Рис.
Зрозуміло, що навіть в простому випадку максимум двох нащадків ми не можемо легко провести розрахунок цим\(h_n(z)\) методом. Однак є один особливий випадок, в якому це можна зробити.
Приклад\(\PageIndex{2}\)
Припустимо, що ймовірності\(p_1\)\(p_2\),,... утворюють геометричний ряд:\(p_k = bc^{k - 1}\)\(k = 1\),, 2,..., з\(0 < b \leq 1 - c\) і\(0 < c < 1\). Тоді у нас є\[\begin{aligned} p_0 &=& 1 - p_1 - p_2 -\cdots \\ &=& 1 - b - bc - bc^2 -\cdots \\ &=& 1 - \frac b{1 - c}\ .\end{aligned}\] Генеруюча функція\(h(z)\) для цього розподілу є\[\begin{aligned} h(z) &=& p_0 + p_1z + p_2z^2 +\cdots \\ &=& 1 - \frac b{1 - c} + bz + bcz^2 + bc^2z^3 +\cdots \\ &=& 1 - \frac b{1 - c} + \frac{bz}{1 - cz}\ .\end{aligned}\] З цього ми знаходимо\[h'(z) = \frac{bcz}{(1 - cz)^2} + \frac b{1 - cz} = \frac b{(1 - cz)^2}\] і\[m = h'(1) = \frac b{(1 - c)^2}\ .\] Ми знаємо, що якщо\(m \leq 1\) процес напевно вимре і\(d = 1\). Щоб знайти ймовірність,\(d\) коли\(m > 1\) ми повинні знайти корінь\(d < 1\) рівняння\[z = h(z)\ ,\] або\[z = 1 - \frac b{1 - c} + \frac{bz}{1 - cz}.\] Це призводить нас до квадратного рівняння. Ми знаємо, що\(z = 1\) це одне рішення. Інший виявляється, щоб бути\[d = \frac{1 - b - c}{c(1 - c)}.\] Легко перевірити, що\(d < 1\) саме тоді\(m > 1\).
Можна в цьому випадку знайти дистрибутив\(Z_n\). Це робиться шляхом першого знаходження генеруючої функції\(h_n(z)\). 7 Результат для\(m \ne 1\) є:\[h_n(z) = 1 - m^n \left[\frac{1 - d}{m^n - d}\right] + \frac{m^n \left[\frac{1 - d}{m^n - d}\right]^2 z} {1 - \left[\frac{m^n - 1}{m^n - d}\right]z}\ .\] Коефіцієнти повноважень\(z\) дають розподіл для\(Z_n\):
\[P(Z_n = 0) = 1 - m^n\frac{1 - d}{m^n - d} = \frac{d(m^n - 1)}{m^n - d}\]і\[P(Z_n = j) = m^n \Bigl(\frac{1 - d}{m^n - d}\Bigr)^2 \cdot \Bigl(\frac{m^n - 1}{ m^n - d}\Bigr)^{j - 1},\]
для\(j \geq 1\).
[іспит 10.2.4.5] Давайте повторно вивчимо дані Keyfitz, щоб побачити, чи розподіл типу, розглянутого в прикладі [іспит 10.2.4] може бути розумно використаний як модель для цієї популяції. Ми повинні були б оцінити з даних параметри\(b\) і\(c\) для формули\(p_k = bc^{k - 1}\). Нагадаємо, що\[m = \frac b{(1 - c)^2} \label{eq 10.2.7}\] і ймовірність\(d\) того, що процес згасне, є\[d = \frac{1 - b - c}{c(1 - c)}\ . \label{eq 10.2.8}\] Рішення рівняння [ур. 10.2.7] і [eq 10.2.8] для\(b\) і\(c\) дає\[c = \frac{m - 1}{m - d}\] і\[b = m\Bigl(\frac{1 - d}{m - d}\Bigr)^2\ .\]
Ми будемо використовувати значення 1.837 для\(m\) і .324 для\(d\) цього ми знайшли в прикладі Keyfitz. Використовуючи ці значення, отримаємо\(b = .3666\) і\(c = .5533\). Зверніть увагу\((1 - c)^2 < b < 1 - c\), що, як потрібно. У таблиці [табл. 10.3] ми наведемо для порівняння\(p_0\) ймовірності\(p_8\), що обчислюються геометричним розподілом проти емпіричних значень.
| Геометричний | ||
| \(p_j\) | Дані | Модель |
| 0 | .2092 | .1816 |
| 1 | .2584 | 3.66 |
| 2 | .2360 | .2028 |
| 3 | .1593 | .1122 |
| 4 | .0828 | .0621 |
| 5 | .0357 | .0344 |
| 6 | .0133 | .0190 |
| 7 | .0042 | .0105 |
| 8 | .0011 | .0058 |
| 9 | .0002 | .0032 |
| 10 | .0000 | .0018 |
Геометрична модель, як правило, сприяє більшій кількості потомства, але досить схожа, щоб показати, що цей модифікований геометричний розподіл може бути доцільним для використання для досліджень такого роду.
Нагадаємо,\(S_n = X_1 + X_2 +\cdots+ X_n\) що якщо сума незалежних випадкових величин з однаковим розподілом, то Закон великих чисел стверджує, що\(S_n/n\) сходиться до константи, а саме\(E(X_1)\). Природно запитати, чи існує подібна гранична теорема для процесів розгалуження.
Розглянемо процес розгалуження з\(Z_n\) представленням кількості потомства після\(n\) поколінь. Тоді ми побачили, що очікуване значення\(Z_n\) є\(m^n\). Таким чином, ми можемо масштабувати випадкову величину\(Z_n\), щоб мати очікуване значення 1, враховуючи випадкову величину.\[W_n = \frac{Z_n}{m^n}\ .\]
У теорії розгалужених процесів доведено, що ця випадкова величина\(W_n\) буде прагнути до межі, як\(n\) прагне до нескінченності. Однак, на відміну від випадку Закону великих чисел, де ця межа є постійною, для процесу розгалуження граничне значення випадкових величин само по собі\(W_n\) є випадковою величиною.
Хоча ми не можемо довести цю теорему тут, ми можемо проілюструвати її моделюванням. Це вимагає невеликого догляду. Коли процес розгалуження виживає, кількість потомства здатне отримати дуже велике. Якщо в даному поколінні є 1000 нащадків, потомство наступного покоління є результатом 1000 випадкових подій, і для імітації цих 1000 експериментів знадобиться деякий час. Однак, оскільки кінцевим результатом є сума 1000 незалежних експериментів, ми можемо використовувати центральну граничну теорему, щоб замінити ці 1000 експериментів одним експериментом з нормальною щільністю, що має відповідне середнє значення та дисперсію. Програма BranchingSimulation здійснює цей процес.
Ми запустили цю програму для прикладу Keyfitz, провівши моделювання 10 та графікуючи результати на малюнку [рис. 10.4].
Очікувана кількість жіночого потомства на самку становить 1,837, так що ми графікуємо результат для випадкових величин\(W_n = Z_n/(1.837)^n\). Для трьох моделювань процес вимер, що відповідає значенню,\(d = .3\) яке ми знайшли для цього прикладу. Для інших семи моделювань значення\(W_n\) має тенденцію до граничного значення, яке відрізняється для кожного моделювання.
[іспит 10.2.4.6] Тепер ми розглянемо випадкову величину\(Z_n\) більш уважно для випадку\(m < 1\) (див. Приклад [іспит 10.2.4]). Виправте значення\(t > 0\); нехай\([tm^n]\) буде ціла частина\(tm^n\). Тоді\[\begin{aligned} P(Z_n = [tm^n]) &=& m^n (\frac{1 - d}{m^n - d})^2 (\frac{m^n - 1}{m^n - d}) ^{[tm^n] - 1} \\ &=& \frac1{m^n}(\frac{1 - d}{1 - d/m^n})^2 (\frac{1 - 1/m^n} {1 - d/m^n})^{tm^n + a}\ ,\end{aligned}\] де\(|a| \leq 2\). Таким чином, як\(n \to \infty\),\[m^n P(Z_n = [tm^n]) \to (1 - d)^2 \frac{e^{-t}}{e^{-td}} = (1 - d)^2 e^{-t(1 - d)}\ .\] For\(t = 0\),\[P(Z_n = 0) \to d\ .\] Ми можемо порівняти цей результат з центральною граничною теоремою для сум\(S_n\) цілозначних незалежних випадкових величин (див. Теорема [thm 9.3.5]), яка стверджує, що якщо\(t\) є цілим числом і\(u = (t - n\mu)/\sqrt{\sigma^2 n}\), то як\(n \to \infty\), \[\sqrt{\sigma^2 n}\, P(S_n = u\sqrt{\sigma^2 n} + \mu n) \to \frac1{\sqrt{2\pi}} e^{-u^2/2}\ .\]Ми бачимо, що форма цих висловлювань досить схожа. Можна довести граничну теорему для загального класу розгалужених процесів, яка стверджує, що при відповідних гіпотезах, як,\[m^n P(Z_n = [tm^n]) \to k(t)\ ,\] для\(n \to \infty\), і\[P(Z_n = 0) \to d\ .\] Однак\(t > 0\), на відміну від центральної граничної теореми для сум незалежних випадкових величин, функція\(k(t)\) буде залежати на основний розподіл, який визначає процес. Його форма відома лише дуже нечисленними прикладами, схожими на той, який ми тут розглянули.
Ланцюг Лист Проблема
[іспит 10.2.5] Цікавий приклад процесу розгалуження запропонував Free Huizinga. 8 У 1978 році в Каліфорнії почався лист ланцюга під назвою «Золоте коло», який, як вважають, розпочався в Каліфорнії, через всю країну потрапив до театрального району Нью-Йорка. Мережа вимагала від учасника купити лист, що містить список з 12 імен за 100 доларів. Покупець віддає 50 доларів людині, у якого було придбано лист, а потім відправляє 50 доларів тому, чиє ім'я знаходиться у верхній частині списку. Потім покупець перекреслює ім'я у верхній частині списку і додає своє власне ім'я внизу в кожній букві, перш ніж воно буде продано знову.
Давайте спочатку припустимо, що покупець може продати лист тільки одній особі. Якщо ви купуєте лист, ви захочете обчислити очікуваний виграш. (Ми ігноруємо тут той факт, що передача ланцюгових листів через пошту є федеральним правопорушенням з певними очевидними наслідками покарання.) Припустимо, що кожна залучена людина має\(p\) ймовірність продажу листа. Тоді ви отримаєте 50 доларів з ймовірністю\(p\) і ще 50 доларів, якщо лист буде продано 12 людям, з тих пір ваше ім'я піднялося б на вершину списку. Це відбувається з ймовірністю\(p^{12}\), і тому ваші очікувані виграші є\(-100 + 50p + 50p^{12}\). Таким чином, ланцюжок в даній ситуації є вкрай несприятливою грою.
Розумніше було б дозволити кожній особі зробити копію списку і спробувати продати лист як мінімум 2 іншим людям. Тоді у вас буде шанс повернути свої 100 доларів на ці продажі, і якщо будь-який з листів продається 12 разів, ви отримаєте бонус у розмірі 50 доларів за кожен з цих випадків. Ми можемо розглядати це як процес розгалуження з 12 поколіннями. Члени першого покоління - це листи, які ви продаєте. Друге покоління складається з листів, що продаються членами першого покоління, і так далі.
Припустимо, що ймовірності того, що кожна людина продає літери 0, 1 або 2 інші\(p_0\), є\(p_1\), і\(p_2\), відповідно. Нехай\(Z_1\),\(Z_2\),...,\(Z_{12}\) бути кількістю букв у перших 12 поколіннях цього процесу розгалуження. Тоді ваш очікуваний виграш,\[50(E(Z_1) + E(Z_{12})) = 50m + 50m^{12}\ ,\] де\(m = p_1 + 2p_2\) очікувана кількість листів, які ви продали. Таким чином, щоб бути сприятливим, ми просто маємо\[50m + 50m^{12} > 100\ ,\] або\[m + m^{12} > 2\ .\] Але це буде правдою, якщо і тільки якщо\(m > 1\). Ми бачили, що це станеться в квадратичному випадку тоді і лише тоді\(p_2 > p_0\). Припустимо, наприклад\(p_0 = .2\), що\(p_1 = .5\), і\(p_2 = .3\). Тоді\(m = 1.1\) і ланцюжок буде сприятливою грою. Ваш очікуваний прибуток буде\[50(1.1 + 1.1^{12}) - 100 \approx 112\ .\]
Імовірність того, що ви отримаєте хоча б один платіж від 12-го покоління, є\(1 - d_{12}\). Ми знаходимо з нашої програми Відділення, що\(d_{12} = .599\). Таким чином,\(1 - d_{12} = .401\) є ймовірність того, що ви отримаєте якийсь бонус. Максимум, що ви могли б отримати від ланцюжка, було б,\(50(2 + 2^{12}) = 204{,}900\) якби всі успішно продали дві літери. Звичайно, не завжди можна розраховувати на те, що так пощастить. (Яка ймовірність цього?)
Щоб імітувати цю гру, нам потрібно лише імітувати процес розгалуження протягом 12 поколінь. За допомогою трохи зміненої версії нашої програми branchingSimulation ми провели двадцять таких симуляцій, давши результати, наведені в таблиці [табл. 10.4].
Відзначимо, що нам досить пощастило на декількох пробігах, але ми вийшли вперед лише трохи менше половини часу. Процес вимер дванадцятим поколінням в 12 з 20 експериментів, добре згодні з тією ймовірністю,\(d_{12} = .599\) яку ми розрахували за допомогою програми Branch.
\[\begin{tabular}{rrrrrrrrrrrrr} $Z_{1}$&$Z_{2}$&$ Z_{3}$& $Z_{4}$& $Z_{5}$& $Z_{6}$& $Z_{7}$& $Z_{8}$& $Z_{9}$&$ Z_{10}$&$ Z_{11}$& $Z_{12}$& Profit\\\hline 1 &0 &0 &0 &0 & 0 & 0 &0 &0 &0 &0 &0 &-50\\ 1 &1 &2 &3 &2 & 3 & 2 &1 &2 &3 &3 &6 &250\\ 0 &0 &0 &0 &0 & 0 & 0 &0 &0 &0 &0 &0 &-100\\ 2 &4 &4 &2 &3 & 4 & 4 &3 &2 &2 &1 &1 & 50\\ 1 &2 &3 &5 & 4 & 3 & 3 &3 &5 &8 &6 &6 & 250\\ 0 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 &-100\\ 2 &3 &2 &2 & 2 & 1 & 2 &3 &3 &3 &4 &6 & 300\\ 1 &2 &1 &1 & 1 & 1 & 2 &1 &0 &0 &0 &0 & -50\\ 0 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 &-100\\ 1 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 2 &3 &2 &3 & 3 & 3 & 5 &9 &12 &12 &13 &15 & 750\\ 1 &1 &1 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 1 &2 &2 &3 & 3 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 1 &1 &1 &1 & 2 & 2 & 3 &4 &4 &6 &4 &5 & 200\\ 1 &1 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 1 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 1 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 1 &1 &2 &3 & 3 & 4 & 2 &3 &3 &3 &3 &2 & 50\\ 1 &2 &4 &6 & 6 & 9 &10 &13 &16 &17 &15 &18 & 850\\ 1 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ \end{tabular}\]
Давайте змінимо припущення щодо нашого ланцюгового листа, щоб дозволити покупцеві продавати лист якомога більшій кількості людей, а не максимум двом. Будемо вважати, по суті, що у людини велика\(N\) кількість знайомих і невелика\(p\) ймовірність умовити будь-якого з них купити лист. Тоді розподіл за кількістю букв, які вона продає, буде двономіальним розподілом зі середнім\(m = Np\). Оскільки\(N\) він великий і\(p\) малий, можна припустити, що ймовірність того,\(p_j\) що індивід продає лист\(j\) людям, дається\[p_j = \frac{e^{-m} m^j}{j!}\ .\] розподілом Пуассона. Генеруюча функція для розподілу Пуассона є\[\begin{aligned} h(z) &=& \sum_{j = 0}^\infty \frac{e^{-m} m^j z^j}{j!} \\ &=& e^{-m} \sum_{j = 0}^\infty \frac{m^j z^j}{j!} \\ &=& e^{-m} e^{mz} = e^{m(z - 1)}\ .\end{aligned}\]
Очікувана кількість листів, які передає людина\(m\), є, і знову ж таки, щоб бути сприятливими, ми повинні мати\(m > 1\). Припустимо ще раз, що\(m = 1.1\). Тоді ми зможемо знову знайти ймовірність\(1 - d_{12}\) бонусу від Відділення. Результат - .232. Хоча очікувані виграші однакові, дисперсія в цьому випадку більше, і покупець має більше шансів на досить великий прибуток. Ми знову провели 20 симуляцій, використовуючи розподіл Пуассона із середнім значенням 1.1. Результати наведені в табл. [табл. 10.5].
\[\begin{tabular}{rrrrrrrrrrrrr} $Z_{1}$&$Z_{2}$&$ Z_{3}$& $Z_{4}$& $Z_{5}$& $Z_{6}$& $Z_{7}$& $Z_{8}$& $Z_{9}$&$ Z_{10}$&$ Z_{11}$& $Z_{12}$& Profit\\\hline 1 &2 &6 &7 &7 & 8 & 11 &9 &7 &6 &6 &5 & 200\\ 1 &0 &0 &0 &0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 1 &0 &0 &0 &0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 1 &1 &1 &0 &0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 0 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -100\\ 1 &1 &1 &1 & 1 & 1 & 2 &4 &9 &7 &9 &7 & 300\\ 2 &3 &3 &4 & 2 & 0 & 0 &0 &0 &0 &0 &0 & 0\\ 1 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 2 &1 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & 0\\ 3 &3 &4 &7 & 11 & 17 & 14 &11 &11 &10 &16 &25 & 1300\\ 0 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -100\\ 1 &2 &2 &1 & 1 & 3 & 1 &0 &0 &0 &0 &0 & -50\\ 0 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -100\\ 2 &3 &1 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & 0\\ 3 &1 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & 50\\ 1 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ 3 &4 &4 &7 &10 &11 & 9 &11 &12 &14 &13 &10 & 550\\ 1 &3 &3 &4 & 9 & 5 & 7 &9 &8 &8 &6 &3 & 100\\ 1 &0 &4 &6 & 6 & 9 &10 &13 &0 &0 &0 &0 & -50\\ 1 &0 &0 &0 & 0 & 0 & 0 &0 &0 &0 &0 &0 & -50\\ \end{tabular}\]
Відзначимо, що, як і раніше, ми виходили попереду менше половини часу, але у нас була і одна велика прибуток. Тільки в 6 з 20 випадків ми отримали будь-який прибуток. Це знову ж таки в розумній згоді з нашим розрахунком ймовірності .232 для цього.
i [exer 10.2.1] Нехай\(Z_1\),,...\(Z_2\),\(Z_N\) опишіть процес розгалуження, в якому кожен батько має\(j\) потомство з ймовірністю\(p_j\). Знайти ймовірність того\(d\), що процес в кінцевому підсумку згасне, якщо
- \(p_0 = 1/2\),\(p_1 = 1/4\), і\(p_2 = 1/4\).
- \(p_0 = 1/3\),\(p_1 = 1/3\), і\(p_2 = 1/3\).
- \(p_0 = 1/3\),\(p_1 = 0\), і\(p_2 = 2/3\).
- \(p_j = 1/2^{j + 1}\), для\(j = 0\), 1, 2,...
- \(p_j = (1/3)(2/3)^j\), для\(j = 0\), 1, 2,...
- \(p_j = e^{-2} 2^j/j!\), для\(j = 0\), 1, 2,... (оцінювати\(d\) чисельно).
i [exer 10.2.2] Нехай\(Z_1\),,...\(Z_2\),\(Z_N\) опишіть процес розгалуження, в якому кожен батько має\(j\) потомство з ймовірністю\(p_j\). Знайти ймовірність того\(d\), що процес згасне, якщо
- \(p_0 = 1/2\),\(p_1 = p_2 = 0\), і\(p_3 = 1/2\).
- \(p_0 = p_1 = p_2 = p_3 = 1/4\).
- \(p_0 = t\),\(p_1 = 1 - 2t\),\(p_2 = 0\), і\(p_3 = t\), де\(t \leq 1/2\).
i [exer 10.2.3] У задачі листа ланцюга (див. Приклад [іспит 10.2.5]) знайти очікуваний прибуток, якщо
- \(p_0 = 1/2\),\(p_1 = 0\), і\(p_2 = 1/2\).
- \(p_0 = 1/6\),\(p_1 = 1/2\), і\(p_2 = 1/3\).
Покажіть, що якщо\(p_0 > 1/2\), ви не можете розраховувати на отримання прибутку.
i [exer 10.2.4] Нехай\(S_N = X_1 + X_2 +\cdots+ X_N\), де є незалежними випадковими величинами із загальним розподілом, що мають генеруючу функцію\(f(z)\).\(X_i\) Припустимо, що\(N\) це ціле значення випадкової величини, незалежної від усіх\(X_j\) і має генеруючу функцію\(g(z)\). Показати, що генеруюча функція для\(S_N\) є\(h(z) = g(f(z))\).: Використовуйте той факт, що\[h(z) = E(z^{S_N}) = \sum_k E(z^{S_N} | N = k) P(N = k)\ .\]
i [exer 10.2.5] Ми бачили, що якщо генеруюча функція для потомства одного з батьків є\(f(z)\), то генеруюча функція для кількості потомства після двох поколінь дається\(h(z) = f(f(z))\). Поясніть, як це випливає з результату вправи [exer 10.2.4].
i [exer 10.2.6] Розглянемо процес черги таким чином, що в кожну хвилину або 1 або 0 клієнти прибувають з ймовірністю\(p\) або\(q = 1 - p\), відповідно. (Номер\(p\) називається.) Коли клієнт починає обслуговування, вона закінчує в наступну хвилину з ймовірністю\(r\). Номер\(r\) називається.) Таким чином, коли клієнт починає обслуговуватися вона закінчить обслуговується в\(j\) лічені хвилини з ймовірністю\((1 - r)^{j -1}r\), для\(j = 1\), 2, 3,...
- Знайдіть генеруючу функцію\(f(z)\) для кількості клієнтів, які прибувають за одну хвилину, і генеруючу функцію\(g(z)\) за проміжок часу, який людина проводить в обслуговуванні після того, як вона починає обслуговування.
i [exer 10.2.7] Розглянемо a, розглядаючи потомство клієнта, щоб бути клієнтами, які прибувають, поки вона обслуговується. Використовуючи Вправа [exer 10.2.4], показати, що генеруюча функція для нашого процесу розгалуження клієнтів є\(h(z) = g(f(z))\).
i [exer 10.2.8] Якщо ми почнемо процес розгалуження з приходом першого клієнта, то проміжок часу, поки процес розгалуження не згасне, буде для сервера. Знайдіть умову з точки зору швидкості прибуття і швидкості обслуговування, яке буде гарантувати, що сервер в кінцевому підсумку матиме час, коли він не зайнятий.
i [exer 10.2.9] Нехай\(N\) буде очікувана загальна кількість потомства в процесі розгалуження. \(m\)Дозволяти бути середньою кількістю потомства одного з батьків. Покажіть, що\[N = 1 + \left(\sum p_k \cdot k\right) N = 1 + mN\] і, отже, що\(N\) є кінцевим, якщо і тільки\(m < 1\) тоді і в цьому випадку\(N = 1/(1 - m)\).
i [exer 10.2.10] Розглянемо процес розгалуження таким чином, що кількість потомства батька\(j\) з ймовірністю\(1/2^{j + 1}\) для\(j = 0\), 1, 2,...
- Використовуючи результати Прикладу [іспиту 10.2.4] показують, що ймовірність наявності\(j\) потомства в\(n\) -му поколінні дорівнює\[p_j^{(n)} = \left \{ \begin{array}{ll} \frac{1}{n(n + 1)} (\frac {n}{n + 1})^j, & \mbox{if $ j \geq 1$}, \\ \frac {n}{n + 1}, & \mbox{if $ j = 0$}.\end{array}\right.\]
- Покажіть, що ймовірність того, що процес згасне саме при генерації, є\(1/n(n + 1)\).\(n\)
- Покажіть, що очікуваний термін життя нескінченний, хоча\(d = 1\).