A statistical approach to the prisoners problem

Question

Two days ago, I found this problem on reddit (I didn't have access to reddit when I did the math, so I did it with 24 instead of 23, and I decided the warden picked someone every day, not "whenever he feels like it"):

A prison warden tells 24 prisoners he has a "game" for them. Once per day, the warden chooses one prisoner at random and leads them to the Switch Room. The aptly named Switch Room has two switches, both at the Off position at first, that are connected to nothing. The called prisoner has to toggle exactly one switch.

At any time, any prisoner can go to the warden and tell him that the 24 prisoners all went to the Switch Room at least once. If that's true, they're all freed. If not, they're going to be made into sausages for the other inmates or something.

The prisoners can come up with a plan now but won't ever be able to communicate again until someone tells the warden.

---

EDIT After some debating with @alex.jordan, I wanted to clarify my intent. My perspective is that this is a metaphor for "how would you tell that N distinct events, uniformly and randomly happening, all happened at least once if you only had 2 bits to spare", and has nothing to do with an actual warden (who could be biased in his random choices or use a different distribution model to screw up the prisoners), or actual prisoners.

I am solely interested in an answer that assumes a prisoner is selected randomly and uniformly once every day (not "from time to time" as stated in the reddit riddle), so you can safely ignore any assumption that the warden is out there to grind the prisoners to sausages or selects people with a bias or just won't ever select anyone.

---

The "classical" solution is that the prisoners designate one leader. When a prisoner enters the Switch Room (except the leader), if they've never been there and find the first switch in the Off position, they turn it on. Otherwise, they toggle the other switch. When the leader enters the Switch Room, if he sees the first switch in the On position, he knows that someone who's never been there before has been, so he counts one and turns off the switch. When he has counted to 23, he knows that everyone has been there at least one.

The thing is, this solution sucks. Assuming 24 prisoners again, and knowing they're picked at random, we can represent the whole thing as a series of geometric distributions (this also assumes I'm doing it right, which I may not be):

$$ X: \text{number of days before the Leader goes to the Switch Room}\\ X \sim Geom\left(\frac{1}{24}\right)\\ E(X) = 24, Var(X) = 552\\ $$ $$ Y_n: \text{number of days before one of the n remaining prisoner}\\ \text{goes to the Switch Room for the first time (n from 1 through 23)}\\ Y_n \sim Geom\left(\frac{n}{24}\right)\\ E(Y_n) = \frac{24}{n}, Var(Y_n) = \frac{24 (24-n)}{n^2} $$

Since expected values and variance can be linearly added, we can expect that the Leader will tell the warden after on average 642 days, with a standard deviation of 116, by assuming the leader will go $E(X)$ days after any given prisoner went for the first time as modeled by $E(Y_n)$:

