Производящие функции. Ветвящийся процесс Гальтона-Ватсона

ПредупреждениеЧерновик

Этот конспект ещё находится в процессе редактуры: в тексте могут встречаться опечатки, неточности и локально не проработанные места. Если что-то нашли — сообщите, пожалуйста, автору (контакты на странице курса).

Распределения случайных величин, принимающих значения в \(\mathbb {Z}_+ = \left\{ 0,1,2,\ldots \right\}\), удобно анализировать через производящие функции. Общая идея очень похожа на метод харфункций: перейти от распределений (т.е. от числовых отображений на сигма-алгебрах), с которыми не очень удобно работать, к функциям на числах.

1 Производящие функции

Напомним, что харфункция для случайной величины определяется так:

\[ \varphi _{\xi }(t) := \mathbb {E}\left[e^{it\xi }\right] = \int _{\mathbb {R}} e^{itx} \; \; \mathbf{P}_{\xi }\left(dx\right) \]

(второе равенство – это замена переменных в интеграле Лебега). Это отображение из \(\mathbb {R}\) в \(\mathbb {C}\), т.е. функция на числах. Причем она однозначно характеризует распределение \(\mathbf{P}_{\xi }\) (напомним, \(\mathbf{P}_{\xi }(B) := \mathbb {P}\left(\xi \in B\right)\), \(B \in \mathscr {B}\left(\mathbb {R}\right)\)) случайной величины \(\xi\).

Если \(\xi\) принимает значения в \(\mathbb {Z}_+\), то удобнее оказывается не брать комплексную экспоненту, а просто составить степенной ряд с вероятностями \(\xi\) попасть в \(0,1,2,\ldots\):

\[ G_{\xi }(z) := \mathbb {E}\left[z^{\xi }\right] = z^0 \cdot \mathbb {P}\left(\xi = 0\right) + z^{1} \cdot \mathbb {P}\left(\xi = 1\right) + \ldots = \sum _{n=0}^{+\infty } \mathbb {P}\left(\xi = n\right) \cdot z^n \]

\(G_{\xi }\) – это производящая функция для \(\xi\). Она определена для тех \(z \in \mathbb {C}\), для которых ряд сходится. Преимущество такого подхода (в частности, того, что \(z\) берется комплексным) в том, что нам становятся доступны методы работы со степенными рядами.

Заметим, что этот степенной ряд сходится абсолютно как минимум для всех \(z \in \mathbb {C}\) с \(\left|z\right| \leq 1\). Мы, как правило, будем рассматривать \(z \in [0,1] \subset \mathbb {R}\). Заметим, что в этом случае значения \(G_{\xi }(z)\) также лежат в отрезке \([0,1]\).

В чуть более общем случае производящая функция для последовательности действительных чисел \(a = (a_{0}, a_{1}, \ldots )\) – это (формальный, т.е. изначально не очень понятно, где и как он сходится) степенной ряд с данными коэффициентами:

\[ G_{a}(z) := \sum _{k=0}^{+\infty } a_k z^{k} \]

ExampleПример 1

Дано распределение.

1. \(X = k_0 \in \mathbb {Z}_+\) п.н.

2. \(X \sim \operatorname {Ber}(p)\)

3. \(X \sim \operatorname {Pois}(\lambda )\)

4. \(X \sim \operatorname {Geom}(p)\) Вычислите производящую функцию, определите радиус сходимости.

SolutionРешение

Enum-item(1)

\(G_{\xi }(z) = z^{k_0}\). Радиус сходимости: \(+\infty\).

Enum-item(2)

\(G_{\xi }(z) = (1-p) + pz\). Радиус сходимости: \(+\infty\).

Enum-item(3)

\(G_{\xi }(z)= \mathbb {E}\left[z^{\xi }\right]=\sum_{k=0}^{\infty } z^{k} \frac{\lambda^{k}}{k !} e^{-\lambda }=e^{-\lambda } \sum_{k=0}^{\infty } \frac{(z \lambda )^{k}}{k !}=e^{\lambda (z-1)}\). Радиус сходимости: \(+\infty\).

Enum-item(4)

\(G_{\xi }(z)= \mathbb {E}\left[z^{\xi }\right]=\sum_{k=0}^{\infty } z^{k} (1-p)^kp = p\cdot \sum_{k=0}^{\infty } \left(z(1-p)\right)^k = p \cdot \frac{1}{1 - z(1-p)}\). Радиус сходимости: \(\left|z(1-p)\right| < 1\) \(\iff\) \(\left|z\right| < \frac{1}{1-p}\).

Теорема 1 (Основные свойства производящих функций) Выделим основные свойства производящих функций.

