Coupon Problem and Hat Problem - Randomized algorithms

1.Coupon Problem

A company selling jeans gives a coupon for each pair of jeans. There are 'n' different coupons. Collecting 'n' different coupons would give you free jeans.How many jeans do you expect to buy before getting a free one?

This problem is a classic example of the Coupon Collector's Problem. The expected number of purchases needed to collect all $n$ coupons is calculated as follows:

Step-by-Step Explanation:

1. Coupon Collector Problem Setup:

• There are $n$ different coupons.
• To collect all $n$ coupons, you buy jeans repeatedly and receive a random coupon with each purchase.
• The problem is to find the expected number of purchases required to collect all $n$ coupons.

2. Breaking Down the Problem:

• To collect the first coupon, you always get a new one. This takes 1 purchase (expected value = 1).
• To collect the second coupon, you already have 1 coupon. The probability of getting a new coupon is $\frac{n-1}{n}$, and the expected number of purchases is $\frac{1}{\text{probability}}=\frac{n}{n-1}$
  
• To collect the third coupon, you already have $2$ coupons. The probability of getting a new coupon is $\frac{n-2}{n}$, and the expected number of purchases is $\frac{1}{\text{probability}}=\frac{n}{n-2}$.
• This pattern continues until the $n$-th coupon.

Summing the Contributions:

• The total expected number of purchases is the sum of the expected number of purchases for each new coupon: $$E(n)=\frac{n}{n}+\frac{n}{n-1}+\frac{n}{n-2}+\cdots +\frac{n}{1}$$

Factoring Out $n$:

• Factor $n$ out of each term: $$E(n)=n(\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}+\cdots +\frac{1}{1})$$
  

Relation to Harmonic Number:

• The series inside the parentheses is the definition of the harmonic number 

  Hn:

$$H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$$

• Therefore, the expected number of purchases is:

  $$E(n)=n\cdot H_n$$

Algorithmic Solution:

1. Initialize Variables:

• Total Jeans Bought: Start with a counter set to zero to track how many pairs of jeans you have bought.
• Coupons Collected: Use a set to keep track of the different types of coupons you have received.
• Number of Coupons: The total number of different coupon types is n.

2. Buying Process:

• Loop Until All Coupons Are Collected: Continue buying jeans until you have one of each type of coupon in your set.
• Each time you buy a pair of jeans, increase the counter for the total jeans bought by one.
• When you buy a pair of jeans, you get a coupon. Add this coupon to your set of collected coupons.
• Check if you have collected all n different types of coupons by comparing the size of your set to n.

3. Repeat for Accuracy:

• To get a reliable estimate, repeat the entire buying process many times (e.g., 100,000 times).
• Keep a running total of the number of jeans bought across all these repetitions.

4. Calculate the Average:

• After completing all repetitions, calculate the average number of jeans bought by dividing the total number of jeans bought by the number of repetitions.

5. Output the Result:

• The average number of jeans bought from the repeated simulations gives you a good estimate of how many pairs of jeans you would typically need to buy before collecting all 'n' coupons and getting a free pair.

Python Program Implementation

import random

def expected_jeans(n, num_simulations=100000):

    total_jeans = 0

    for _ in range(num_simulations):

        coupons_collected = set()

        jeans_bought = 0

        while len(coupons_collected) < n:

            jeans_bought += 1

            # simulate getting a random coupon

            coupon = random.randint(1, n)

            # add the coupon to the set

            coupons_collected.add(coupon)

        total_jeans += jeans_bought

    expected_jeans = total_jeans / num_simulations

    return expected_jeans

# Example usage:

n = 10 # number of different coupons

expected_num_jeans = expected_jeans(n)

print(f"Expected number of jeans before getting a free one with {n} coupons: {expected_num_jeans}")

Output:

Expected number of jeans before getting a free one with 10 coupons: 29.28991

Running the code multiple times ensures that the results are consistent and demonstrate the reliability of the simulation approach.The theoretical expected number of purchases required to collect all n coupons is given by: Hn =n*(1/1+1/2+1/3........1/n) , where Hn is the n-th harmonic number.

10*(1/1+1/2+1/3+1/4+1/5+1/6+1/7+1/8+1/9+1/10)=29.289682539682538

2.Hat Problem

'n' people go to a party and drop off their hats to a hat-check person.When the party is over, a different hat-check person is on duty and returns then hats randomly back to each person. What is the expected number of people who get back their hats?

This problem is a classic example of a derangement problem, where the goal is to find how many people receive their own hat when hats are returned at random. Let's walk through the reasoning step by step to find the expected number of people who get back their own hats.

