Hat guessing notes (for talk by Nate Eldredge) ================== Basic hat guessing game: each player gets hat according to coin flip. Can see other hats but not their own. Must guess own hat color; other players do not get to hear the guess. Logistics: how to play this game in front of the audience? First observation: each player has 50% chance of being right, no matter what they do. Thus expected number of players who guess right is n/2, no matter what. If they ignore hats of other players, then their guesses are independent, like independent coin flips. So what is the probability that they all guess right? (1/2^n). That at least half guess right? (1/2 if n odd, slightly larger if n even, involution argument.) Can we do better? Consider two players. Is there a strategy to guarantee that one of them guesses right? (Remember: "strategy" needs to cover every possible situation. Brute force: 16 possible strategies?) One guesses colors are the same, the other guesses they are different. Note that the other player will always guess wrong. This has to happen by considering the expectation. Note although each individual player still has 50% chance of being right, we have made these events (completely) negatively correlated. Like looking at the top and bottom of the same coin. Scale up to n players (say even number): pair them off. Then exactly n/2 will always guess right (and the rest guess wrong). Expectation shows we cannot improve this. Instead of maximizing the number who guess right, try maximizing the chance of everybody guessing right. Certainly can't be higher than 1/2 (again expectation). Can we achieve that? How for two players? How with more than two? Parity: agree that everyone will guess the number of red hats is even, say. There is a 50% chance of this being true (why? involution of flipping one color), and if it is then everyone guesses right. If not then everyone guesses wrong (this must be the case because of expectation). Here we have made the events completely positively correlated: they are all the same coin flip. Can also use this in a different way to guarantee half guess correct: half of players guess number of red hats is even, other half guess it's odd. Can generalize this to more colors. Number the colors as, say, 0,1,2, and agree everyone will guess that the sum of all hat colors is a multiple of 3. If it actually is, then everyone has guessed right; otherwise everyone is wrong. Remainder of total mod 3 is equally likely to be 0,1,2, so probability 1/3 of being correct. Similarly can use this to guarantee that 1/3 guess right. Also, this means if the players have a spy who can pass along information, the spy only needs to signal a single small number to the entire group (the total mod 3) and then everyone can guess correctly. This is the idea of a checksum and shows up in CS. Now what if the number of players is infinite? E.g. players numbered 1, 2, 3, ... Go back to 2 hat colors. We can still guarantee "half" to guess right by having players work in groups of 2. But can we do better? In fact I claim we can guarantee that only a finite number will guess wrong, which is way better than half! Make a list of all possible hat assignments, say writing each one as a sequence of 0 and 1. Sort them into boxes (equivalence classes): two sequences go in the same box if they eventually agree, i.e. have only finitely many differences. Then go through the boxes and choose one sequence from each box to mark with a star (chosen representative). Now the game starts. Say you are player 5. You see every hat but yours, so you know the assignment is either, say 010001011...or 010011011... They are both in the same box, so find that box. Look at its chosen representative *, see what it has in position 5, and guess that. Now everyone was able to correctly identify which box the assignment was in, and so everybody took their guesses from the same *. So * shows us the sequence of all guesses. But it's in the same box as the true assignment, whatever that was, so it has only finitely many differences from the true assignment! Incidentally, we can adapt this to get a strategy where either everyone guesses right or everyone guesses wrong (with "equal probability"). Look at *. It differs from the true assignment in a finite number of places. That number N is even or odd. Let's agree in advance that we will always guess it's even. So count how many people, other than yourself, whose hats disagree with what * says. If it's an even number, make your guess according to * as before; if odd, switch. If N really was even, then your guess according to * is right (you were not one of the people whose hats disagreed with *), and the same logic holds for every player, so everyone has guessed right. If N was odd, then you and everyone else guessed wrong. (Alternate approach via "parity functions". Take all sequences and sort them into two bins, "even" and "odd". Every sequence with a finite even number of red hats goes in "even" bin, finite odd goes in "odd" bin. For each sequence left over, choose a bin arbitrarily to put it in, but then every other sequence that differs from it in finitely many places must go either in the same bin or the opposite, according to whether the number of places where it differs is even or odd. For the game, agree that we will guess the true assignment is in the "even" bin. When you see everyone else's hat, you narrow down to two sequences. One is in the even bin and the other is in the odd bin. Make the guess that corresponds to the even bin.) Why does this seem to contradict probability? This strategy is too crazy, too many arbitrary choices. Think about how impractical it would actually be to formulate it explicitly so that everyone could follow it. When you do probability theory on experiments involving uncountably many outcomes (e.g. infinitely many coin flips), and try to do things rigorously, you find you can only do it if you make assumptions of "measurability". Some "events" and some "random variables" are too weird to be able to assign them probabilities in a consistent way, so we exclude them from consideration. All "reasonable" strategies are fine, and they include pretty much everything you could describe unambiguously. "Guess red if the hats alternate in color." "Guess red if infinitely many prime-numbered hat is red". Etc. All those strategies are measurable. And we can prove that all those "reasonable" strategies don't behave unreasonably well. For instance, with any such strategy, the probability of having all but finitely many guess right is 0, as you would expect. Indeed there is probability zero of having more than "half" guess right, or all wrong (an "all right or all wrong" strategy is not possible). Blue eyed islanders credit Tao =================== Recruit 4 players. Give them all blue hats. Does anyone know, for certain, the color of their own hat? How about now? Answer truthfully. etc. Now I'll give you a piece of information that may not seem useful at first. "At least one of you is wearing a blue hat." Does anyone know their own hat? How about now? x4. I claim you actually do have enough information now to deduce your own hat. Try it with 2 players. What if A's hat were red? Then B would have deduced on round 1 that her own hat must be blue, and would have said so. Since she didn't, A's hat must be blue, and she can announce this on round 2. Similarly, B will also know at round 2 that her hat is also blue. This is not affected by adding any number of red hats. Theorem. If there are n players, all with blue hats, and are told "at least one blue hat", then by round n they can all deduce that their hats are blue. Note first that all players with blue hats have exactly the same information at all times, so whenever one of them can deduce their hat color, they all can. Proof by induction. n=1 is trivial. n=2 we just did. Suppose it's true for n-1. Pick one player, A, and say it's round n, and she hasn't been able to deduce her hat color so far. Then neither have any of the other blue hats. If her hat were red, there would have been n-1 blue hats, and by IHOP those players would have announced their hats on round n-1. They did not, so her hat must be blue. (We can also show they cannot deduce any earlier than that. Suppose n players could deduce in round m, m= 2 blue hats can deduce in 1 round which is absurd.) Note that on round n+1, all the remaining players deduce that their hats were red (if not, they'd have deduced on round n that they were blue). Draw thought bubble pictures for n=2, n=3. Although everyone knows there is a blue hat, n=2 they don't know that the others also know. n=3, they know the others know, but don't know the others know the others know. Announcement makes it common knowledge: everyone knows that everyone knows that... etc. Particularly weird to think about for large n, e.g. 100. Ask 99 times and nothing happens, on 100th time they all say "yes".