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\)
gives^{1}
$$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. ↩︎