1. \(G_{\xi }(z)\) непрерывно дифференцируема бесконечное число раз в области \(\{ |z|<1\}\);

2. По производящей функции можно однозначно восстановить функцию вероятностей:

   \[ \mathbb {P}\left(\xi = k\right) = \frac{G_\xi ^{(k)}(0)}{k!} \]

3. Как следствие из предыдущего пункта получаем, что производящая функция однозначно задает распределение на \(\mathbb {Z}_+ \cup \left\{ +\infty \right\}\). Т.е. если 2 сл. величины \(\xi , \eta\), принимающие значения в \(\mathbb {Z}_+ \cup \left\{ +\infty \right\}\), имеют равные произв. функции (\(G_{\xi }(z) = G_\eta (z)\) при \(z \in [0,1)\)), то \(\operatorname {Law}\left(\xi \right) = \operatorname {Law}\left(\eta \right)\).

4. Если \(\xi\) и \(\eta\) независимы, то \(G_{\xi +\eta }(z)=G_{\xi }(z) \cdot G_{\eta }(z)\);

5. Пусть \(\mathbb {P}\left(\xi < +\infty \right) = 1\). Тогда имеем

   \[ 1 = G_{\xi }(1-) = \lim _{x \to 1-0}G_{\xi }(x) \]

   1-й момент:

   \[ \mathbb {E}\left[\xi \right] = G_{\xi }^{\prime }(1-) = \lim _{x \to 1-0}G^{\prime }_{\xi }(x) \]

   В общем случае \(k\)-й факториальный момент \(\mathbb {E}\left[\xi (\xi -1) \cdot \ldots \cdot (\xi - k + 1)\right]\):

   \[ \mathbb {E}\left[\frac{\xi !}{(\xi - k)!}\right] = G_{\xi }^{(k)}(1-) = \lim _{x \to 1-0}G^{(k)}_{\xi }(x) \]

   Следовательно, дисперсия:

   \[ \operatorname {Var}\left[\xi \right] = G_{\xi }^{\prime \prime }(1-) + G_{\xi }^{\prime }(1-) - \left[ G_{\xi }^{\prime }(1-) \right]^2 \]

   В общем случае \(k\)-й момент:

   \[ \mathbb {E}\left[\xi ^k\right] = \lim _{x \to 1-0} \left( \left(x \frac{d}{dx}\right)^k G_{\xi }(x) \right) \]

В этом разделе мы рассматривали случайные величины \(X\), принимающие только конечные (целые неотрицательные) значения, и, следовательно, их производящие функции \(G_X\) удовлетворяют условию \(G_X(1)=1\). Однако мы уже сталкивались со случайными величинами, принимающими значения в \(\left\{ 0,1,2,\ldots \right\} \cup \left\{ +\infty \right\}\) (см., например, момент достижения \(1\) для случайного блуждания, стартующего в нуле). Для таких случайных величин \(G_X(s)= \mathbb {E}\left[s^X\right]\) сходится при \(|s|<1\), и, кроме того,

\[ \lim _{s \uparrow 1} G_X(s)=\sum _k \mathbb {P}(X=k)=1-\mathbb {P}(X=+\infty ) \]

Мы больше не можем найти моменты \(X\) через \(G_X\); разумеется, все они равны \(+\infty\). Если \(\mathbb {P}(X=+\infty )>0\), то говорят, что \(X\) – несобственная (англ. defective) случайная величина, а ее распределение – несобственное. (Осторожно: не путать с вырожденным распределением – так называют распределение константы.)

2 Определение ветвящегося процесса

Модель ветвящихся процессов была впервые предложена Ф. Гальтоном и Г. Ватсоном в 1873 году в связи с анализом вырождения аристократических фамилий Великобритании.

Физическая модель: в дискретные моменты времени частицы распадаются на случайное количество таких же частиц. Число потомков каждой частицы имеет одно и то же распределение.

Математическая модель: пусть \(\xi\) – случайная величина со значениями в \(\mathbb {Z}_{+} = \left\{ 0,1,2,\ldots \right\}\), пусть

\[ \left\{ \xi _{k}^{(n)} , \; k, n \in \mathbb {N}\right\} = \left\{ \begin{array}{cccc} \xi _{1}^{(1)} & \xi _{2}^{(1)} & \xi _{3}^{(1)} & \cdots \\ \xi _{1}^{(2)} & \xi _{2}^{(2)} & \xi _{3}^{(2)} & \cdots \\ \vdots & \vdots & \vdots & \ddots \\ \end{array}\right\} \]

– набор независимых случайных величин с тем же распределением, что и \(\xi\). Определим дискретный процесс \((X_n, \; n \in \mathbb {Z}_+)\) индуктивно:

