#analysis/probability-statistics
# Definition
We have a [[stochastic process]] defined as follows:
We start with a single *root node*, ![[CleanShot 2022-11-05 at 20.47.14.jpg]]
each *descendent* behaves just like the *root node*, independently of others, and so forth:
![[CleanShot 2022-11-05 at 20.48.54.jpg]]
# [[Probability Generating Function]]
**Question 1.** Let $X_n$ be the *total population* at level $n$. What is the [[probability generating function]] $G_{X_n} = G_n$?
For later convenience denote $G_1(s) = \sum_{k=0}^\infty s^k \overbrace{P(X_1=k)}^{\text{prob. that root has $k$ descendants}} = \sum_{k=0}^\infty p_k s^k := p(s),$where $p_k = P(X_1=k)$.
For $G_n(s)$, condition on the *first step of the process* (a common pattern!): From [[total expectation]] we can write $G_n(s) = E(s^{X_n}) = \sum_{k=0}^\infty P(X_1=k)E(s^{X_n} | X_1=k) = \sum_{k=0}^\infty p_kE(s^{X_n}|\text{``there are $k$ descendants at the $1^{st}$ step"}).$
Also$\begin{align}
E(s^{X_n} | \text{0 descendants at 1st level}) = E(s^0) = E(1)=1\\ E(s^{X_n} | \text{1 descendant at 1st level}) \ \ = E(s^{X_{n-1}}).\end{align}$
We have that last equality because having $1$ descendant from the 1st level is like "starting the process anew, but with one level used up"; our 'root' becomes the 2nd level itself and we're left with a tree of $n-1$ levels.
Now what about $E(s^{X_n} | \text{2 descendants at 1st level})$?
![[CleanShot 2022-11-06 at 16.37.24.jpg]]
Let $Y_1$ be the total population coming from the 1st (left) descendant; $Y_2$ that from the 2nd (right) descendant, so that the total population at the $n^{th}$ level is $Y_1 + Y_2$. Everything is [[independent random variables|independent]], so $E(s^{X_n}| \text{exactly $2$ descendants at 1st level}) = E(s^{Y_1 + Y_2}) = E(s^{Y_1}s^{Y_2})= $ by independence $E(s^{Y_1})E(s^{Y_2}) = E(s^{X_{n-1}})E(s^{n-1}) = E^2(s^{n-1}).$
Now, in general: $E(s^{X_n}| \text{ exactly k descendants at 1st level})$ is $E(s^{Y_1 + \dots + Y_k}) = E(s^{Y_1})\dots E(s^{Y_k}) = \big( E(s^{x_{n-1}}) \big)^k.$
Coming back to $G_n(s)$ we have $G_n(s) = p_0 + p_1E(s^{X_{n-1}}) + p_2E^2(s^{X_{n-1}}) + \dots + p_kE^k(s^{X_{n-1}}) + \dots$
that is, $G_n(s) = p\big(G_{n-1}(s)\big), \ \ n>1.$
# Probability of Eventual Extinction
We say the probability of extinction is $P(X_1= 0 \text{ or } X_2=0 \text{ or } X_3=0 \text{ or } \dots)$
Note that these [[event]]s are *nested:*
![[CleanShot 2022-11-06 at
[email protected]]]
We've shown that if we have a nested family of events, then (intuitively!) $\begin{align}
P(X_1= 0 \text{ or } X_2=0 \text{ or } X_3=0 \text{ or } \dots) =& \lim_{n \to \infty} P(X_n=0), \end{align}$
but in our case that is just $=\lim_{n \to \infty} G_n(0).$
So what is that [[function limit]]'s value? Proof by picture:
![[CleanShot 2022-11-06 at 20.13.18.jpg]]
$\begin{align}
G_n(s) = p\big(G_{n-1}(s)\big) =& p(p(G_{n-2}))\\ =& \cdots \\ = p(p(\dots(p(0))).\end{align}$
So we conclude that the above [[function limit]] is the **smallest nonnegative solution to the equation $p(s)=s$**.
## Example of This
![[CleanShot 2022-11-06 at 20.20.24.jpg]]
# Remarks
## 1
Suppose that $p_0>0$ (process could extinct right away). Then the probability of extinction is $1$ **if and only if** $p'(1) = \sum_{k=1}^\infty kp_k = E(X_1) \leq 1$. This means that to go on forever, just need the expected number of descendants for a given node to be