Last term, I took a lovely class in probability theory with Professor Omer Tamuz. On the first problem set, he posed an interesting bonus problem about a certain game played by a countable sequence of players wearing colored hats. The game goes like this:

Countably many cooperating players stand in a line indexed by . A neutral game master walks down the row of players, placing black and white hats on the player’s heads independently and uniformly at random. (In other words, the color of each player’s hat is decided by a fresh fair coin flip.) Afterwards, the game master goes through again, asking each player in turn to announce a guess for their own hat color. Each player hears the guesses of the players that came before them and sees all of the hats on the heads of people ahead of them. The players win if everyone except for the first person guesses correctly. (The first person, of course, is doomed to only guess their hat correctly 50% of the time, regardless of their strategy. However, the rest of the players have a chance to come out ahead by using the information provided by those behind them.)

The players conspire beforehand to come up with a strategy. Is it possible for them to cook up a strategy for which they always win? A bit more conservatively, how about one that wins with probability ?

Continue reading “A Countable Hat Game and the Kolmogorov 0-1 Law”