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.