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?
Best Answer
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.