The Doors

It was the first evening of the 2008 School of Information Theory, and Paul Cuff, then a grad student at Stanford, had just shared a probability puzzle about doors (not the Monty Hall problem). I don’t remember exactly how we started on puzzles, but I am pretty sure people had grown tired of my Ali G impersonation. At some point, I had shared a puzzle about dice that has a solution in the spirit of Paul’s puzzle, which may have been the inspiration.

We found a strategy that would work, but calculating the probability seemed a little tricky. When I asked Paul, he mentioned that the probability was about 1/3 but that he hadn’t gleaned any special insights from it. Thoughts about the puzzle were quickly replaced with the more common preoccupations of a final-year graduate student: finishing a dissertation and finding a job. The “about 1/3” result entered my head as a folk theorem.

Recently, I posed the puzzle to Jim and Chrysteena, two friends in the San Francisco improv community. Jim designs puzzles and seemed dissatisfied when he evaluated the probability for the candidate solution purported to be the best. I quoted the folk theorem, but I was dissatisfied, as well, and I thought it was time to revisit the puzzle.

100 Doors Puzzle

There are 100 people and a room with 100 doors. Behind each door is the name of exactly one of the 100 people such that every name is behind exactly one door. The location of the names are unknown to the 100 people. The 100 people are then asked to play the following game:

  1. Each person is given a chance to go into the room and open 50 doors.
  2. After a person opens 50 doors, the room is reset to the state it was in before entry, and the person who entered may not communicate with any of the other people for the remainder of the game.
  3. The game ends in victory if and only if each of the 100 people opens the door with his or her name. In other words, if any one person fails, everyone loses.

If the location of the names behind the doors is chosen at random, find a strategy that maximizes the probability of victory.

Candidate Solution

It helps to look at cases with a smaller number of doors to build intuition. Let’s first consider two doors and two people, in which each person is allowed to open one door. Note that if both people open the same door, then they are guaranteed to lose since we require that they both find their names. Thus, the best strategy is for them to choose separate doors, at which point the probability of them winning is \frac{1}{2}. Note that this matches the probability that one of them finds his or her name, so it is optimal.

Now let’s move to four doors, four people, in which each person is allowed to open two doors. After some thought, one strategy that would generalize to 100 doors is to arrange the names in alphabetical order and assign a number to each name based on where it is in the ordering, e.g. the first name in alphabetical order is assigned the number 1, and the last is assigned 100. Then, each person starts by opening the door with the number corresponding to his or her name. Upon opening the door, that person will see a new name, which has its own number associated with it in the alphabetical ordering, and will then proceed to open the door associated with this new number. The process repeats until all tries are exhausted.

If one follows this approach, the cases leading to victory are those in which the process of going through the subsequent doors will cycle through to each person’s name within 50 tries in the case of 100 doors, or within 2 tries in the case of 4 doors. For instance, with 4 doors, victory occurs in a case like the following:

Door 1 (Bob), Door 2 (Alice), Door 3 (Dennis), Door 4 (Cindy)

Bob would start at door 2, see Alice’s name and then go to door 1, where he would find his name. Following the approach for the others results in something similar. On the other hand, we fail if we have a case like this:

Door 1 (Bob), Door 2 (Cindy), Door 3 (Alice), Door 4 (Dennis)

Again, Bob would start at door 2, which would give him Cindy’s name and lead him to door 3, which would give him Alice’s name, by which point he has exhausted his two tries without finding his name. Since one person failed, everyone loses.

It turns out that for four doors, there are 10 cases among the 24 permutations that have these smaller cyles, resulting in a victory with probability \frac{5}{12}, which is close to \frac{1}{2}. For 100 doors, there’s the folk theorem.

Probability of Victory

One thing that has bothered me in the formulation of the puzzle is that the focus is to maximize the probability, but it’s unclear to me whether the candidate strategy above does this. If “about 1/3” continues to hold as the probability of victory as the number of doors increases say even beyond 100, then at least there is a sense that this is a scaleable strategy if not the best since no strategy can exceed 1/2. On the other hand, if the probability decays to 0, it raises a new question to understand why that’s the case, if all strategies decay to a victory probability of 0 as the number of doors increase, or if there exists a strategy that is within some bound \Delta < \frac{1}{2} of \frac{1}{2}.

