×   Home   Blog   Newsletter   Privacy   Contact Us   About

Bayes, keys, and prisoners

Paddy slept in and was late for work. As he was leaving the house, in haste, he grabbed one of the two keys that were laying on the kitchen counter, placed this key in his (otherwise empty) pocket, and left.
Of the two keys he could have taken, one was his front door key, and the other was a key to a friend’s garden shed. Both keys appeared identical (I'm using colour in this article just for illustrative purposes), and he had a random coin flip of selecting the key he needed (the key to his front door).
Throughout the morning, this single key floated around in his pocket in a superposition of states. Was it his front door key? Was it a useless shed key? The only true way to find the answer to this cat-like problem is to experience what happens when he returns home and tries the key. It’s fair to say at this point that Paddy has a 50% of getting into his house when he returns home.
At lunchtime, Paddy met his twin sister. Over sandwiches she returned to him his spare front door key that she had borrowed. This spare key is just as indistinguishable as the others. Paddy placed this additional key into the same pocket as the first key.
After a long day of work, Paddy returned home. Upon arrival at his door, he reached into his pocket, pulled out one of the two keys at random, inserted it into the door, and let himself in. It worked!
What is the probability that the other key in his pocket will also open the door?
What is the probability that the other key in his pocket will also open the door?
Advertisement:

Solution

It’s tempting to think that the answer is still 50%, after all, it was 50% before he received the key from his sister, and all we’ve done is removed a successful key (either his sister’s key, or his key if it were correct, and we’re back to where we started). But this is not correct. The probability the key remaining in his pocket will be a front door key is actually 66⅔%
If we use S to describe a shed key, and D to denote a door key, there are four, equally likely, ordered ways in which the keys could be in Paddy’s pocket {SD, DS, DD, DD}. We know that the first key he pulled out was a door key, so it must be a solution in the set {DS, DD, DD}, and of these three, two have another door key as the second key. There’s a 2/3 chance that the second key is also a door key.

Bayesian

Another way to help think about this is to imagine the thought experiment of returning the key back into the pocket and drawing, checking, and then repeating the unlock attempt again, and again. The more unlock attempts you try, the more ‘information’ it gives you about the possible types of key you have in the pocket.
Imagine you have an urn containing two balls. These balls are either both red, or one red and one black. You repeatedly draw a ball from the urn, note its color, then return it. How many times would you need to draw only red balls before convincing yourself that the urn probably only contained red balls?

Bertrand's Box

These types of problem are renderings of the class of puzzles called the Bertrand's Box Paradox. Other examples, including the proverbial Monty Hall problem, the two children (boy/girl) paradox, and the three prisoners. The Monty Hall problem has been written about to death on the internet by far more talented people than myself, so I will quote the Three Prisoners variant below (which originally appeared in a Martin Gardner column).

Three Prisoners

In this classic variant there are three prisoners: A, B, C. The next morning two of them are to be executed, and the third pardoned and released. Prisoner A begs, and begs, the guard to tell him if he, himself, is going to be executed. The guard knows all, but refuses to tell. Finally, prisoner A strikes a deal with the guard “Look, I know you can’t tell me my fate, so instead can you tell me the fate of one of the other two prisoners? Tell me which of the other two will be executed.” (After all, at least one of the other two will be executed). The guard will truthfully tell A which of B or C is to be executed (or if both of them are to be executed, he will flip a fair coin to determine which of B or C to name).
The guard shrugs and says “Prisoner B is going to be executed tomorrow”. This makes A very happy because, according to his logic, his chances of survival have just increased from 1/3 to 1/2 (after all, there are now only himself and C who are in the running for a pardon). Excited with this, he shares his news with C.
C is even more happy! He tells A, “Thanks buddy, I’ll sleep better tonight knowing that I now have a 2/3 chance of being pardoned!”. His logic is that the guard did not give A any new information about A’s fate, so A’s chance of being executed is still 1/3, and, through the stochastic principal that all probabilities must add up to 1, that his personal chances of survival must be the complement of 1/3, and thus he now has a 2/3 chance of a pardon.
Who is correct?

Solution

Prisoner C is correct. With the guard’s revelation, prisoner C’s chances of being pardoned have improved to 2/3.
The guard gave no new information to A about his individual fate (he was only told information about the fate of someone else), so his base chance remains at 1/3.
Enumerating all the possibilities, there are three, equally likely, branches for who will be pardoned. These each have a base chance of 1/3.
For the top branch (which is where A is pardoned), we know that the guard will not disclose this and so will flip a coin to determine what he says. Each of these subbranches has a 1/2 chance resulting in probability of 1/6 for either answer in this top section.
We heard the guard say “Prisoner B is to be executed” so these are the only situations we need to examine (We ignore all the situations other than those indicated by “B executed”); this gives us our denominator. The probability that A is to pardoned out of time times that we hear the proclamation about B is Pr = (1/6)/(1/6 + 1/3) = 1/3. In complement, the probability that C is to be pardoned after hearing the declaration is (1/3)/(1/6 + 1/3) = 2/3.
Paradoxically, by asking for the status of the fate of one of the other prisoners, A learned information that decreased his probability of being the person that is pardoned.
If you are familiar the Monty Hall problem, this is the same logic about why you should switch doors; the guard has revealed to you someone he knows will be executed. Before the guard disclosure there is a 2/3 chance that the pardon is with B or C. This probability does not change after his revelation, yet one of the targets has been removed (so it's still 2/3, but now this is in reference to only one prisoner).