\[ X_{0} := 1, \qquad X_{n} := \sum _{k=1}^{X_{n-1}} \xi _{k}^{(n)}, n \geqslant 1 \]

• \(\xi_{k}^{(n)}\) – это количество потомков \(k\)-го представителя из поколения \((n-1)\) (в поколении \(n\), соотв.).

• \(X_{n}\) – это общее количество представителей в \(n\)-м поколении. Оно считается как сумма потомков каждого представителя из поколения \(n-1\).

Процесс \(\left(X_{n}, n \in \mathbb {Z}_{+}\right)\) называется ветвящимся процессом Гальтона-Ватсона с законом размножения частиц \(\xi\).

Понятно, что в реальной жизни представитель какого бы то ни было биологического вида редко может самостоятельно порождать потомков, как в нашей модели. Однако преимущество в том, что наша модель более простая, по сравнению с моделями, учитывающими пары. Также она подходит для случая, когда мы хотим исследовать один конкретный род и его потомков. В данном случае каждый представитель порождает потомков в рамках рода «самостоятельно», т.к. супруг/супруга все время приходят со стороны, не из рода.

Пример ветвящегося процесса (для некоторого фиксированного элементарного исхода ω₀). Наведите курсор на узел или стрелку, чтобы увидеть подробности.

3 Распределение ветвящегося процесса

Пусть \(X=\left(X_{n}, n \in \mathbb {Z}_+\right)\) – это ветвящийся процесс Гальтона-Ватсона с законом размножения частиц \(\xi\).

Лемма 1 Между производящими функциями элементов процесса \(X\) имеют место следующие рекуррентные соотношения: \[ G_{X_{n+1}} = G_{X_{n}} \circ G_{\xi } \] т.е. \(G_{X_{n+1}}(z)=G_{X_{n}}\left(G_{\xi }(z)\right)\).

Как следствие получаем, что \(G_{X_{n}} = G_{\xi } \underbrace{\circ \dots \circ }_{n \text{ раз}} G_{\xi }\).

ExampleПример 2

Доказать лемму Лемма 1.

SolutionРешение

3 похожих решения.

• Имеем \(X_{n+1} = \sum_{k=1}^{X_{n}} \xi_k^{(n+1)}\). Основная проблема работы с этим объектом состоит в том, что в сумме случайны не только сами слагаемые \(\xi_k^{(n+1)}\), но и их количество \(X_n\). Преодолеть эту проблему можно, если брать условные вероятности и матожидания по \(X_n\), т.е. как-бы фиксировать \(X_n\). В таком случае слагаемых в сумме уже будет фиксированное число:

  \[ \begin{align} G_{X_{n+1}}(z) = \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}\right] & = \mathbb {E}\left[\mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}|X_n\right]\right] \stackrel{*}{=} \\ \notag & \stackrel{*}{=} \mathbb {E}\left[G_\xi ^{X_n}(z)\right] = G_{X_n} ( G_\xi (z) ) \end{align} \tag{1}\]

  Равенство \(*\) выполнено, поскольку если \(X_n\) известно (и равно \(k_0\), например), то сумма \(\xi^{(n+1)}_1 + \dots + \xi^{(n+1)}_{X_n}\) равна \(\xi^{(n+1)}_1 + \dots + \xi^{(n+1)}_{k_0}\) и превращается просто в сумму \(k_0\) независимых одинаково распределенных случайный величин с распределением \(\operatorname {Law}\left(\xi \right)\).

• Чуть подробнее распишем Уравнение 1. \(X_n\) – дискретная случайная величина, \(\mathbb {Z}_+\) – носитель распределения, значит условное матожидание по ней можно записать в явном виде. Для фиксированного \(z \in \mathbb {C}, \; \left|z\right| \leq 1\) имеем

  \[ \begin{align} \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}|X_n\right] & \stackrel{\text{п.н.}}{=} \sum _{k \in \mathbb {Z}_+} \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}} \mid X_n = k\right] \\ & \quad \cdot \; \mathbb {1}_{X_n = k} \enclose {circle}{=} \\ \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}} \; \mid \; X_n = k\right] & = \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{k}}\mid X_n = k\right] = \\ & = \bigg\rvert \text{$X_n$ и $\xi _i^{(n+1)}$ независ.} \bigg\rvert = \\ & = \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{k}} \right] = \\ & = \mathbb {E}\left[z^{\xi ^{(n+1)}_1}\right] \cdot \mathbb {E}\left[z^{\xi ^{(n+1)}_2}\right] \cdot \cdots \cdot \mathbb {E}\left[z^{\xi ^{(n+1)}_{k}}\right] = \\ & = G_\xi (z) \cdot G_\xi (z) \cdot \cdots \cdot G_\xi (z) = G_\xi ^{k}(z) \\ & \enclose {circle}{=} \sum _{k\in \mathbb {Z}_+} G_\xi ^{k}(z) \cdot \; \mathbb {1}_{X_n = k} \\ G_{X_{n+1}}(z) = \mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}\right] & = \mathbb {E}\left[\mathbb {E}\left[z^{\xi ^{(n+1)}_1 + \dots + \xi ^{(n+1)}_{X_n}}|X_n\right]\right] = \\ & = \mathbb {E}\left[ \sum _{k\in \mathbb {Z}_+} G_\xi ^{k}(z) \cdot \; \mathbb {1}_{X_n = k}\right] = \\ & = \sum _{k\in \mathbb {Z}_+} G_\xi ^{k}(z) \cdot \mathbb {P}\left(X_n = k\right) = \mathbb {E}\left[\left(G_\xi (z)\right)^{X_n}\right] \\ & = G_{X_n}(G_\xi (z)) \end{align} \]