We can start asking these questions if we have an expression for the probability of victory. Let’s consider n = 2k doors, where k represents the number of tries, and n = 100 in the original problem. We have characterized the victory cases as those in which the permutation of doors can be represented as cycles of at most k. To calculate the probability, we can use the cycle index of the symmetric group S_n as

Z(S_n) = \sum_{j_1+2 j_2 + 3 j_3 + \cdots + n j_n = n} \frac{1}{\prod_{i=1}^n i^{j_i} j_i!} \prod_{i=1}^n a_i^{j_i},

where a_i denotes cycles of length i.

It turns out the cycle index of the symmetric group can be expressed as the recurrence

Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l})

Let’s define F_n(a_1, \ldots, a_n) = Z(S_n) to highlight the dependence on the cycles. Thus, we can rewrite the above equation as

F_n(a_1, \ldots, a_n) = \frac{1}{n} \sum_{l=1}^n a_l F_{n-l}(a_1, \ldots, a_{n-l}).

Let’s define the cumulative distribution function (CDF) F_{n}^{(i)} as F_n(a_1, \ldots, a_n) evaluated at a_l = 1, l \leq i and a_l = 0, l > i. In words, F_{n}^{(i)} is the probability that all cycles are of length i or less.

Thus, if we can find an expression for F_{n}^{(k)}, we can evaluate it at F_{100}^{(50)} to get our result. The results are contained in Propositions 1 and 2 below, where Proposition 2 is reminiscent of our folk theorem, which yields a probability of 0.306, which is slightly less than 1/3. Furthermore, Corollary 1.1 indicates that we decrease monotonically to this probability, so regardless of the number of doors, this strategy is within 0.2 of \frac{1}{2}, the upper bound on how well one could possibly do.

Proposition 1. F_{2k}^{(k)} = F_{n}^{(k)} = 1 - \sum_{m=k+1}^n \frac{1}{m}.
Proof: The first equality is by definition, so we simply need to show the second equality. For i \leq j, we can evaluate the probabilities as

F_{2j}^{(i)} = \frac{1}{2j} \sum_{l=1}^i F_{2j-l}^{(i)}

F_{2j}^{(2j-i)} = \frac{1}{2j} \sum_{l=1}^i F_{2j-l}^{(2j-i)} +\frac{1}{2j}\sum_{m=i+1}^{2j-i} F_{2j-m}^{(2j-m)} = \frac{2j-2i}{2j}+ \frac{1}{2j} \sum_{l=1}^i F_{2j-l}^{(2j-i)}

F_{2j+1}^{(i)} = \frac{1}{2j+1} \sum_{l=1}^i F_{2j+1-l}^{(i)}

F_{2j+1}^{(2j+1-i)} = \frac{1}{2j+1} \sum_{l=1}^i F_{2j+1-l}^{(2j+1-i)} + \frac{1}{2j+1} \sum_{l=i+1}^{2j+1-i} F_{2j+1-l}^{(2j+1-l)} = \frac{2j+1-2i}{2j+1} + \frac{1}{2j+1} \sum_{l=1}^i F_{2j+1-l}^{(2j+1-i)}.

Note that if i \leq j, then i - 1 \leq j, so we can apply the same result to get that

F_{2j}^{(2j+1-i)} = \frac{2j-2(i-1)}{2j}+ \frac{1}{2j} \sum_{l=1}^{i-1} F_{2j-l}^{(2j+1-i)}

and substituting this into our expression for F_{2j+1}^{(2j+1-i)} yields

F_{2j+1}^{(2j+1-i)} = \frac{2j}{2j+1} (F_{2j}^{(2j+1-i)} - \frac{2j-2(i-1)}{2j}) = F_{2j}^{(2j+1-i)} - \frac{1}{2j+1}.

Likewise, one can similarly derive

F_{2j}^{(2j+1-i)} = F_{2j-1}^{(2j+1-i)} - \frac{1}{2j}.

Starting with the base case that F_{2k}^{(k)} = F_{n}^{(k)} = F_{n-1}^{(k)} - \frac{1}{n} and the above inductive steps, one can conclude that

F_{n}^{(k)} = F_{k}^{(k)} - \sum_{m=k+1}^{2k} \frac{1}{m}.

However, F_{k}^{(k)} = 1, so we have our result.

Corollary 1.1. F_{n+2}^{(k+1)} = F_{n}^{(k)} - \frac{1}{(n+2)(n+1)}.

Proposition 2. \lim_{k \rightarrow \infty} F_{2k}^{(k)} = 1 - \ln 2 \approx 0.306
Proof: From Proposition 1, we can write

