Solution To Second Prisoners Puzzle Question

It depends on how many prisoners there are

Should the prisoners take the deal?

Solution

A little thought should convince you that there is no certain answer to how long this game will take before all N-1 prisoners have been counted, since the prisoners are selected randomly. The table below shows the expected exact number of days to count all the prisoners as a function of the number of prisoners N, using a formula we derive below. The table also shows the standard deviation, which is a measure of the typical deviation from the average. We also simulated the game to show that the formulas are correct. As you can see, the number of prisoners must be reasonably low for the prisoners to accept the warden’s proposal. At N = 35, the total average wait time of 3.66 years plus two standard deviations is almost five years, so the prisoners are taking a non-trivial risk of extending their sentences if there are 35 or more prisoners. On the other hand if N is less than 20, the warden’s offer is a good deal.

Mathematical Derivation of the Formulas

The key to solving this problem is to realize that each prisoner must wait some random number of days to get into the room for the first time to turn on the light. Similarly, Bob must wait some random number of days before he is selected to enter the room and count each prisoner who turned on the light. The total number of days to win the game is the sum of the days each prisoner must wait on average to turn on the light and the number of days Bob must wait to count each prisoner. The geometric distribution is ideal for this problem because it models the number of trials until the first success.

Suppose we’re in the middle of the game. Out of N prisoners, there are k prisoners remaining that have yet to turn on the light. The probability that one of the k prisoners will be selected to enter the room is

\(p_k=\frac{k}{N}\)

since the probability that any prisoner selected is 1/N and the probability that one of the k prisoners will be selected is

\(\frac{1}{N}+\frac{1}{N}+\frac{1}{N}\ldots+\frac{1}{N} k\, times = \frac{k}{N}\)

The probability that a prisoner will be selected who has already turned on a light is then

\(1-p_k=\frac{N-k}{N}\)

We can model the selection process of one of the k prisoners who has not yet turned on the light as a geometric distribution, which gives us the probability that one of the k prisoners will be selected in i days as

\(p_k^i=(\frac{k}{N})(\frac{N-k}{N})^{i-1}\)

The formula says that prisoners who have already turned on the light switch are randomly selected for i-1 days, followed by the selection of one of the prisoners who has yet to turn on the light switch.

Similarly, Bob’s selection can also be modeled by a geometric distribution.

The probability that Bob is selected to enter the room after i days is

\(p_{Bob}^i=(\frac{1}{N})(\frac{N-1}{N})^{i-1}\)

The average number of days that the kth prisoner will wait to turn on the light is the mean of the geometric distribution, which is the reciprocal of the probability he will be selected. The average wait time for the kth prisoner to be selected to turn on the light is

\(w_k=\frac{N}{k}\)

days.

Another way to see this result has been suggested by Rutgers mathematics Professor Siddhartha Sahi, one of the original founders of the science club in Princeton and a colleague and friend of Gyan’s. Professor Sahi noted that the wait time w_k could be seen as an expected value. The probability that one of the k prisoners will be selected is k/N, and if the prisoner is selected, he will be in the room for one day. On the other hand, if a prisoner who has already turned on the light is selected, then the wait time will be 1 + w_k : one day will be consumed by the selected prisoner who has already turned on the light and then there will be an additional wait of w_k to select the next prisoner who has not turned on the light. Thus,

\(w_k=\frac{k}{N}(1)+\frac{N-K}{N}(1+w_k)\)

Solving for w_k, we get

\(w_k=\frac{N}{k}\)

the same result we obtained using the geometric distribution.

The average time that Bob will wait to count each prisoner who has turned on the light is the reciprocal of his probability of being selected. Hence the average number of days for the kth prisoner to get into the room followed by Bob is

\(w_k=\frac{N}{k}+\frac{N}{1}=\frac{N(1+k)}{k}\)

This is the average number of days to count the kth prisoner,. The total number of days is the sum of this quantity for k from 1 to N-1. Hence,

\(w_N=\sum_{k=1}^{N-1}\frac{N(1+k)}{k}=N(\frac{2}{1}+\frac{3}{2}+\frac{4}{3}+\ldots+\frac{N}{N-1})\)

We can write this series as

\(w_N=N\sum_{i=0}^{N-2}\frac{N-i}{N-i-1}\)

Note that

\(\frac{N-i}{N-i-1}=1+\frac{1}{N-i-1}\)

so

\(w_N = N\sum_{i=0}^{N-2}1+N\sum_{i=0}^{N-2}\frac{1}{N-i-1}=N(N-1)+N\sum_{i=0}^{N-2}\frac{1}{N-i-1}\)

Set j = N - i - 1 and thus

\(N\sum_{i=0}^{N-2}\frac{1}{N-i-1}=N\sum_{j=1}^{N-1}\frac{1}{j}\)

Finally,

\(w_N=N(N-1)+NH_{N-1}\)

where

\(H_{N-1}=\sum_{j=1}^{N-1}\frac{1}{j}\)

the N-1 th harmonic number.

The harmonic numbers are the finite sums of the reciprocals of the integers. The first few harmonic numbers are H₁ = 1, H₂ = 3/2, H₃=11/6, and H₄ = 25/12.

The expected time to win the game is not all the prisoners need to make a decision. The wait time is random, so they will also need an estimate of the standard deviation of the wait time to account for uncertainty. Using the geometric distributions, and the fact that Bob’s selection is independent of every other prisoner’s selection, we can add the variance of Bob’s wait time to the other prisoner’s wait time. The total variance of the wait time is:

\(VAR(w_N)=N(N-1)^2+N^2\sum_{k=1}^{N-1}\frac{1}{k^2}-NH_{N-1}\)

We can also derive an extremely accurate approximation for relatively small N. For N sufficiently large, the harmonic numbers can be approximated as

\(H_{N-1}=\ln(N-1)+\gamma\)

where γ ≈ 0.5772, the Euler-Mascheroni constant. Thus, for sufficiently large N, the expected waiting time in days to win the game is

\(w_N\approx N(N-1)+N\ln(N-1)+N\gamma\)

Similarly, we can write the variance as

\(VAR(w_N)\approx N(N-1)^2+N^2\frac{\pi^2}{6}-N\ln(N-1)-N\gamma\)

where we have made use of Euler’s famous Basel problem relation:

\(\sum_{k=1}^{\infty}\frac{1}{k^2}=\frac{\pi^2}{6}\)

We can check our large N approximation against this table. For N = 35, the expected wait time is 35*34+35*ln(34)+35*0.5772=1333.62 days. The variance is 35*34² + 35*π²/6 – 35*ln(34)-35*(0.5772) = 90,254.72. and the standard deviation is the square root of the variance, 205.74 days. The approximations are extremely accurate for relatively small N.