• Иначе все то же самое можно расписать так:

  \[ \begin{align} G_{X_{n+1}}(z) & = \mathbb {E}\left[z^{\sum _{k=1}^{X_{n}} \xi _k^{(n+1)}}\right] = \\ & = \mathbb {E}\left[\; \mathbb {1}_{X_n = 0}z^{\sum _{k=1}^{0} \xi _k^{(n+1)}} + \; \mathbb {1}_{X_n = 1}z^{\sum _{k=1}^{1} \xi _k^{(n+1)}} + \; \mathbb {1}_{X_n = 2}z^{\sum _{k=1}^{2} \xi _k^{(n+1)}} + \ldots \right] = \\ & = \mathbb {E}\left[\sum _{m=0}^\infty \; \mathbb {1}_{X_n = m}z^{\sum _{k=1}^{m} \xi _k^{(n+1)}}\right] \stackrel{\ast }{=} \\ & \stackrel{\ast }{=} \sum _{m=0}^\infty \mathbb {E}\left[\; \mathbb {1}_{X_n = m}z^{\sum _{k=1}^{m} \xi _k^{(n+1)}}\right] \stackrel{\ast \ast }{=} \\ & \stackrel{**}{=} \sum _{m=0}^\infty \mathbb {P}\left(X_n = m\right) \mathbb {E}\left[z^{\sum _{k=1}^{m} \xi _k^{(n+1)}}\right] \stackrel{**}{=} \\ & \stackrel{**}{=} \sum _{m=0}^\infty \mathbb {P}\left(X_n = m\right) \prod _{k=1}^m \mathbb {E}\left[z^{\xi _k^{(n+1)}}\right] \stackrel{***}{=} \\ & \stackrel{***}{=} \sum _{m=0}^\infty \mathbb {P}\left(X_n = m\right) \prod _{k=1}^m \underbrace{\mathbb {E}\left[z^{\xi }\right]}_{=G_{\xi }(z)} = \\ & = \sum _{m=0}^\infty \mathbb {P}\left(X_n = m\right) G_{\xi }^m(z) = \\ & = \mathbb {E}\left[G_{\xi }^{X_n}(z)\right] = G_{X_n} ( G_\xi (z) ) \end{align} \]

  • выполнено по теореме Беппо Леви о монотонной сходимости интеграла Лебега;

  • выполнено из-за независимости \(X_n, \xi^{(n+1)}_1, \xi^{(n+1)}_2, \ldots\);

  • выполнено из-за того, что \(\xi^{(n+1)}_1, \xi^{(n+1)}_2, \ldots\) одинаково распределены по закону \(\xi\).

ExampleПример 3

Предположим, что каждый представитель рода рождает детей так:

• \(0\) с вероятностью \(1/4\);

• \(1\) с вероятностью \(1/4\);

• \(2\) с вероятностью \(1/3\);

• \(3\) с вероятностью \(1/6\).

С какой вероятностью во втором поколении будет ровно \(6\) представителей?

SolutionРешение

