Prisoner’s Game

Here is a neat Prisoner’s game with some really neat results. Consider the following:

A warden gives 3 prisoner’s black and white hats such that each prisoner can only see the color of other prisoner’s hats, but not their own. All at once, each prisoner must guess what color hat is on their head. They may all say black, white, or refuse to guess.

They all go free if the following happens:

  1. No one incorrectly guessed a color
  2. Not everyone refused to guess (yeah, that’s called cheating)

If the prisoners have time before hand to discuss a strategy, what is the optimal strategy? What is the highest probability of winning we can obtain?

Think about it before scrolling down!

.

..

A naive approach

If everyone but one person refuses to guess a color, the probability of winning is 1/2 since it is only dependent on one person guessing.

Winrate: 1/2

A better approach

For the sake of simplicity map black to 1 and white 0. Now consider the prisoner’s from left to right, their hat colors will correspond to a 3 digit value (i.e. 010, 001, 111). Let  S = {000,111} be the set of bad values the prisoners agree on beforehand. Note that every 3 digit value can be obtained by changing at most 1 value of only one element in S.

Our approach is the following:

  1. Look at the hats around you, if the hat you have would create a 3 digit value in S, guess the color.
  2. Otherwise, refuse to guess

Example 1: Prisoners are 101. First prisoner refuses to guess, second guesses 0, third refuses to guess and they are all set free.

Example 2: Prisoners are 111. First prisoner guesses 0, second guesses 0, third guesses 0 and they are all sad.

Why does the approach work?

We are essentially establishing 000 and 111 as values we are avoiding. By avoiding 000, we ensure that we win when 100, 010, 001 show up. By avoiding 111, we ensure that we win when 101, 110, 011 show up. As a result, we give up on two possibilities to be right in 6 other possibilities.

Put another way, instead of having a 1/2 chance of winning in all cases, we say we put a 0% of winning in two cases, and 100% of winning in 6 cases.

Note the following observation: when each person guesses a color, the probability that everyone gets set free or dies is 1/2. However, the strength stems from that the fact that when people guess incorrectly, they all guess incorrectly on the same scenario, which is why we see everyone being horribly wrong in example 2. Now, when people guess correct, everyone else refuses to guess thereby spreading the correctness over multiple scenarios.

Win rate: 3/4

————————————————————————–

Ok so why is this so cool?

What if we repeat the same problem with say 255 prisoners? Well it turns out you can create another set S with 2^247 elements, such that each of the 2^255 values can be attained by changing at most 1 value from exactly one element in S. By the same argument, if the hats correspond to any of the 2^247 values in S, we lose. Otherwise, we win. Therefore, we lose with probability equal to 2^247/2^255 = 1/256 and win with probability equal to 255/256. In general if we have 2^n – 1 prisoners, our probability of winning is 1- 1/(2^n – 1). Our probability of winning grows with more prisoners. Specifically as n grows to infinity, we are guaranteed to win. Amazing!

However, this stems from a well chosen set of S that has the probability that every 2^n element can be attained by changing at most 1 value from exactly one element in S. The existence of such a set is made possible by Hamming codes. These are sets of values have the exact properties we are looking for when creating S. These codes arise in error-correcting codes, used to correct messages that may undergo a fixed number of incorrect bits. I encourage the interested reader to check it out!

— Hao Shen

Advertisements

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