This week’s Riddler Classic poses a question about bacteria (paraphrased for brevity):
Each bacterium in a colony splits into two copies with probability
\(p\)and dies with probability\((1-p)\). If the colony starts with one bacterium, what is the probability that the colony survives forever?
We can model the colony’s size as a Galton-Watson process.
Let \(X_t\) be the colony’s size in generation \(t\in\{1,2,\ldots\}\) and let \(Y_{it}\) be the number of offspring generated by bacterium \(i\in\{1,2,\ldots,X_t\}\).
The \(Y_{it}\) are independently and identically distributed, with
$$\Pr(Y_{it}=y)=\begin{cases} p & \text{if}\ y=2 \\ 1-p & \text{if}\ y=0 \\ 0 & \text{otherwise} \end{cases}$$
for each \(i\) and \(t\).
The colony’s size grows according to
$$X_{t+1}=\sum_{i=1}^{X_t}Y_{it}$$
with \(X_1=1\).
Our goal is to compute
$$\lim_{t\to\infty}\Pr(X_t>0)=1-\lim_{t\to\infty}q_t,$$
where \(q_t\equiv\Pr(X_t=0)\) is the probability that the colony is extinct by generation \(t\).
We can compute \(q_t\) by conditioning on \(Y_{11}\), the number of offspring generated by the first bacterium.
If \(Y_{11}=0\) then the colony is extinct from the second generation onwards.
However, if \(Y_{11}=2\) then there are two sub-colonies in the second generation that must be extinct in \((t-1)\) generations if the whole colony is extinct by generation \(t\).
These sub-colonies grow independently, so the probability that both are extinct in \((t-1)\) generations is \(q_{t-1}^2\).
Thus, by the law of total probability, we have
$$\begin{align} q_t &= \Pr(X_t=0\,\vert\,Y_{11}=0)\Pr(Y_{11}=0)+\Pr(X_t=0\,\vert\,Y_{11}=2)\Pr(Y_{11}=2) \\ &= 1\times(1-p)+q_{t-1}^2\times p \\ &= 1-p+pq_{t-1}^2 \end{align}$$
for \(t\ge2\).
Defining \(q\equiv\lim_{t\to\infty}q_t\) and taking limits as \(t\to\infty\) gives1
$$q=1-p+pq^2,$$
which has solutions
$$\begin{align} \newcommand{\abs}[1]{\lvert#1\rvert} q &= \frac{1\pm\sqrt{1-4p(1-p)}}{2p} \\ &= \frac{1\pm\sqrt{(2p-1)^2}}{2p} \\ &= \frac{1\pm\abs{2p-1}}{2p}. \end{align}$$
The larger solution exceeds unity when \(p<0.5\), which we cannot have because \(q\) is a probability.
Thus
$$\lim_{t\to\infty}\Pr(X_t>0)=1-\frac{1-\abs{2p-1}}{2p}.$$
For example, if \(p=0.8\) then the colony survives forever with probability
$$1-\frac{1-\abs{2\times0.8-1}}{2\times0.8}=0.75.$$
If \(p<0.5\) then extinction is guaranteed because each bacterium generates fewer than one offspring on average.
-
The function
\(x\mapsto x^2\)is continuous and so preserves limits. ↩︎