Actually, I have no idea if anyone actually reads this blog anyway, so I might just be shouting at nothing.
In any case, here.
PART 1: The Solution
The prisoners will choose one of them to be the "spokesperson" for the group. Let's call this prisoner the principal. The prisoners all decide that the principal is the only one who can offer the answer "Yes" to the warden; all other prisoners will always say "No" until the challenge is complete.
The switches both start in the down/off position. Let's call the left switch Switch 1 and the right switch Switch 2. Switch 1 will be the indicator switch, and Switch 2 will be the "dummy" switch.
When a prisoner is selected, there are two possible cases that matter: whether or not the prisoner is the designated principal.
CASE 1: The prisoner selected is not the principal. The prisoner will ask himself, "Have I turned Switch 1 'on' before in this challenge?" If the answer is yes, then he will toggle Switch 2. If the answer is no, he will then examine Switch 1. If Switch 1 is already on, then he will toggle Switch 2. If Switch 1 is not on, then he will toggle Switch 1 to the on position. If this prisoner turned Switch 1 on, then during any subsequent visits to the room, this prisoner will only toggle Switch 2. Every prisoner who is not the principal must always respond "No" to the warden's question.
CASE 2: The prisoner selected is the principal. The principal is also tasked with the job of keeping a cumulative count. When he enters the room, he will examine Switch 1. If Switch 1 is on, he will add 1 to the cumulative count and will toggle Switch 1 to the off position. If Switch 1 is not on, he will add 0 to the cumulative count and will toggle Switch 2. Naturally, if it is the principal's first time to the room, he will also add an additional 1 to the cumulative count for himself. When the principal's cumulative count reaches n, the number of prisoners, then he will answer "Yes" to the warden's question.
This strategy takes a stochastic number of days to complete, which frustrated me at first. Essentially, Switch 1 being on means that a new prisoner has had the opportunity to turn Switch 1 on. (Switch 2 means nothing.) So the one person who is designated to check Switch 1 knows with certainty that n unique prisoners have been in the cell when he arrives to the room to an on Switch 1 for the (n - 1)th time. (The principal is obviously the last case.)
PART 2: Distribution Analysis
Two questions immediately popped into my head: How can the distribution of days that it will take to complete this challenge be characterized (specifically, what are the mean and variance of the number of days it will take)? How sensitive is this distribution to n, the number of prisoners?
Before answering these questions, we need a definition of a common discrete probability distribution.
The geometric distribution is a discrete distribution that counts the number of independent Bernoulli trials (essentially binary "success"/"fail" trials) that must be completed until a "success" is reached. A common example of a geometric distribution is, "How many flips of a coin does it take to get a 'heads'?" In this example, the trials are coin flips, and a "success" is getting a heads. Because the trials are assumed to be independent, each trial has the same success probability, denoted as p. In the coin-flip example, p = 1/2 if the coin is fair.
If a random variable X has a geometric distribution, we denote it as X ~ geom(p).
Here are two properties about the geometric distribution that we care about for this problem:
The mean of X, E(X), is 1/p. This value represents the expected number of trials needed to be conducted until a "success" is achieved. In the coin-flip example, we expect that on average, it will take two flips to get a "heads".
The variance of X, var(X), is (1-p)/p2
We will use these properties in determining the mean and the variance of the solution to this riddle.
PART 2a: Finding the Mean
Let's start with finding E(Tn), the expected number of days it will take until a solution is reached, as a function of n, the number of prisoners. Let's start with the case of n = 2 just to simplify the problem.
n = 2
For simplicity's sake, let's suppose the two prisoners have selected Prisoner 1 as the principal. (It doesn't actually matter which prisoner is selected to be the principal.) On day 1, the warden selects one of the two at random. At this point, the amount of time until a new prisoner can toggle Switch 1 follows a geometric distribution with probability 1 (E(X) = 1, Var(X) = 0). This first selection is critical; there are two possible sample paths that can follow.
CASE 1: The first prisoner selected is the principal. When the principal leaves, he sees Switch 1 as down, so he knows the other prisoner has not been in yet. He can add 1 to his cumulative count. Once he returns, the amount of time until Prisoner 2 enters the room follows a geometric distribution with probability 1/2. (E(X) = 2). Then, once Prisoner 2 has been in, the principal must go back in again to receive the message through Switch 1 that Prisoner 2 has been in. The amount of time that this takes again follows a geometric distribution with probability 1/2. At that point, the principal can answer the warden's question correctly with a "Yes", and all prisoners can go free. On average, this will take 1 + 2 + 2 = 5 days.
CASE 2: The first prisoner selected is not the principal. Prisoner 2 flips Switch 1 up. The next "success" is when the principal enters the room. The amount of time that this takes again follows a geometric distribution with probability 1/2. When the principal enters, he will see Switch 1 up, and he immediately knows that all prisoners have been in since he has also been in. On average, this will take 1 + 2 = 3 days.
Now we weight these two lengths of time by the probability of each case occurring. Since selection is equally likely and there are two prisoners, each case can occur with probability 1/2. Therefore, the overall mean length of time that it will take for n = 2 prisoners to get out is 0.5*5 + 0.5*3 = 4 days. So E(T2) = 4.
Now let us consider the case of n = 3 with the same logic.
n = 3
On day 1, the amount of time until a new prisoner can toggle Switch 1 is geometric with probability 1. However, we must again condition on which prisoner was chosen first.
CASE 1: The first prisoner selected is the principal. He will add 1 to his count. After he leaves, the amount of time until a new prisoner enters the room and can toggle Switch 1 is geometric with probability 2/3. After that, the principal must be selected again; the time this takes is geometric with probability 1/3. At this point, there is one prisoner left who must toggle Switch 1 for the first time, which will occur after an amount of time defined again by a geometric distribution with probability 1/3. The principal must once again be selected, adding on another geometric with probability 1/3. Adding up the mean of all these distribution gives an expected time of 1 + 3/2 + 3 + 3 + 3 = 11.5 days.
CASE 2: The first prisoner selected is not the principal. After this first prisoner, the next time Switch 1 will be touched is when the principal enters. This happens after geom(1/3) time. At that point, the principal can add 2 to his cumulative count. After he leaves, it is another geom(1/3) until a new prisoner can turn on Switch 1. Then the principal must be called again, which occurs after geom(1/3) time. This gives an expected time of 1 + 3 + 3 + 3 = 10 days.
Now we weight these two cases. Case 1 occurs with probability 1/3, and Case 2 occurs with probability 2/3. Therefore, the overall mean length of time that it will take n = 3 prisoners to get out is (1/3)*(23/2) + (2/3)*(10) = 10.5 days.
n = 4 [Abridged, but following the same logic.]
CASE 1: (Principal first, occurs with probability 1/4)
geom(1) + geom(3/4) + geom(1/4) + geom(2/4) + geom(1/4) + geom(1/4) + geom(1/4) yields a mean of 61/3 days.
CASE 2: (Principal not first, occurs with probability 3/4)
geom(1) + geom(1/4) + geom(2/4) + geom(1/4) + geom(1/4) + geom(1/4) yields a mean of 57/3 days.
The overall mean length of time that it will take n = 4 prisoners to get out is 58/3 days, or 19.333 days.
And so we can see a pattern forming. For a general n, we can condition on whether or not the first prisoner selected is the principal.
CASE 1: (Principal first, occurs with probability 1/n)
geom(1) + geom((n-1)/n) + geom(1/n) + geom((n-2)/n) + geom(1/n) + ... + geom(2/n) + geom(1/n) + geom(1/n) + geom(1/n). The mean of the sum of these random variables can be written as follows:
CASE 2: (Principal not first, occurs with probability (n-1)/n)
geom(1) + geom(1/n) + geom((n-2)/n) + geom(1/n) + geom((n-3)/n) + geom(1/n) + ... + geom(2/n) + geom(1/n) + geom(1/n) + geom(1/n). The mean of the sum of these random variables can be written as follows:
The mean for Case 2 is written in this way to simplify the sum. In Case 2, the principal counts 2 when he first arrives as opposed to just 1 in Case 1. So Case 2 does not have the geom((n-1)/n) term, but otherwise, the means are identical. So we can simply subtract off n/(n-1).
When we weight the mean from Case 1 by 1/n and the mean from Case 2 by (n-1)/n, we get the following beautifully simple result:
We see that the mean is quadratic and increasing in n, the number of prisoners. Plotted below is the mean number of days that will pass until the prisoners can all be released, as a function of n (from 1 to 15):
PART 2b: Finding the Variance
Of course, in practice, the mean, or expected value, rarely actually occurs. In most cases, such as when n = 3, the expected value is actually not a possible value that the distribution can take, since the length of time will always be an integer number of days.
Therefore, we may be interested in knowing how "spread out" the distribution is for the time until release. Naturally, we expect the distribution to be more spread out, or more variable, as n increases. But how can we precisely calculate the variance of this strategy?
We will make extensive use of the fact that the time until escape is a sum of geometric random variables, for which we know the variance. We will also make use of the fact that each prisoner is randomly selected. What this means is that all individual trials are independent of each other (hence we can use a geometric distribution); but furthermore, we can assume that all geometric distributions in the sum are independent of each other. This is a critical assumption, as the equation
Var(X + Y) = Var(X) + Var(Y)
in general does NOT hold unless the random variables X and Y are independent of each other. Since all of our geometric random variables are independent, we can in fact use this equation to our advantage.
Variance is defined as follows:
Var(X) = E[(X - E(X))2]
Verbally, this means that the variance of X is defined as the expected squared deviation from the mean of the X. This value is squared to ensure that the deviation is represented as a positive value; it unfortunately places disproportionate weight on large deviations.
As an aside: the phrase "standard deviation" is used in common culture frequently. The standard deviation is simply the square root of the variance. By Chebyshev's Inequality, for every distribution, at least 75% of a distribution falls within 2 standard deviations of the mean, and at least 88.9% of a distribution falls within 3 standard deviations of the mean. As a general rule of thumb, if a distribution is roughly bell-shaped, then at least 95% (or more) of the distribution will be within 3 standard deviations of the mean. That is why the standard deviation is significant.
Unfortunately, in this problem, calculating the variance is not straightforward, as it again depends on which type of prisoner is selected first. We unfortunately cannot just condition on what happens first and then weight the variance of each case by the probability of each first selection; instead, we must use the formula for conditional variance and condition on the first selection.
Var(X) = E(Var(X | Y)) + Var(E(X | Y))
It is important to note that E(X | Y) is a random variable, as is Var(X | Y). Otherwise, taking the variance and mean of these values, respectively, would not make sense.
We define the random variable Y as follows:
We could have defined it the other way around, but it does not matter. What matters is what value X, or in our case, Tn, takes on when Y is 1 or 0. Fortunately, from the exercise in calculating the mean, we know what possible values this random variable can take. We will use g() to denote a geometric random variable.
We already know what E(Tn | Y) is. This random variable's possible values are the means that were calculated above. Case 1 represents E(Tn | Y = 1) and Case 2 represents E(Tn | Y = 0). Consequently, we also know E(E(Tn | Y)), which by the definition of conditional expectation, is just E(Tn). We can use these values to calculate the second part of the conditional variance formula, Var(E(Tn | Y)). This will be done by using the basic definition of variance, as defined above (expected squared deviation from the mean).
After a whole bunch of terms cancelling out, this simply reduces to:
Intuitively, this should make sense. As n grows large, the difference in possible values for E(Tn | Y) asymptotically and decreasingly approaches 1. Additionally, the probability of one of the two values occurring approaches 1. Both of these factors explain why the variance of E(Tn | Y) is decreasing in n.
Now we must calculate E(Var(Tn | Y)). This is where we can weight the variances that arise based on which prisoner is selected first. We must take the variance of the two possible outcomes for Tn. This is fairly simple by the formula for the variance of a geometric random variable, although it is a mess to write out.
I hope you're good at rearranging your fractions, because nicely enough, it simplifies to this:
Recall that we must add E(Var(Tn | Y)) and Var(E(Tn | Y)) to find Var(Tn). When we do that, the 1/(n-1) terms cancel out, and we are left with the following formula for the variance:
This result is also strikingly simple. The variance is cubic in n, implying that increasing n has a greater impact on the variance than on the mean, which intuitively makes sense. Plotted below is the variance of the time to be released, as a function of n (from 1 to 15):
Now, for you naysayers out there, I also built a simulation to model this game strategy with different numbers of n to verify if these results were correct. They are.
Anyways. I had a good nerding out about this. Hope you enjoyed this problem.
