Title: The Hat Problem and Autoreductions of Random Sequences
Speaker: Wolfgang Merkle, University of Heidelberg
Date: Wednesday, September 26, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The hat problem asks for a strategy for the following game. Each of n Players is assigned a blue or red hat according to independent tosses of a fair coin. Each player knows the colors of all other hats but not of his own hat. The player collaborate as a team, the team wins if at least one player guesses his or her own color correctly and no player guesses incorrectly, while any player may abstain from guessing. The players can agree on an arbitrarily complex strategy before the game starts but cannot communicate during the game.
The talk will discuss an optimal strategy for the hat problem where the probability of success goes to 1 when the number of players increases. The strategy will then be applied to autoreductions of infinite random sequences, which are considered in the field of algorithmic randomness. The main result is that for appropriate types of random sequences and models of autoreductions, the bits of a random sequence depend on each other in such a way that infinitely many bits may be computed from the remaining bits, while it is not possible to compute this way a constant nonzero fraction of all bits.