Linearity of Expectations in the Hat Check Problem

In this example of linearity of expectations, we explore the Hatcheck Problem where a new employee checks the hats of n people at a restaurant without assigning claim check numbers. When customers return for their hats, they are randomly given hats. The expected number of hats returned correctly is 1, independent of the number of people who checked their hats.

• Discrete math
• Expectations
• Linearity
• Probability theory
• Hat check

portales_g Follow

Uploaded on Sep 27, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Discrete Math: Example2 of Linearity of Expectations

2. Example 2 Expected Value in the Hatcheck Problem A new employee checks the hats of n people at a restaurant, forgetting to put claim check numbers on the hats. When customers return for their hats, the checker gives them back hats chosen at random from the remaining hats. What is the expected number of hats that are returned correctly?

3. Solution Let X be the random variable that equals the number of people who receive the correct hat from the checker. Let Xi be the random variable with Xi = 1 if the ith person receives the correct hat and Xi = 0 otherwise. It follows that X = X1 + X2 + + Xn. Because it is equally likely that the checker returns any of the hats to this person, it follows that the probability that the ith person receives the correct hat is 1/n. Consequently, by Theorem 1, for all i we have

4. Solution Consequently, the average number of people who receive the correct hat is exactly 1. Note that this answer is independent of the number of people who have checked their hats!

5. References Discrete Mathematics and Its Applications, McGraw-Hill; 7th edition (June 26, 2006). Kenneth Rosen Discrete Mathematics An Open Introduction, 2nd edition. Oscar Levin A Short Course in Discrete Mathematics, 01 Dec 2004, Edward Bender & S. Gill Williamson