$$ Z: \text{Number of days before the Leader announces everyone's been to the Switch Room}\\ E(Z) = \sum_{n=1}^{23}E(X) + E(Y_n) = 552 + \sum_{n=1}^{23}E(Y_n) \approx 552 + 89.6229 \approx 641.6229\\ Var(Z) = \sum_{n=1}^{23}Var(X) + Var(Y_n) = 12696 + \sum_{n=1}^{23}Var(Y_n) \approx 12696 + 833.3521 \approx 13529.3521\\ \sigma = \sqrt{13529.3521} = 116.3157 $$

Very simple maths tell us that after 642 days, every prisoner's been on average 26 times to the Switch Room. This looks like a horrible waste of time.

I'm pretty sure it's possible to calculate how many days you would need to wait before you have 99% chances (or higher) that each prisoner has been there. Problem is, I'm only halfway through my college stats class, and we've only seen easy distributions where successes are independent, so I'm not too sure how to tackle that.

How would you calculate the chances that each prisoner has been to the Switch Room after $Z$ days?

---

EDIT I just made a quick and dirty program to run "simulations", and it takes on average 90.6 days until every prisoner has visited the Switch Room, with a standard deviation of 28.5. Making that into a normal distribution, it should be around 157 days before we can say with 99% certainty that each prisoner has visited the Switch Room at least once, and 179 days for 99.9% certainty. Needless to say, you're pretty safe after 641 days...

It's an empirical technique and it doesn't really feel mathematically satisfying, so the question is still open for better answers.

Answer 1

It is even worse than that. On day $1$ some prisoner turns the switch on (unless the leader goes first). Then all the prisoners that visit next can't turn it on, so those visits are wasted.

The page here has a good writeup. Your solution is Solution 6: Simple count and he claims with 100 prisoners you need 28 years. There are some strategies, and I found a very nice paper that I can't find again.

For your question, we can pretend that each prisoner is independent of each other (which is a much better approximation than it sounds). After $d$ days the prisoner has $(\frac {23}{24})^d$ chance of not having visited the room. To have a $99\%$ chance that they all have visited, we need $$(1-(\frac {23}{24})^d)^{24}=0.99 \\1-(\frac {23}{24})^d=0.99^{\frac 1{24}}\\(\frac {23}{24})^d=1-0.99^{\frac 1{24}}\\d=\frac {\log (1-0.99^{\frac 1{24}})}{\log \frac {23}{24}}\approx 182.76$$ You are right that this is much faster

Answer 2

A problem with what you are trying to do is that you are not considering the sadism of the warden. Both your simulation and @Ross's estimation assume that prisoners are sent in a uniformly random way to the switch room. It's debatable whether or not "the warden chooses one prisoner at random" really means that. And I have heard versions of this problem that leave out the phrase 'at random'. The warden could thwart these strategies by choosing some prisoners with 1/100 the probability of others. The warden could be really sadistic and purposely never choose one particular prisoner. Or the warden could be using his human brain to "randomly" pick a prisoner, which will fail to be a truly uniformly random selection.

The classic solution that involves a leader counting is deterministic in that if the leader counts to 24 (23?), it's over for sure. If you were one of these prisoners, would you really bet that the warden is using a true uniformly random selection?

---

EDIT: OP asks "How would you calculate the chances that each prisoner has been to the Switch Room after Z days?"

My response is essentially that you cannot do this, until you explicitly assume a particular distribution for how prisoners are randomly selected. And why on earth would you do that if this or any similar situation was real?

I don't understand the down votes, unless someone

• thinks that "random" (which means 'cannot be predicted') means the same thing as 'uniformly random'
• and think I'm just being cheeky and that I might as well let the warden tamper with switches. But allowing the warden to use other random selection processes does not make them a liar, like tampering with the switches would.

Part of the beauty of the way I understand this problem and the 'leader' solution is that you find a strategy that thwarts the warden's human imperfections no matter how the selection process goes. We have to assume the warden is honest or else there is no point to any of it.

Answer 3

As multiple people already suggested (but no one actually answered), this is essentially the same as the coupon collector's problem: in a set of $n$ unique coupons that you draw with replacement, how many draws will it take until you have drawn each coupon at least once?

This kind of model is suited for combining multiple geometric distributions with equal probabilities (as is the case here). Per the two links above, letting $T_n$ be the number of trials to collect all $n$ coupons (or to send all $n$ prisoners to the Switch Room), then

$$ E(T_n) = n \cdot H_n\\ Var(T_n) = \frac{\pi^2 n^2}{6} - n\cdot H_n $$

Therefore, reusing my $Z$ variable:

$$ Z: \text{Days before the Leader announces all prisoners been to the Switch Room}\\ E(Z) = E(T_{24}) = 24 \cdot H_{24} \approx 90.623\\ Var(Z) = Var(T_{24}) = 96\pi^2 - 24H_{24} \approx 856.859\\ \sigma = \sqrt{Var(Z)} \approx 29.2722 $$

Both values closely match what I got with my simulations.

It looks like it would be fairly hard to assess a probability between 0 and 1 for whether or not all the prisoners will have visited the room after $z$ days following exactly the distribution curve, seeing how it is left-biased. Approximating it as a normal distribution $N(856.859, 29.2722^2)$, there are 99% chances that all the prisoners will have visited the Switch Room after 158.72 days; 99.9% chances after 181.081 days; 99.99% after 199.487 days; and after 233.822 days, my venerable calculator can't handle a number small enough to distinguish the probability from 1.

Answer 4

To remove the independence assumption that Ross uses for simplification leaves you with a messy equation, but one that could be solved to arbitrary precision if you allow a computer.

After $d$ days, $24^d$ possible sequences may have come to pass. How many of these have each prisoner represented? Well, we could subtract the ones without prisoner #1, then those without #2 and so on. But we've overcounted what to subtract this way. We'd throw back in those with #1 and #2 missing. If you're familiar with the inclusion-exclusion principle, then what this leads to is

$$P(d) =\frac{24^d-\binom{24}{23}23^d+\binom{24}{22}22^d-\cdots\pm\cdots-\binom{24}{1}1^d}{24^d}$$

where $P(d)$ is the probability that all prisoners have visited the room by day $d$. An equation like $P(d)=0.99$ is not the nicest thing to try to solve, but you could get computer assistance. It may be helpful to recognize that you are only looking for integer $d$.

@Ross's result suggests $d$ should be close to $182.76\ldots$ for 99% certainty. Well, $P(182)=0.989655\ldots$ and $P(183)=0.990085\ldots$, so it's hard to argue that it is worth the effort to be more precise than making an independence assumption.