Производящая функция \(\xi\): \[ G_{\xi }(z) = \sum _{n=0}^{\infty } \mathbb {P}\left(\xi = n\right) \cdot z^n = \frac{1}{4} + \frac{1}{4}z + \frac{1}{3}z^2 + \frac{1}{6}z^3 \] Производящая функция количества людей во втором поколении: \(G_{X_{2}} = G_{\xi } \circ G_{\xi }\). Нас интересует только коэффициент при \(z^6\). Вычислим: \[ \begin{align} G_{X_{2}}(z) & = G_{\xi } (G_{\xi } (z)) = \\ & =\frac{1}{4} + \frac{1}{4}\cdot \left(\frac{1}{4} + \frac{1}{4}z + \frac{1}{3}z^2 + \frac{1}{6}z^3\right) \\ & \quad + \frac{1}{3}\cdot \left(\frac{1}{4} + \frac{1}{4}z + \frac{1}{3}z^2 + \frac{1}{6}z^3\right)^2 + \frac{1}{6}\cdot \left(\frac{1}{4} + \frac{1}{4}z + \frac{1}{3}z^2 + \frac{1}{6}z^3\right)^3 = \\ & = \ldots + \\ & \quad \left(\frac{1}{3} \cdot \frac{1}{6^2} + \frac{1}{6} \cdot \left(3 \cdot \frac{1}{4} \cdot \frac{1}{6^2} + 3! \cdot \frac{1}{4} \cdot \frac{1}{3} \cdot \frac{1}{6} + \frac{1}{3^3}\right)\right)z^6 + \ldots = \\ & = \ldots + \frac{85}{2592}z^6 + \ldots \end{align} \]

AnswerОтвет

\(\frac{85}{2592} \approx 3.28 \%\).

ProblemЗадача 1

Найдите производящую функцию числа частиц в \(n\)-м поколении ветвящегося процесса, если

1. \(\xi \sim \operatorname {Ber}(p)\);

2. \(G_{\xi }(z) = 1 - p(1-z)^\alpha , \; \alpha \in (0,1)\). Найдите вероятность, с которой в \(2\)-м поколении будет \(1\) представитель. Найдите, с какой вероятностью в 3-м поколении будет \(5\) представителей (в пункте а) пусть \(p=0.3\), в б) пусть \(p=0.3\), \(\alpha = 0.8\)).

HintПодсказка

Для разложения функции в степенной ряд воспользуйтесь Wolfram Alpha.

Попробуем выразить матожидание и дисперсию \(X_{n}\).

Лемма 2 Пусть \(\mathbb {E}\left[\xi \right] = \mu , \; \operatorname {Var}\left[\xi \right] = \sigma^{2}< \infty\). Для ветвящегося процесса \(X_n\) имеем \[ \mathbb {E}\left[X_{n}\right] = \mu ^n, \qquad \operatorname {Var}\left[X_{n}\right] = \begin{cases} \sigma ^2n, & \mu = 1 \\ \sigma ^2 \mu ^{n-1} \frac{\mu ^n - 1}{\mu - 1}, & \mu \neq 1 \end{cases} \]

ProblemЗадача 2

1. Докажите формулу для матожидания \(X_n\);

2. Докажите формулу для дисперсии \(X_n\);

HintПодсказка

Воспользуйтесь свойствами производящей функции.

Десять смоделированных траекторий ветвящегося процесса с законом размножения \(\operatorname{Pois}(\mu)\). Хорошо видна дихотомия «вымирание или экспоненциальный рост»: часть популяций вымирает, даже если \(\mu > 1\) (надкритический случай), а выжившие растут вдоль пунктирной кривой \(\mathsf E X_n = \mu^n\). Двигайте слайдер \(\mu\) через критическое значение \(1\): при \(\mu \leqslant 1\) все траектории рано или поздно вымирают (\(q=1\)), при \(\mu>1\) появляется шанс неограниченного роста, и доля вымерших среди смоделированных траекторий приближается к теоретической вероятности вырождения \(q\) (наименьшему корню \(z=e^{\mu(z-1)}\)). Кнопка «Новые траектории» пересчитывает всё с той же \(\mu\), но со свежими случайными числами.

μ = 1.30

4 Вероятность вырождения

Обозначим через \(q\) вероятность вырождения, т.е. \(q= \mathbb {P}\left(\exists n \in \mathbb {N}: \; X_n = 0\right)\). Тогда выполнено следующее утверждение.

Лемма 3 Вероятность вырождения \(q\) ветвящегося процесса с законом размножения частиц \(\xi\) является наименьшим неотрицательным корнем уравнения \[ z=G_{\xi }(z), \tag{2}\] т.е. это неподвижная точка функции \(G_{\xi }\).

ExampleПример 4

Доказать лемму Лемма 3.

SolutionРешение

Заметим, что каждый человек в поколении порождает (в своих потомках) копию исходного процесса Гальтона-Ватсона, которая не зависит от остальных людей в поколении и их потомков. Т.е. чтобы процесс вымер, нужно, чтобы или он вымер сразу на 1-м шаге (т.е. чтобы \(\xi_1^{(1)} = 0\)), или чтобы все \(\xi_1^{(1)}\) независимых копий процесса Г-В в конечном итоге вымерли. Вероятность этого (при условии, что \(\xi_1^{(1)} = k\)) равна \(q^k\) из-за независимости. В итоге,

