# Extra information in a IID random variable?

So here's the original question:

$$n$$ players enter a room and a red or blue hat is placed on each person’s head. The color of each hat is determined by [an independent] coin toss. No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other hats [but not their own], the players must simultaneously guess the color of their own hats or pass. The puzzle is to find a group strategy that maximizes the probability that at least one person guesses correctly and no-one guesses incorrectly.

Now the solution for $$n=3$$, I could somehow solve (winning probability = 0.75):

Say Red/Blue if you see 2 Blue/Red (in that order), pass otherwise

Although I do not know how to generalize this result to $$n$$, my issue with any arbitrary $$n$$ is this.

Looking at it from the perspective of say any one player Bob. Bob has 2 jobs, decide whether he will pass or not based on what the others' hats are, and the guess (again based on the hats of the rest).

Both of these steps require basing his decision on the hats of the rest. So why does any decision based on the information from independent variables affect the chances of his being right when he does guess?

Irrespective of what the other hats are, from Bob's point of view, whenever he does choose to guess (based on information which is in no way related to the color of his own hat), it will always be a 50% chance that he is right. And this reasoning can be extended to every other player, so that from their own perspective, all the guesses are in fact only 50% valid. How does the winning probability be any higher than 0.5?

Isn't basing your prediction about the next outcome on a sequence of IID previous outcomes very similar to the Gambler's fallacy? I am significantly confused, since I did solve the $$n=3$$ case somehow.

PS: I hear that this is somewhat a famous puzzle. Any link to a solution for the general case?

• Could you tell us more about your solution for $n = 3$ (and provide a full proof that the winning probability is 0.75)? Currently, I am still struggling to understand how did that happen... – Yanior Weg Jan 21 '19 at 8:28
• @YaniorWeg Out of the 8 possibilities, 2 will have all the hats of the same color, in which case all the three participants will guess and get it wrong. Of the remaining 6, there will be 3 with 2Blue+1Red and vice versa. In all of these possibilities only the odd-one out will guess (and the remaining people will pass), which will be a correct guess, and hence, overall, the probability is 0.75. – stochastic13 Jan 21 '19 at 8:32
• For $n=5$, I think a good strategy could be when seeing $3$ of one colour and $1$ of the other to choose the second, and seeing $4$ of one colour and $0$ of the other to choose the first, and seeing $2$ of each to pass; this looks to me as having a probability of $\frac{22}{32}$ of success. – Henry Jan 21 '19 at 8:57
• – Henry Jan 21 '19 at 9:01

You are right that for each person separately, the chance to get it right or wrong in repeated executions of this procedure is the same. But this game is about $$n$$ players playing the game simultaneously, and the information those players have is highly correlated: Player $$A$$ and player $$B$$ see the absolute same hats from all the other $$n-2$$ players, the only difference is in hat $$A$$, that player $$B$$ sees, and hat $$B$$, that player $$A$$ sees.
As another argument, assume that players could not pass, each one had to state the color of their hat. It would seem that the probability that everyone guesses correctly would now plunge down to almost 0 for big $$n$$, right? Not correct, with a prediscussed strategy the probability that everyone guesses correctly can be made 0.5. Everybody simply assumes that the number of overall red hats among all players is even, then states their own hat color based on what they can see to make the assumption true.
First to note is that with this strategy, all players simultaneously get it right or get it wrong. That's due to the highly correlated information they get to make their decision. Second to note is that using binomial coefficients, the number of red hats being even is happening in exactly half of the $$2^n$$ cases, so the probabiliy of being right is 0.5.
It should be clear that allowing passes might increase the probability, as you've shown for $$n=3$$.
• Look at your$n=3$ example: Your strategy makes a player pass in 4 of 8 cases, guess correctly in 2 of 4 and incorrectly in 2 of 4, so every guess is only 50% correct. But you made is such that all 3 players guess incorrectly at the exact same 2 cases (RRR or BBB). That means their 50% incorrect guesses (6 all together) all coincide, leading to a loss in just 2 of 8 cases. At the same time, their correct guesses (also 6) are perfectly distributed over the remaining 6 cases. That's where correlation comes in: It allows to concentrate your losses and spread the winning guesses (+ other passes). – Ingix Jan 25 '19 at 15:30