Each member of a population dies with probability $\frac12$ each day, what is the probability that there will be exactly $1$ person alive?

Suppose that there are $n$ people alive in a population. Due to a deadly disease, each person dies with probability $\frac12$ each day (and there are no births). What is the probability that there will be exactly one person alive at some time?

Thoughts:

Let $p_k$ be the probability that the population reaches exactly $1$ person given that there are currently $k$ people alive. Then $p_0 = 0$ and $p_1 = 1$.

The probability of going from $k$ people alive to $k - j$ being alive (where $0 \leq j \leq k$) is the probability that $j$ die: $$ \binom{k}{j} \left(\frac{1}{2}\right)^j \left(\frac{1}{2}\right)^{k - j} = \binom{k}{j} \left(\frac{1}{2}\right)^k $$ And using conditional probability we have the recursion: $$ p_k = \frac{1}{2^k} \binom{k}{0} p_k + \frac{1}{2^k} \binom{k}{1} p_{k - 1} + \cdots + \frac{1}{2^k} \binom{k}{k - 1} p_1 + \frac{1}{2^k} \binom{k}{k} p_0, $$ or $$ (2^k - 1)p_k = \binom{k}{1} p_{k - 1} + \cdots + \binom{k}{k - 1} p_1. $$ Is it possible to solve a recursion like this? Is there a better way to solve the puzzle?

Solution 1:

Partial solution. First find the probability that one specific person is the unique last survivor, then multiply by $n$.

Omegaman is the last to die on the $k+1$st day with probability

$$ p_k = \frac{1}{2^{k+1}} \left(1-\frac{1}{2^k}\right)^{n-1} $$

so then the desired probability is

\begin{align} q & = n\sum_{k=1}^\infty p_k \\ & = n\sum_{k=1}^\infty \frac{1}{2^{k+1}} \left(1-\frac{1}{2^k}\right)^{n-1} \\ & = \frac{n}{2} \sum_{k=1}^\infty \frac{1}{2^k} \left(1-\frac{1}{2^k}\right)^{n-1} % & = \frac{n}{2} % \sum_{k=1}^\infty \frac{1}{2^k} % \sum_{j=0}^{n-1} \binom{n-1}{j}\left(-\frac{1}{2^k}\right)^j \\ % & = \frac{n}{2} % \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j % \sum_{k=1}^\infty \left(\frac{1}{2^k}\right)^{j+1} \\ % & = \frac{n}{2} % \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j % \sum_{k=1}^\infty \left(\frac{1}{2^{j+1}}\right)^k \\ % & = \frac{n}{2} % \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j % \frac{\frac{1}{2^{j+1}}}{1-\frac{1}{2^{j+1}}} \\ % & = \frac{n}{2} % \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j \frac{1}{2^{j+1}-1} \end{align}

Still working out if there's a closed-form expression for this. I will point out that we can obtain

$$ q = \frac{n}{2} \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j \frac{1}{2^{j+1}-1} $$

if that counts as closed.

Solution 2:

I believe Brian has solved the problem as far as it can be solved for finite $n$. But my skepticism about finding a closed form for the limit for $n\to\infty$ was unwarranted. Approximating Brian's sum by an integral for large $n$, we find

\begin{eqnarray*} q &=& \frac n2\sum_{k=1}^\infty\frac1{2^k}\left(1-\frac1{2^k}\right)^{n-1} \\ &\approx& \frac n2\int_0^\infty2^{-x}\left(1-2^{-x}\right)^{n-1}\mathrm dx \\ &=& \frac n2\int_0^1u(1-u)^{n-1}\frac{\mathrm du}{u\ln2} \\ &=& \frac n{2\ln2}\int_0^1(1-u)^{n-1}\mathrm du \\ &=& \frac1{2\ln2} \\ &\approx& 0.7213\;, \end{eqnarray*}

in agreement with Ross's numerical results.

We can also ask how this limit depends on the survival probability $r$, which is $r=\frac12$ in the question. For $r=0$ we have $q=0$, and for $r\to1$ we should have $q\to1$. In general, for large $n$,

\begin{eqnarray*} q &=& n(1-r)\sum_{k=1}^\infty r^k\left(1-r^k\right)^{n-1} \\ &\approx& n(1-r)\int_0^\infty r^x\left(1-r ^x\right)^{n-1}\mathrm dx \\ &=& n(1-r)\int_0^1u(1-u)^{n-1}\frac{\mathrm du}{-u\ln r} \\ &=& \frac{r-1}{\ln r}\;. \end{eqnarray*}