\[ \begin{align} q = \mathbb {P}\left(\xi _1^{(1)} = 0\right) + \sum _{k=1}^\infty q^k \mathbb {P}\left(\xi _1^{(1)} = k\right) = G_\xi (q) \end{align} \]

Другое доказательство: события \(\left\{ X_n = 0\right\}\) возрастают по \(n\) (вымерший процесс не воскресает), и их объединение – это событие вырождения. По непрерывности вероятностной меры \(\mathbb {P}\left(X_n = 0\right) = G_{X_n}(0)\) неубывает по \(n\) и сходится к \(q\). Используя непрерывность \(G\), имеем

\[ \begin{align} G_\xi (q) & = G_\xi (\lim _{n \to \infty } G_{X_n}(0)) = \lim _{n \to \infty } G_\xi (G_{X_n}(0)) = \lim _{n \to \infty } G_{X_{n+1}}(0) = \\ & = q \end{align} \]

Из этого можно вывести и то, что \(q\) – наименьший неотрицательный корень уравнения \(z = G_\xi (z)\). Пусть \(z \geq 0\) – произвольный корень. Тогда \(z\) – неподвижная точка и всех композиций: \(G_{X_n}(z) = z\). Производящие функции монотонны на \([0, +\infty )\), поэтому

\[ \begin{align} G_{X_n}(0) \leq G_{X_n} (z) = z \end{align} \]

Берем предел по \(n\) в левой части, получаем \(q \leq z\).

Уравнение (Уравнение 2) - это первая замечательная формула в теории ветвящихся процессов. Отметим, что \(z=1\) всегда является решением (Уравнение 2). Однако при наличии других корней нам надо уметь отбирать среди них вероятность вырождения. Полную классификацию ситуаций дает теорема о вероятности вырождения.

Теорема 2 Пусть СВ \(\xi\) не равна тождественно \(1\), т.е. \(\mathbb {P}\left(\xi = 1\right) < 1\). Обозначим \(\mu = \mathbb {E}\left[\xi \right]\) (может быть, \(\mu = +\infty )\). Тогда

1. Если \(\mu \leqslant 1\), то уравнение (Уравнение 2) имеет только одно решение \(z=1\) на \([0,1]\). В этом случае \(q=1\).

2. Если \(\mu >1\), то уравнение (Уравнение 2) имеет единственное решение \(z_{0} \in [0,1)\). В этом случае \(q=z_{0}\).

Таким образом, вероятность вырождения - это наименьший корень уравнения \(z=G_{\xi }(z)\) из отрезка \([0,1]\).

Отметим, что теорема имеет весьма жизненную интерпретацию: если среднее число потомков в процессе не больше 1, то процесс обречен на вымирание; в противном случае есть ненулевая вероятность бесконечного существования популяции.

Итерации производящей функции: лестница \(0 \to G_\xi(0) \to G_\xi(G_\xi(0)) \to \ldots\) (красная) изображает рост вероятностей \(\mathsf P(X_n = 0) = G_{X_n}(0)\) к вероятности вырождения \(q\) — наименьшей неподвижной точке \(G_\xi\) на \([0,1]\) (точке пересечения с диагональю). Закон размножения — \(\operatorname{Geom}(p)\), \(\mathsf P(\xi = k) = p(1-p)^k\), со средним \(\mu = \frac{1-p}{p}\). Двигайте слайдер \(p\): при переходе \(\mu\) через критическое значение \(1\) (т.е. \(p\) через \(\frac12\)) точка пересечения кривой \(G_\xi\) с диагональю «отрывается» от \(1\), и вероятность вырождения \(q\) становится меньше единицы. Кнопками «Шаг» и «Играть» лестницу итераций можно построить пошагово, «Сброс» возвращает её к началу.

p = 0.30

ExampleПример 5

Найдите вероятность вырождения ветвящегося случайного процесса с геометрическим \(\operatorname {Geom}(p)\), \(p \in (0,1)\) законом размножения частиц (т.е. \(\mathbb {P}\left(\xi = k\right) = p(1-p)^{k}, \; k \in \mathbb {Z}_{+}\)).

SolutionРешение

Найдем сначала производящую функцию закона размножения.

\[ G_{\xi }(z)= \mathbb {E}\left[z^{\xi }\right] = \sum _{k=0}^{\infty } z^{k} p(1-p)^{k} = \frac{p}{1-z(1-p)} \]

Теперь решаем уравнение \(z=G_{\xi }(z)\). Квадратное уравнение имеет два корня: \(z_{1}=1, z_{2}=p /(1-p)\). Согласно следствию из теоремы, мы должны выбрать наименьший корень на отрезке \([0,1]\). Тем самым, \(q = 1\), если \(p \geqslant \frac{1}{2}\); \(q= \frac{p}{1-p}\), если \(p < \frac{1}{2}\).