F_{2k}^{(k)} = 1 - \sum_{m=k+1}^{2k} \frac{1}{m}. Note that we can rewrite the summation

\sum_{m=k+1}^{2k} \frac{1}{m} = \sum_{i=1}^{k} \frac{1}{k+i} = \sum_{i=1}^{k} \frac{1}{1+i/k} \frac{1}{k}.

The key is to observe that this is simply a Riemann sum approximating the integral

\int_{0}^1 \frac{1}{1+x} dx = \ln 2,

which converges as we let k \rightarrow \infty.

Advertisements
This entry was posted in Probability, Puzzle. Bookmark the permalink.

8 Responses to The Doors

  1. Sridhar Ramesh says:

    Hm… it seems to me there’s a much simpler approach to calculating the probability of success: failure only occurs if there is some cycle of greater than $k$, and there can be at most one such cycle. So the probability of failure is the sum, over $j > k$, of the number of ways to pick $j$ people to be in the big cycle ($\binom{2k}{j} = \frac{2k!}{j! (2k – j)!}$) times the number of ways to put an ordering on this big cycle ($j!/j$, accounting for the fact that the starting point of a cycle is arbitrary) times the number of ways to permute everyone else ($(2k – j)!$). Each of these terms is $1/j$, so the sum is $H_{2k} – H_{k}$, where $H_i = 1/1 + 1/2 + …. + 1/i$ is the $i$th harmonic number. So the probability of success is one minus that, and one can of course approximate harmonic numbers by natural logs if one likes.

  2. Sridhar Ramesh says:

    Whoops, I forgot to mention the factor of $1/(2k!)$ to turn this from a count into a probability, but I guess that’s obvious enough. Also, I clearly don’t know how to turn on math mode here. And of course, at the end I carry out the same steps you already noted; the point is just that the beginning can be made much easier. I’d edit if I could, but ah well…

  3. Sridhar Ramesh says:

    And as for the optimality: there’s a very nice proof of it by Curtin and Washauer here: http://www.maths.tcd.ie/~onash/pity_the_prisoners_files/locker-problem.pdf

  4. Sridhar Ramesh says:

    Sorry, “Warshauer”. I can’t get any of these comments right…

    • K says:

      Thanks for sharing the optimality proof (that’s a slick argument) and the more straightforward derivation. I hadn’t thought about the fact that if they fail, there will be exactly one large cycle.

  5. Sridhar Ramesh says:

    It also occurs to me that there’s another way to look at the optimality proof which doesn’t require actually thinking about the “records-to-cycles bijection” or even calculating the success probability; to wit:

    Let us say that players may not open any door they know not to be theirs, and the game ends immediately when a player uses up their 50 doors unsuccessfully. This makes no difference to anything so far. Suppose we furthermore consider not resetting the room inbetween players’ turns. This can’t hurt the players, and perhaps could help them.

    Note that:

    A) In this non-resetting game, the players have no control over their success probability. We can always think of the doors’ values as undetermined till they are first opened, at which point they are randomly assigned from the remaining names, making any unopened door as good as any other, so it’s all blind luck.

    B) The cycle-chasing strategy isn’t significantly affected by whether doors reset: either way, those players whose doors were previously opened will find their own name and break no new ground in door-opening [the only difference is whether they go straight to their name or meander with previously opened doors first], while players whose doors have never yet been opened (and who therefore are not in any previous players’ cycles) will chase through “fresh” doors looking for theirs [in the same manner regardless of resetting].

    Thus, the cycle-chasing strategy (whether or not the doors reset) is as good as any other strategy would be if the doors didn’t reset, which is as good or better than any strategy when the doors do reset, establishing optimality.

    • K says:

      Yes, the stipulation that a player cannot open a door known not to be theirs and the non-resetting condition appear to create an equivalent to Game 2 from the other optimality proof in the sense that it effectively skips over players whose doors have already been opened by someone else and prevents players who have find their doors from uncovering additional ones.

      • Sridhar Ramesh says:

        Right. I didn’t mean to imply that this was different from Game 2; rather, my goal was to demonstrate how one could analyze Game 2 (as well as its relation to the cycle-chasing strategy for Game 1) without having to understand the records-to-cycles bijection or carry out any calculations. [Not that understanding more things is ever a bad thing, but sometimes there is also a greater clarity of understanding to be found in shearing away distracting details]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s