Hat Problem/Hamming Codes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T12:12:25Z http://mathoverflow.net/feeds/question/14980 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/14980/hat-problem-hamming-codes Hat Problem/Hamming Codes Jon Brant 2010-02-11T08:54:00Z 2010-02-11T20:32:14Z <p>I've been reading about how hamming codes are used to 'solve' the <a href="http://en.wikipedia.org/wiki/Hat%5Fpuzzle" rel="nofollow">Hat Problem</a>, 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?</p> http://mathoverflow.net/questions/14980/hat-problem-hamming-codes/14984#14984 Answer by Sridhar Ramesh for Hat Problem/Hamming Codes Sridhar Ramesh 2010-02-11T09:34:46Z 2010-02-11T20:32:14Z <p>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.</p> <p>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.</p> <p>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?</p> <p>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.</p> <p>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).</p> <p>(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)</p> http://mathoverflow.net/questions/14980/hat-problem-hamming-codes/15026#15026 Answer by Ian Durham for Hat Problem/Hamming Codes Ian Durham 2010-02-11T20:10:42Z 2010-02-11T20:10:42Z <p>So I looked at Loepp and Wootters and it does seem to answer your question. Here's roughly how the argument goes.</p> <p><strong>Strategy</strong> During the strategy session prior to the game the players agree on some binary [$n,n-r$] Hamming code <em>C</em> and a check matrix <em>H</em> for <em>C</em>. The players also number themselves 1 through <em>n</em>. The agree on the convention that 0 represents blue and 1 represents red and the convention that the vector <code>$\bar{v}\in \mathbb{Z}^{n}_{2}$</code> 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. <code>$\bar{v}_{0}$</code> if that person has on a blue hat and <code>$\bar{v}_{1}$</code> if that person has on a red hat. The $i$th person then does the following:</p> <p>If <code>$H\bar{v}^{T}_{0} \ne \bar{0}$</code> and <code>$H\bar{v}^{T}_{1} \ne \bar{0}$</code> he/she passes.</p> <p>If <code>$H\bar{v}^{T}_{0} = \bar{0}$</code> and <code>$H\bar{v}^{T}_{1} \ne \bar{0}$</code> he/she guesses red.</p> <p>If <code>$H\bar{v}^{T}_{0} \ne \bar{0}$</code> and <code>$H\bar{v}^{T}_{1} = \bar{0}$</code> he/she guesses blue.</p> <p>The case where <code>$H\bar{v}^{T}_{0} = \bar{0}$</code> and <code>$H\bar{v}^{T}_{1} = \bar{0}$</code> never occurs.</p> <p>[Note: <code>$\bar{v}^{T}$</code> is the transpose of <code>$\bar{v}$</code>.]</p> <p><strong>Winning and losing</strong> If they use this strategy the team wins whenever <code>$H\bar{v}^{T}\ne 0$</code> and they lose whenever <code>$H\bar{v}^{T} = 0$</code>. The probability that the team will win turns out to be <code>$\frac{n}{n+1}$</code>.</p>