AnswerОтвет

\(q = 1\), если \(p \geqslant \frac{1}{2}\); \(q= \frac{p}{1-p}\), если \(p < \frac{1}{2}\).

ProblemЗадача 3

Найдите вероятности вырождения для ветвящихся процессов с производящей функцией числа потомков одной частицы

1. \(1-p(1-z)^{\alpha }, \alpha \in (0,1)\);

2. \(\left(1+z+z^{2}+z^{3}\right) / 4\).

ProblemЗадача 4

Найдите распределение момента вырождения \(\tau_0\) для ветвящихся процессов с производящей функцией числа потомков одной частицы

1. \(p z+1-p\);

2. \(1-p(1-z)^{\alpha }, \alpha \in (0,1)\)

ProblemЗадача 5

Ветвящийся процесс имеет следующий закон \(\xi\) распределения потомков одной частицы: \[ \mathbb {P}\left(\xi = 0\right) = \frac{1}{4}, \quad \mathbb {P}\left(\xi = 2\right) = \frac{1}{2}, \quad \mathbb {P}\left(\xi = 6\right) = \frac{1}{4} \] Верно ли, что вероятность вырождения будет принадлежать интервалу \((1 / 4,1 / 3)\)?

ProblemЗадача 6

Человек заразился редким вирусом. В течение суток с вероятностью \(p<1\) с ним не произойдет никаких важных событий (вроде контактов с другими людьми или выздоровления). При условии, что за сутки произойдет важное событие, с вероятностью \(r\) больной заразит одного человека, с вероятность \(s\)- двоих, и с вероятностью \(t=1-r-s\) он перестанет болеть и никого не заразит. Судьбы заразившихся независимы друг от друга, как и события разных дней. Заболевший становится потенциально опасным на следующий день после заражения. Пусть \(q\)- вероятность окончания эпидемии. Докажите, что \(q\) не зависит от \(p\). Найдите \(q\), если

1. \(2 r+3 s \leq 1\)

2. \(2 r=s=t\).

5 Общее число частиц

Обсудим теперь вопрос об общем числе частиц в ветвящемся процессе. Обозначим \(Y_{n}=1+X_{1}+\ldots +\) \(X_{n}\) – общее число частиц в процессе до момента времени \(n\) включительно. Тогда имеет место следующее рекуррентное соотношение между производящими функциями \(Y_{n}\) и \(Y_{n-1}\), аналогичное соотношениям в Лемма 1 для самого \(X_{n}\):

\[ G_{Y_{n+1}}(z)=z G_{\xi }\left(G_{Y_{n}}(z)\right) \tag{3}\]

ExampleПример 6

Докажите ().

HintПодсказка

См. пример @G-W_proc:prob_of_extict_lem_proof.

SolutionРешение

Заметим, что каждый из представителей первого поколения в своих потомках порождает процесс Гальтона-Ватсона, независящий от остальных представителей и их потомков. При этом кол-во представителей первого поколения распределено по закону \(\xi\) и не зависит от последующего кол-ва потомков. Т.е. имеем \(Y_{n+1} \overset {d}{=} 1 + \sum_{i=1}^{\xi } Y_n^i =: \tilde{Y}_{n+1}\), где \(Y_n^i\) – независимые (между собой и от \(\xi\)) копии \(Y_n\). При этом (более подробно см. решение G-W_proc:prob_of_extict_lem_proof) \[ \begin{align} G_{\tilde{Y}_{n+1}}(z) & = \mathbb {E}\left[z^{\tilde{Y}_{n+1}}\right] = \mathbb {E}\left[z \cdot z^{\sum _{i=1}^{\xi } Y_n^i}\right] = \\ & = z \cdot \mathbb {E}\left[z^{\sum _{i=1}^{\xi } Y_n^i}\right] \enclose {circle}{=} \\ \mathbb {E}\left[z^{\sum _{i=1}^{\xi } Y_n^i}\right] & = \mathbb {E}\left[\mathbb {E}\left[z^{\sum _{i=1}^{\xi } Y_n^i} \mid \xi \right]\right] = \mathbb {E}\left[G^\xi _{Y_n}(z)\right] = G_{\xi }(G_{Y_n}(z)) \\ & \enclose {circle}{=} \; z \cdot G_{\xi }(G_{Y_n}(z)) \end{align} \] Т.к. речь идет о матожиданиях, можно делать переходы с точностью до равенства по распределению того, что стоит под матожем. Итого \[ \begin{align} G_{Y_{n+1}}(z) = z G_\xi (G_{Y_n}(z)) \end{align} \]

