10
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ You might find this article relevant. (Disclaimer: I haven't verified whether it answers your specific question; actually I believe it doesn't.) $\endgroup$ Commented Oct 20, 2013 at 1:32
  • $\begingroup$ Is there any reason for having two switches and requiring the prisoner flip exactly one, rather than simply having one switch which the prisoner can flip or not? The state of the second switch will always be the opposite of the first one after odd-numbered days, and the same as the first on even-numbered days, so it may as well not exist. $\endgroup$ Commented Feb 24, 2014 at 0:51

4 Answers 4

Reset to default
7
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ I add $E(X)$ to the summation to account for "wasted days", and they make up for 552 of the 641 days, so I would think I got that part right. For the rest, I'll think about your answer for a bit and come back to accept, probably ;) $\endgroup$ Commented Oct 20, 2013 at 1:53
  • $\begingroup$ +1 This is the sensible approximation for your question. This is esentially a coupon collector problem. en.wikipedia.org/wiki/Coupon_collector's_problem $\endgroup$ Commented Oct 20, 2013 at 2:16
  • $\begingroup$ @leonbloy: The usual solution to the Coupon collector problem gives you the expected time, not the time until you are $99\%$ sure you have them all. I don't see how to modify the usual approach, which is why I took this one. This would be easy to model to see how good the independence assumption is. I believe it is very close, even though I can't justify it. $\endgroup$ Commented Oct 20, 2013 at 2:44
  • $\begingroup$ I made a program to test (see question update), and the answer should be around 157 days for 99% certainty. 183 days is overestimated by almost exactly one standard deviation. $\endgroup$ Commented Oct 20, 2013 at 5:24
  • $\begingroup$ @zneak: alex.jordan's latest answer confirms this $183$ number with an entirely different (and exact) method without the independence assumption, so something seems to be wrong with your simulation. Did you get 157 out of your simulation directly, or did you just get it by assuming normal distribution somewhere? If you did the latter, then we can see that the assumption of normal distribution is worse than the independence assumption Ross used here. $\endgroup$ Commented Oct 21, 2013 at 2:27
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Interesting: did you plug in $d = 182$ and $d = 183$ into your expression and get those probability numbers, or are they from Ross's independence approximation? (I'm confused by the "Using Ross's result" part of the last paragraph.) $\endgroup$ Commented Oct 21, 2013 at 2:13
  • $\begingroup$ @ShreevastaR Ross's result leads to an answer between 182 and 183, so I used those numbers in my $P(d)$ to see what happened. I was using Excel for the computation, so it's possible there is rounding error, but Excel is usually good up to $10^{-12}$. But thanks - I'll clarify in my answer what I meant. $\endgroup$ Commented Oct 21, 2013 at 2:17
  • $\begingroup$ Very cool, this shows that the independence assumption is really good. Even linear interpolation between those two probabilities gives about $182.8$, which shows that it is excellent. $\endgroup$ Commented Oct 21, 2013 at 2:25
2
$\begingroup$

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.

$\endgroup$
10
  • 2
    $\begingroup$ While I understand your concerns, I don't feel your answer helps me understand the underlying mathematical concepts much better. $\endgroup$ Commented Oct 20, 2013 at 5:44
  • $\begingroup$ An underlying mathematical concept that you may not understand well is the difference between uniform randomness, general randomness, and lack of randomness. I understand that you want to move on to a calculation that assumes uniform randomness. But I think you may have overlooked something of fundamental importance when you say that the classical solution sucks because it takes too long. I don't think you can expect to do better in real world conditions. The warden is a human being and has already revealed his sadism by setting this game up in the first place. $\endgroup$ Commented Oct 20, 2013 at 5:54
  • 1
    $\begingroup$ The warden could also go in and toggle switches without telling anyone and that may break the classical solution. There are endless ways in which this could go wrong if we start assuming the warden doesn't behave: however, in this version of the riddle (and feel free to go check on the Reddit source, there's a reason I included the link), the warden has a uniform random distribution for picking people and he's honest. $\endgroup$ Commented Oct 20, 2013 at 14:49
  • $\begingroup$ If I wanted a clever answer, I'd be going back to Reddit (and God knows there are already dozens of them) or riddles.stackexchange.com if there's such a thing. Given this is math.stackexchange.com, I would expect answers to talk about the actual problem, which is: "after how many attempts will I have picked at random all 24 elements with replacement?" $\endgroup$ Commented Oct 20, 2013 at 15:02
  • $\begingroup$ You're missing my point - I'll give it one more go. I'm a probability and statistics teacher and it is important to me that my students do not misuse these tools in the real world. You can calculate and simulate all you want, but this modeling is just an abstract exercise that does not make for a clever shortcut to the chosen leader solution. If you model like this while working in industry, you'll have lots of failed predictions. See my edits to the question. $\endgroup$ Commented Oct 20, 2013 at 17:29
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.