Hat Problem/Hamming Codes - MathOverflow

Hat Problem/Hamming Codes

2010-02-11T08:54:00Z

I've been reading about how hamming codes are used to 'solve' the Hat Problem, and I understand how it 'assigns' one person to be the speaker, and how that speaker knows the answer. Everything I read says that it worked (2^n - 1)/(2^n) times, but what I don't understand is why it fails where it does. Apparently there's one case where every person guesses wrong, but I can't figure out which case that is, or (more importantly) why. Anyone care to explain?

Answer by Sridhar Ramesh for Hat Problem/Hamming Codes

2010-02-11T09:34:46Z

Well, I wouldn't say there's just one case where they lose, but it depends on how you count cases. Remember, the idea is that the number of people is of the form $2^n - 1$. Accordingly, if we take a case to be an ordered assignment of colors, then there are $2^{2^n - 1}$ different cases. The fraction of these in which the prisoners is win is $(2^n - 1)/2^n$, but the denominator here isn't the number of cases, on this method of counting them; there's more than one case in which they lose.

Anyway, the way it works is that in a Hamming code, some cases (specifically, $2^{2^n - 1 - n}$ of them) are picked as "well-formed" such that for every case A, there is a unique well-formed case B such that the number of color changes between A and B is at most 1.

So, suppose the prisoners use the strategy "Consider both possible cases compatible with the information available to you. If one of them is well-formed (they won't both be), then guess in accordance with the other one. Otherwise, in the case where neither of them is well-formed, you should refrain from guessing". What will the outcome be?

What happens is that, in those cases which are well-formed, every prisoner guesses wrong, since every prisoner will take the first branch of the above strategy. On the other hand, in those cases which aren't well-formed, there is a unique prisoner who goes down the first branch and guesses correctly, while every other prisoner goes down the second branch and refrains.

Accordingly, the number of cases in which the prisoners lose is the number of well-formed cases; that is, $2^{2^n - 1 - n}$. So the fraction of cases in which the prisoners lose is $2^{2^n - 1 - n}/2^{2^n - 1} = 1/2^n$. Like I said, though, this isn't just one case (if we identify cases with ordered assignments of colors).

(Incidentally, if you'd like to know how to actually construct a Hamming code, you can take the well-formed cases to be those with the property that, for every $i$, there are an even number of black hats at positions whose $i$th bit is 1 (using position numbering starting at 1). It should be straightforward to verify that this has all the properties mentioned above)

Answer by Ian Durham for Hat Problem/Hamming Codes

2010-02-11T20:10:42Z

So I looked at Loepp and Wootters and it does seem to answer your question. Here's roughly how the argument goes.

Strategy During the strategy session prior to the game the players agree on some binary [$n,n-r$] Hamming code C and a check matrix H for C. The players also number themselves 1 through n. The agree on the convention that 0 represents blue and 1 represents red and the convention that the vector $\bar{v}\in \mathbb{Z}^{n}_{2}$ represents the correct description of the way the hats are distributed. So, for example, suppose $n=3$ and the distribution is that the first two people have red and the third has blue. In this case $\bar{v}=(110)$. After the game begins the $i$th person will knows all of the entries of $\bar{v}$ $except$ for the $i$th entry. This person then forms two possible vectors for $\bar{v}$, e.g. $\bar{v}_{0}$ if that person has on a blue hat and $\bar{v}_{1}$ if that person has on a red hat. The $i$th person then does the following:

If $H\bar{v}^{T}_{0} \ne \bar{0}$ and $H\bar{v}^{T}_{1} \ne \bar{0}$ he/she passes.

If $H\bar{v}^{T}_{0} = \bar{0}$ and $H\bar{v}^{T}_{1} \ne \bar{0}$ he/she guesses red.

If $H\bar{v}^{T}_{0} \ne \bar{0}$ and $H\bar{v}^{T}_{1} = \bar{0}$ he/she guesses blue.

The case where $H\bar{v}^{T}_{0} = \bar{0}$ and $H\bar{v}^{T}_{1} = \bar{0}$ never occurs.

[Note: $\bar{v}^{T}$ is the transpose of $\bar{v}$ .]

Winning and losing If they use this strategy the team wins whenever $H\bar{v}^{T}\ne 0$ and they lose whenever $H\bar{v}^{T} = 0$ . The probability that the team will win turns out to be $\frac{n}{n+1}$ .