Пусть \(Y\) – общее число частиц в ветвящемся процессе за все время: \(Y = \lim_{n \to \infty } Y_{n}\). \(Y_{n}\) сходятся к \(Y\) поточечно (т.е. при всех \(\omega\)), значит п.н. и по распределению. Можно доказать, что из этого следует поточечная сходимость производящих функций:

\[ G_{Y}(z) = \lim _{n \to \infty } G_{Y_n}(z), \qquad \text{для любых } \left|z\right| < 1 \]

Найти \(G_{Y}\) можно как предел \(G_{Y_n}\), а можно из второго замечательного уравнения в теории ветвящихся случайных процессов.

Лемма 4 Функция \(G_{Y}(z)\), \(\left|z\right| < 1\) удовлетворяет \[ G_Y(z) = z G_{\xi }(G_Y(z)). \]

Попробуйте самостоятельно доказать эту формулу.

ProblemЗадача 7

Предположим, что \(\xi \sim \operatorname {Geom}(1 - p)\), т.е. \(G_{\xi }(z) = \frac{1 - p}{1 - pz}\).

1. Найдите вероятность вырождения процесса;

2. Найдите производящую функцию \(G_Y(z)\) общего числа частиц \(Y\). Найдите \(\lim_{z \to 1}G_Y(z)\), сравните с результатом из предыдущего пункта (они должны совпадать).

3. Найдите производящую функцию \(G_{X_n}\) для \(X_n\).

HintПодсказка

К пункту в): отображение вида \(f(z) = \frac{az + b}{cz + d}\) (\(a,b,c,d \in \mathbb {C}\), \(ad \neq bc\)) называется дробно-линейным преобразованием. Точнее говоря, ДЛО определяется так: \[ f(z) = \begin{cases} \frac{az + b}{cz + d}, & z \in \mathbb {C} \setminus \left\{ -\frac{d}{c}\right\} \\ \infty , & z = -\frac{d}{c} \\ \frac{b}{d}, & z = \infty \end{cases}, \qquad z \in \overline{\mathbb {C}} \] ДЛО как преобразования сферы Римана \(\overline{\mathbb {C}}\) образуют группу относительно композиции. Причем эта группа гомоморфна группе \(\operatorname {GL}_2(\mathbb {C})\) обратимых матриц \(2 \times 2\) над \(\mathbb {C}\): отображение \[ \frac{az + b}{cz + d} \mathrel {\leadsto } \begin{pmatrix} a & b \\ c & d \end{pmatrix} \] преобразует операцию композиции ДЛО в матричное умножение.

Вероятность вымереть к поколению \(n\) для геометрического закона размножения с \(\theta = \mathsf E \xi\): точная формула \(\mathsf P(X_n = 0) = \frac{\theta^n - 1}{\theta^{n+1} - 1}\) при \(\theta \neq 1\) и \(\frac{n}{n+1}\) при \(\theta = 1\) (выводится из дробно-линейного вида \(G_\xi(z) = \frac{1}{1+\theta-\theta z}\)). Тонкими линиями показаны три канонических случая \(\theta = 0{,}8\), \(\theta = 1\), \(\theta = 1{,}25\); жирная выделенная кривая следует за слайдером \(\theta\) (или кнопками-пресетами). Нижняя панель — то же расстояние \(q - \mathsf P(X_n=0)\) в логарифмической шкале: на ней хорошо видно, что докритическая и надкритическая сходимости геометрические (прямые линии), а критическая (\(\theta=1\)) — степенная (медленно изгибающаяся кривая).

θ = 1.25

ProblemЗадача 8

На последнем уровне компьютерной игры «Герои мочалки и мыла III: Дыхание Мойдодыра» игроку предстоит сразиться со злобным Мыльным Пузырём. Каждый раз когда игрок атакует Пузырь, происходит одно из двух равновероятных событий: Пузырь может лопнуть, а может распасться на два новых Пузыря. Для победы игроку необходимо уничтожить все Мыльные Пузыри.

1. Каков шанс пройти этот уровень?

2. Пусть \(\tilde{Y}\) общее количество лопнувших Пузырей. Найдите производящую функцию и распределение \(\tilde{Y}\).

3. Вычислите \(\mathbb {E}\left[\tilde{Y}\right]\).

ProblemЗадача 9

Пусть \(\tilde{Y}\) – общее количество частиц, не имеющих потомков в ветвящимся процессе Гальтона-Ватсона с геометрическим законом размножения \(\operatorname {Geom}(2/3)\) (то есть \(\mathbb {P}\left(\xi =k\right) = \frac{2}{3} \cdot \left(\frac{1}{3}\right)^k\) для \(k \in \left\{ 0,1,2, \ldots \right\} )\). Вычислите \(G_{\tilde{Y}}\) и \(\mathbb {E}\left[\tilde{Y}\right]\).