Here's a plot.

The probability increases very rapidly around $r=0$; for $r=0.01$ we already have $q\approx0.215$.

Solution 3:

Here's a look at the problem using a generating function. As you point out, we have for $k > 1$: $$ p_k = \frac{1}{2^k}\sum_{j=0}^k \binom{k}{j} p_j $$ Note that this is off by $\frac12$ when $k=1$. We define $f(z)$ to be the exponential generating function for $p_k$: $$ f(z) = \sum_{k=0}^\infty \frac{p_k}{k!} z^k $$ Then we observe: $$ f(\frac z2)e^{\frac z2} + \frac{z}{2} = \sum_{k=0}^\infty \left(\sum_{j=0}^k \frac{p_j}{j!(k-j)!}\right)\left(\frac{z}{2}\right)^k + \frac{z}{2} = f(z) $$ This gives us a recursion formula for $f(z)$. Inductively, we can see $$ f(z) = \frac{z}{2} + f(\frac z2)e^{\frac z2} = \frac{z}{2} + \frac{z}{4}e^{\frac{z}{2}} + f(\frac z4)e^{\frac {3z}4} = ... = \sum_{n=0}^{N-1} \frac{z}{2^{n+1}} e^{\frac{2^n - 1}{2^n} z} + f(\frac{z}{2^N}) e^{\frac{2^N - 1}{2^N} z} $$ Taking the limit as $N$ goes to infinity and recalling that $f(0) = p_0 = 0$, we determine: $$ f(z) = \sum_{n=0}^{\infty} \frac{z}{2^{n+1}} e^{\frac{2^n - 1}{2^n} z} =\frac{z e^z}2 \sum_{n=0}^\infty \frac{e^{-2^{-n} z}}{2^n} $$ Thus we have $p_n = f^{(n)} (0)$ which works out to agree with the other answers: $$ p_n = f^{(n)}(0) = \frac{n}{2}\sum_{k=1}^\infty 2^{-k}\left(1 - 2^{-k}\right)^{n-1} $$ Note that this is increasing in $n$, and bounded above by $1$, hence it converges.

Now we show that $\lim p_k = \frac1{2\log 2}$. Notice that the sum $\sum_{n=0}^\infty \frac{e^{-2^{-n} z}}{2^n}$ is a left Riemann sum with interval divisions of length $1$ of the integral $\int_0^\infty 2^{-x} e^{-2^{-x} z} dx$, which evaluates to $\frac{1 - e^{-z}}{z\log 2}$. Call the integrand $g(x)$. Notice that $g(x)$ is increasing for $x < \log_2{z}$ and decreasing for $x > \log_2{z}$. Thus, for the smaller $x$, the integral underestimates the sum, and for the larger $x$, it overestimates. Changing to a right Riemann sum switches the over/underestimation but since all terms in the series go to $0$ exponentially as $z$ goes to infinity this doesn't change the asymptotics of the overall sum in $z$. Hence the sum and the integral are asymptotically equivalent. We therefore can conclude $$ f(z) \sim \frac{e^z}{2\log 2} $$ which implies that if $p_n$ converges to a limit, it must converge to $\frac1{2\log 2}$. Since we have already established that $p_n$ is convergent, this shows that indeed $\lim\limits_{n\rightarrow\infty} p_n = \frac1{2\log2}$.

Solution 4:

This is as far as I can get ...

Another possible approach would be to reason that after $k$ days, the probability of any particular person being alive is $2^{-k}$ and the probability of being dead is $(1-2^{-k})$ so the probability that exactly one person is alive after $k$ days is given by ... $$ P_k =n( 1-2^{-k})^{n-1}2^{-k} \\= n(2^k -1)^{n-1}2^{-nk} $$

your final probability will be $$P=\sum_{k=0}^\infty P_k $$ $$ P= n\sum_{k=0}^\infty \sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j 2^{(j-n)k } \\ = n\sum_{j=0}^{n-1} \binom{n-1}{j} (-1)^j \sum_{k=0}^\infty 2^{(j-n)k } \\ =n \sum_{j=0}^{n-1}\dfrac{ (-1)^j \binom{n-1}{j} }{ 1-2^{j-n} } $$