Another Take on the 7-Hats problem

Consider the problem described here.

Let 0 denote Red and 1 denote Blue. Fix an order among the n players. So the different ways to put hats is all possible n-bit strings, each occurring with equal
probability. Any assignment is an n-bit string.

The players could decide the following strategy. They split all n-bit strings into two disjoint sets S and S' (S'=complement of S). They try to split it in a certain way so that they are able to correctly guess (which means at least one guesses correctly and others pass) when the assignment is in S'. Then their probability of success will be |S'|/|S|+|S'|.

Property of S,S': Let the actual assignment be s. They want, if s is in S, someone to be able to guess correctly and no one wrongly. One way to ensure this is if for all s in S', there is some i in 1...n (at least one bit position), such that flipping the i-th bit of s gives a string in S. The players will decide in advance a suitable S and S' satisfying this property.

Then then need to decide a strategy based on S and S'. Here is a simple one. Each person i can see (n-1) bits. He considers the two possible n-bit assignments, s₀ using 0 in the i-th bit and s₁ with 1 in the i-th bit. These are the cases,

• s₀ is in S and s₁ is in S': Guess 1 as his bit. If s is in S', guess is correct.
• s₀ is in S' and s₁ is in S: Guess 0 as his bit. If s is in S', guess is correct.
• Both s₀,s₁ are in S: So, the actual string s must also be in S. He can just say pass.
• Both s₀,s₁ are in S': So, the actual string s is in S'. He can say pass. By the property above, there is some j such that s is obtained from S by flipping bit j. Then person-j will guess correctly.
  

By the strategy above, they win if the string s is in S'. The tricky part is to find the correct S and S' satisfying the property above. They can be found using various algorithms e.g. using brute force or greedy approach. For example when n=3, one possiblity is S={000,001,010,011} and S'={100,101,110,111} (so the success probability is 1/2).

It turns out the above property is satisfied by error detecting codes detecting 1-bit error. All the non-codewords in a 1-bit error detecting code are obtained by flipping 1-bit of some codeword; so S is the set of codewords. Any such error detecting code with k codewords will give a strategy with error probability k/2^n. The probability can be maximized by finding a error detecting code with the smallest set of codewords. The (7,4)-Hamming code is one such example with 16 codewords; so using its codewords as S gives a strategy with error probability 16/128=1/8.

Note that, the game does not allow the players to collaborate once the game starts, which means they are not allowed to pass hints to others by choosing which order to make their guess or listening to others before making guess. If colloboration is allowed, the error can be made very small 2/2^n.

7-hats problem

7-hat problem: 7 persons are assigned red or blue hats, uniformly at random, with their eyes closed. When they open their eyes, they look around and try to predict the colour of their own hat by saying blue, red or staying silent. They lose if any of them is wrong or if all stay silent. What is the maximum probability of winning ?

Consider the various possibilities,

A) (prob: 1/128) 0 red, 7 blue: All players see 6 blue. To win, they should say blue.
B) (prob: 7/128) 1 red, 6 blue: 1 player sees 6 blue (should say red), other 6 see 5 blue (should say blue).
C) (prob: 21/128) 2 red, 5 blue: 2 players see 5 blue (should say red), other 5 see 4 blue (should say blue).
D) (prob: 35/128) 3 red, 4 blue: 3 players see 4 blue (should say red), other 4 see 3 blue/3 red (should say blue).
and complement cases (interchange red and blue in the four cases).

If the players decide based on the number of blue/red hats, they can decide a strategy to win alternate cases. So the best they can do is to satisfy (B), (D) and their complementary cases i.e. anyone seeing 6 or 4 blue will say red and vice versa, others stay silent. They will win with probability 84/128 = 21/32 = 0.656.

They can take into account ordering information beside just looking at the numbers. This will give them higher chance of winning. Lets look at the 3-hat problem once again.

Consider how the players might decide a strategy. They can decide an order among themselves so that the values, 0 (for red) or 1 (for blue), form a bit-string of length 3. When they open their eyes, they will consider both the possibilities for themselves and decide accordingly. They could decide beforehand a set S, and its complement S' and a strategy such that for every player if bit b (b in {0,1}) puts the string in S, he says b for himself; otherwise stays silent. What are the properties needed for such a set S ?

1) For all s' in S', changing one bit of S' should put it in S. Otherwise, the player will not be able to decide. (The same could also hold for S, but that is not a strict requirement since the players are allowed to stay silent. So, if both 0 and 1 puts the value in S, the player stays silent).

2) For all s in S, there must be some s' in S' such that, s is obtained by flipping some bit of S'. Otherwise, all players will remain silent and they will lose. If such s' exists, then one of the players will be correct.

If they find such an S (and S'), they will win if the value is in S.
Consider any s in S. By (2), there exists some s' such that s=flip(s'). Say the flip occurs in position i. Then, player i will say the correct value. Others will either stay silent (both 0 and 1 put it in S) or say the correct thing (only one of the values put it in S) (it cannot be that neither puts it in S by (1)).
Consider any s in S'. Everybody will be either wrong or stay silent (in which case they also lose).
So, they win with probability size(S)/size(S)+size(S').

(1) => all strings in S' are at least 2 bit-flips apart. So, the trick is to come up with S and S' such that S' has strings separated by at least 2 bit-flips and all strings in S are obtained by flipping one bit of some string in S'. You can greedily construct some sets. Put any string s in S'. Flip one bit of s at a time and put them in S. When done, look at the strings left and pick one not used. Put that in S'. Continue.

E.g. for 3-hat, S' could be {000, 011, 101, 110} (prob of winning 4/8 = 0.5) or S' could be {000, 111} (prob of winning 6/8=0.75).

The above strategy has nothing to do 3. This could as well be used for 7-hat.

For 7-hat, the strategy at the top would work. S' is the string in cases (A) and (C) (and complement sets). Verify easily that all 7-bit strings are either in S' or S, all strings in S are one-bit away from some string in S' and all strings in S' are 2-bit flips apart.

Finding the best S and S' manually is a bit difficult. If you are familiar with coding theory, you can observe that any code that detects one bit error will work (S' would be the set of codewords; since they differ by 2, one bit error can be detected). E.g. the Hamming code for 7-bit codewords, gives S' of size 16 (out of total 128). So, using S' as the set of codewords of (7,4) hamming code, the players can win with probability 7/8. Note that, hamming code not only detects but corrects one-bit of error. Any other 1-bit error detecting code will also work but will give a lower probability of winning.