Key Points:

• We have $n$ people.
• Each person has dropped off their hat with a hat-check person.
• The hats are returned randomly.

We need to calculate the expected number of people who will get their own hat back.

Solution Outline:

Let $X_i$ be an indicator random variable for each person $i$, where:

$$X_i = \begin{cases} 1 & \text{if person } i \text{ gets their own hat back}, \\ 0 & \text{otherwise}. \end{cases}$$

Thus, the total number of people who get their own hats back is the sum of all these indicator variables:

$$X = X_1 + X_2 + \dots + X_n$$

Now, we want to find the expected value of $X$, i.e., $\mathbb{E}[X]$

Step 1: Calculate the Expected Value of $X_i$

Since $X_i$

​ is an indicator random variable, the expected value of 

$X_i$ is simply the probability that person $i$ gets their own hat back:

$$\mathbb{E}[X_i] = \mathbb{P}(\text{person } i \text{ gets their own hat})$$

When the hats are returned randomly, the probability that any person gets their own hat is 

$\frac{1}{n}$, because there are $n$ hats and each one is equally likely to be returned to any person.

Thus, for any $i$:

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

Step 2: Calculate the Expected Value of $X$

Since $X = X_1 + X_2 + \dots + X_n$, we can use the linearity of expectation:

$$\mathbb{E}[X] = \mathbb{E}[X_1] + \mathbb{E}[X_2] + \dots + \mathbb{E}[X_n]$$

Each $\mathbb{E}[X_i] = \frac{1}{n}$    so:

$$\mathbb{E}[X] = n \times \frac{1}{n} = 1$$

Conclusion:

The expected number of people who get their own hats back is 1, regardless of how many people are at the party.

This result might be surprising, but it reflects the fact that, on average, only one person is expected to get their own hat back in this random hat-return scenario.

Algorithmic Solution:

1. Initialization:

• Set up variables to count the total number of correct matches across all simulations.
• Define the number of simulations to ensure statistical reliability.
• Define the number of people n.

2. Simulate the Process:

• For each simulation:

• Create a list of hats representing each person.
• Shuffle the list to simulate random distribution.
• Count how many people receive their own hat.
• Add this count to the total number of correct matches.

3. Calculate the Expected Value:

• Divide the total number of correct matches by the number of simulations to get the average.

4. Output the Result:

• Print the expected number of people who get their own hats back.

Let us walk through an example

1. Setup and Initialization Step:

•  Suppose there are 5 people at the party.
• Initialize total_correct to 0, which will keep track of the total number of people who receive their own hat across multiple simulations and num_simulations to 100,000.

2. Simulate the Process:

•  For each simulation:

        – Create a list of hats [1, 2, 3, 4, 5].
        – Shuffle the list, e.g., [3, 1, 5, 2, 4].
        – Initialize correct to 0.

• – Check each person:

        ∗ Person 1 (hat 3) - not correct.
        ∗ Person 2 (hat 1) - not correct.
        ∗ Person 3 (hat 5) - not correct.
        ∗ Person 4 (hat 2) - not correct.
        ∗ Person 5 (hat 4) - not correct.

• – Add correct (which is 0 for this run) to total_correct.

3. Repeat Many Times:

• Repeat the simulation 100,000 times, each time shuffling the hats and counting how many people get their own hats back.
• Sum the number of correct matches across all simulations.

4. Calculate Average:

•  Divide total_correct by 100,000 to get the average number of people who receive their own hat.

By following these steps, you can determine the expected number of people who will get their own hats back after the hats are randomly redistributed. In the case of this specific problem, the expected number will be approximately 1, meaning on average, one person will get their own hat back. This is due to the nature of permutations and the expectation of fixed points in a random permutation. This solution uses a Monte Carlo simulation approach to estimate the expected number of people who get their own hats back, which is a practical way to solve problems involving randomness and expectations.

Python Implementation

import random

def simulate_hat_problem(n, num_simulations):

    total_correct = 0

    for _ in range(num_simulations):

        hats = list(range(n))

        random.shuffle(hats)

        correct = sum(1 for i in range(n) if hats[i] == i)

        total_correct += correct

    expected_value = total_correct / num_simulations

    return expected_value

# Example usage

n = 10 # Number of people at the party

num_simulations = 100000 # Number of simulations to run

expected_hats_back = simulate_hat_problem(n, num_simulations)

print(f"The expected number of people who get their own hatsback is approximately: {expected_hats_back}")

Output

The expected number of people who get their own hats back is approximately: 1.00174