CLRS Solutions | Exercise 5.2-4 | Probabilistic Analysis and Randomized Algorithms

Use indicator random variables to solve the following problem, which is known as the hat-check problem. Each of \(n\) customers gives a hat to a hat-check person at a restaurant. The hat-check person gives the hats back to the customers in a random order. What is the expected number of customers who get back their own hat?

The hat-check problem is a classic probability puzzle. Imagine checking your hat at a restaurant, but the hat-check person completely mixes them up and returns them randomly. How many people, on average, will get lucky and receive their own hat back?

Using Indicator Random Variables

For each customer \(i\) where \(1 \leq i \leq n\), we define an indicator random variable:

\[X_i = \begin{cases} 1 & \text{if customer } i \text{ gets their own hat back} \\ 0 & \text{otherwise} \end{cases}\]

The total number of customers who get their own hat back is:

\[X = \sum_{i=1}^{n} X_i\]

By linearity of expectation:

\[E[X] = E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i]\]

Computing the Probability

By Lemma 5.1 from the text, \(E[X_i] = \Pr\{\text{customer } i \text{ gets their own hat}\}\).

Since the hats are returned in a uniformly random order, customer \(i\) is equally likely to receive any of the \(n\) hats. Therefore:

\[\Pr\{\text{customer } i \text{ gets their own hat}\} = \frac{1}{n}\]

This gives us:

\[E[X_i] = \frac{1}{n}\]

The Surprising Result

\[\begin{align*} E[X] &= \sum_{i=1}^{n} E[X_i] \\ &= \sum_{i=1}^{n} \frac{1}{n} \\ &= n \cdot \frac{1}{n} \\ &= 1 \end{align*}\]

The expected number of customers who get their own hat back is exactly 1, regardless of how many customers there are!

Interactive Simulation

See the remarkable constant in action! The simulation below shows that regardless of \(n\), the expected number of matches stays at 1:

import random def hat_check_simulation(n): """ Simulate the hat-check problem for n customers. Returns the number of customers who get their own hat back. """ # Create hats numbered 1 to n hats = list(range(1, n + 1)) # Shuffle the hats randomly random.shuffle(hats) # Count how many customers get their own hat # Customer i gets their own hat if hats[i-1] == i matches = sum(1 for i in range(1, n + 1) if hats[i - 1] == i) return matches def simulate_expected_matches(n, num_trials=1000): """ Simulate the hat-check problem many times and compute average matches. Args: n: Number of customers/hats num_trials: Number of simulations to run Returns: The empirical average number of matches """ total_matches = sum(hat_check_simulation(n) for _ in range(num_trials)) return total_matches / num_trials # Test with different numbers of customers print("Hat-Check Problem: Expected number of matches") print("=" * 60) for num_customers in [5, 10, 100]: empirical_average = simulate_expected_matches(num_customers) theoretical_expected = 1.0 # Always 1! print(f"n = {num_customers:3d} customers") print(f" Theoretical: {theoretical_expected:.4f}") print(f" Empirical: {empirical_average:.4f}") print(f" Difference: {abs(empirical_average - theoretical_expected):.4f}") print() # Detailed example print("=" * 60) print("Five individual simulations with n = 10:") for trial in range(5): matches = hat_check_simulation(10) print(f" Trial {trial + 1}: {matches} customer(s) got their own hat") print(f"\nTheoretical expected value: 1 (regardless of n!)")