This problem is a balancing act. If $k$ of the prisoners flip their coins, the chance of being released is
\[
\mathrm{Prob}(\text{win if }k\text{ coins are flipped})=\begin{cases} 0 & k=0\\ \frac{1}{2^k} & k=1,2,\dots,n\end{cases}
\]The best-case scenario is if $k=1$ prisoner flips their coin and the others do not, ensuring the maximum probability of release of $1/2$. But how should the prisoners decide who flips their coin? If they were allowed to communicate ahead of time, they could elect somebody to flip their coin. But since the prisoners cannot communicate so there is no way to plan ahead!
Since each prisoner has access to a random number generator, they can use it to decide whether they should be flipping their coin or not. Here is the strategy. We must decide on a threshold $t$. Each prisoner queries their random number generator and if the number they obtain is less than $t$, they flip their coin. The larger $t$ is, the more likely prisoners are to flip coins. So there is a trade-off between ensuring at least one prisoner flips a coin and ensuring not too many prisoners flip coins. Let’s figure out the best choice of $t$.
Let’s call the probability the prisoners are released $f_n(t)$. It depends on the threshold they choose. Now,
\begin{align*}
f_n(t) &= \sum_{k=1}^n \frac{1}{2^k} \mathrm{Prob}(\text{there are }k\text{ flips}) \\
&= \sum_{k=1}^n \frac{1}{2^k} \binom{n}{k}t^k(1-t)^{n-k} \\
&= \sum_{k=1}^n \binom{n}{k}\left(\frac{t}{2}\right)^k (1-t)^{n-k} \\
&= ( 1-\tfrac{1}{2}t)^n-(1-t)^n
\end{align*} In the last step, we used the Binomial Theorem to evaluate the sum. So our goal is to find $t\in[0,1]$ that minimizes $f_n(t)$. Here is what the function looks like for different values of $n$:
As anticipated, there is an ideal value of the threshold $t$ that maximizes the probability of winning. However, the maximum depends on $n$, the number of prisoners. To find the maximum, we can use calculus: set the derivative of $f_n(t)$ equal to zero:
\[
\frac{\mathrm{d}f_n(t)}{\mathrm{d}t}=n(1-t)^{n-1}-\tfrac{1}{2}n(1-\tfrac{1}{2}t)^{n-1}=0
\]Solving for the optimal threshold $t$, we obtain:
$\displaystyle
t_\text{opt}=1-\frac{1}{2^{n/(n-1)}-1}
$
As a function of $n$, $t_\text{opt}$ is the threshold each prisoner should use. If their random number generator produces a value less than the threshold, they should flip their coin. Otherwise, they should not. As anticipated, in the limit $n\to\infty$, $t_\text{opt}\to 0$ because as the number of prisoners increases, we want each prisoner to be less likely to flip their coin. As an approximation, the first order asymptotic expansion of $t_\text{opt}$ is
\[
t_\text{opt} = \frac{2\log(2)}{n} + O\left(\frac{1}{n^2}\right)\approx\frac{1.386}{n}
\]So this can be used as a quick way to approximate the threshold (in case the prisoners don’t have access to a calculator!).
How about the probability of winning assuming the prisoners use this strategy? This simply amounts to evaluating $f_n(t_\text{opt})$. Doing so, we obtain:
$\displaystyle
\textrm{Prob}(\text{win}) = \frac{1}{\left(2^{n/(n-1)}-1\right)^{n-1}}
$
Here is a table comparing the optimal threshold and corresponding probability of winning for different values of $n$:
| Number of prisoners |
threshold $t_\text{opt}$ |
Probability of freedom |
| 1 |
1 |
0.5 |
| 2 |
0.666667 |
0.333333 |
| 3 |
0.453082 |
0.299119 |
| 4 |
0.342037 |
0.284842 |
| 5 |
0.274529 |
0.277001 |
| 10 |
0.13802 |
0.262709 |
| 50 |
0.0277034 |
0.252429 |
| 100 |
0.0138574 |
0.251208 |
So when $n=1$, the lone prisoner flips every time and the probability of winning is $\frac{1}{2}$. With two prisoners, each prisoner should flip $\frac{2}{3}$ of the time, and the probability of winning is $\frac{1}{3}$. As $n\to\infty$, the threshold goes to zero as described above, and we can also verify that the probability of winning tends to $\frac{1}{4}$ in the limit.
So this strategy ensures that the probability of all prisoners being released is always at least 25%. The only caveat is that in order to compute which threshold to use, the prisoners must know $n$, the total number of prisoners playing the game.
