WUSTL ESE 523 - ProblemSet1-2013 (3 pages)

Previewing page 1 of 3 page document View the full content.
View Full Document

ProblemSet1-2013



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

ProblemSet1-2013

117 views


Pages:
3
School:
Washington University in St. Louis
Course:
Ese 523 - Information Theory
Unformatted text preview:

ESE 523 Introduction to Information Theory Professor Joseph A O Sullivan Fall 2013 Problem Set 1 Due Tuesday September 16 2013 Suggested Problems 1 Look over the problems at the end of chapter 2 2 Problem 2 9 Required Problems 1 Problem 2 1 2 Problem 2 6 3 Problem 2 10 4 Problem 2 12 5 Problem 2 16 6 Solve the problem from the New York Times article see below for three players and for seven players April 10 2001 Why Mathematicians Now Care About Their Hat Color By SARA ROBINSON ERKELEY Calif April 9 It takes a particularly clever puzzle to stump a mind accustomed to performing mental gymnastics So it s no ordinary puzzle that s spreading through networks of mathematicians like a juicy bit of gossip Known as the hat problem in its most popular incarnation this seemingly simple puzzle is consuming brain cycles at universities and research labs across the country and has become a vibrant topic of discussion on the Internet The reason this problem is so captivating mathematicians say is that it is not just a recreational puzzle to be solved and put away Rather it has deep and unexpected connections to coding theory an active area of mathematical research with broad applications in telecommunications and computer science In their attempts to devise a complete solution to the problem researchers are proving new theorems in coding theory that may have applications well beyond mathematical puzzles This puzzle is unique since it connects to unsolved mathematical questions said Dr Joe Buhler deputy director of the Mathematical Sciences Research Institute here and a hat problem enthusiast The hat problem goes like this Three 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 a coin toss with the outcome of one coin toss having no effect on the others Each person can see the other players hats but not his own 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 the players must simultaneously guess the color of their own hats or pass The group shares a hypothetical 3 million prize if at least one player guesses correctly and no players guess incorrectly The same game can be played with any number of players The general problem is to find a strategy for the group that maximizes its chances of winning the prize One obvious strategy for the players for instance would be for one player to always guess red while the other players pass This would give the group a 50 percent chance of winning the prize Can the group do better Most mathematicians initially think not Since each person s hat color is independent of the other players colors and no communication is allowed it seems impossible for the players to learn anything just by looking at one another All the players can do it seems is guess I tell someone the problem and they think they don t have the conditions right said Dr Peter Winkler director of fundamental mathematics research at Bell Labs of Lucent Technologies in Murray Hill N J But if you try to prove it s impossible it doesn t quite work Mathematicians credit the problem to Dr Todd Ebert a computer science instructor at the University of California at Irvine who introduced it in his Ph D thesis at the University of California at Santa Barbara in 1998 Dr Ebert said he discovered the problem s appeal only recently when he offered extra credit to his students for solving a seven player version he called the seven prisoners puzzle Next thing he knew the problem was posted on Internet news groups and in chat rooms I started getting e mail from all over the country Dr Ebert said Meanwhile Dr Winkler a well known collector and distributor of clever puzzles heard the problem from a colleague and spread it widely It has cropped up at Microsoft Research in Redmond Wash at Hewlett Packard Laboratories in Palo Alto Calif and at mathematics statistics and computer science departments at universities across the country The problem has even spread to the Caribbean At a workshop at a research institute in Barbados one hardy group of theoretical computer scientists stayed up late one rum soaked night playing a drinking game based on the puzzle It spread to Berkeley after Dr Winkler bumped into Dr Elwyn Berlekamp a professor in the Berkeley math department at a conference in New Orleans in January I told him about the problem and next thing I knew he was leaving messages on my hotel phone saying Great problem haven t gotten it yet then finally I got it Dr Winkler said I thought with his knowledge of coding theory he d find that approach and he didn t disappoint me Dr Berlekamp a coding theory expert said he figured out the solution to the simplest case in about half an hour but he saw the coding theory connection only while he was falling asleep that night If you look at old things that you know from a different angle sometimes you can t see them he said The first thing Dr Berlekamp saw was that in the three player case it is possible for the group to win three fourths of the time Three fourths of the time two of the players will have hats of the same color and the third player s hat will be the opposite color The group can win every time this happens by using the following strategy Once the game starts each player looks at the other two players hats If the two hats are different colors he passes If they are the same color the player guesses his own hat is the opposite color This way every time the hat colors are distributed two and one one player will guess correctly and the others will pass and the group will win the game When all the hats are the same color however all three players will guess incorrectly and the group will lose If you look at the total number of guesses made it s still the case that half are right and half wrong Dr Winkler said You only make progress if when players are guessing wrong a great many are guessing wrong The strategy gets far more complicated for larger numbers of players Still it all comes down to making sure that most of the time no one is wrong and occasionally everyone is wrong at once As it turns out this requirement can be perfectly met only when the number of players is one less than a power of two three seven 15 and so on For example in the game with 15 players there is a strategy for which the group is victorious 15 out of every 16 times they play This strategy can be described using elegant


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view ProblemSet1-2013 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ProblemSet1-2013 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?