Each one of n persons, indexed by 1,2,…,n, has a clean hat and throws it into a box. The persons then pick hats from the box, at random. Every assignment of the hats to the persons is equally likely. In an equivalent model, each person picks a hat, one at a time, in the order of their index, with each one of the remaining hats being equally likely to be picked. Find the probability of the following events.
1. Every person gets his or her own hat back.
2. Each one of persons 1,…,m gets his or her own hat back, where 1≤m≤n.
3. Each one of persons 1,…,m gets back a hat belonging to one of the last m persons (persons n−m+1,…,n), where 1≤m≤n.
Now assume, in addition, that every hat thrown into the box has probability p of getting dirty (independently of what happens to the other hats or who has dropped or picked it up). Find the probability that:
4. Persons 1,…,m will pick up clean hats.
5. Exactly m persons will pick up clean hats.
1. 1/n!
2.(n-m)!/n!
3. 1/(n m)
4. (1-p)^m
5. (n m)*(1-p)^m * p^(n-m)
1. The probability that every person gets their own hat back is 1/n!. This is because there are n! total possible assignments of hats to persons, and only one of those assignments results in every person getting their own hat back.
2. The probability that each of persons 1 to m gets their own hat back is 1/(n-m)!. This is because there are (n-m)! possible assignments of hats to persons 1 to m, and only one of those assignments results in each of them getting their own hat back.
3. The probability that each of persons 1 to m gets back a hat belonging to one of the last m persons is m!/(n-m)!. This is because there are m! possible assignments of hats to persons 1 to m from the last m persons, and (n-m)! possible assignments of the remaining hats to the remaining persons. So the total number of favorable outcomes is m!(n-m)!, and the total number of possible outcomes is n!.
4. The probability that persons 1 to m pick up clean hats is p^m. This is because the probability that each person picks up a clean hat is p, and since the events are independent, the probability that all m persons pick up clean hats is p^m.
5. The probability that exactly m persons pick up clean hats is p^m(1-p)^(n-m). This is because the probability that each of the m persons picks up a clean hat is p, and the probability that each of the remaining n-m persons picks up a dirty hat is (1-p). Since the events are independent, the probability that exactly m persons pick up clean hats is the product of these probabilities.
1. To find the probability that every person gets his or her own hat back, we can use the principle of inclusion-exclusion.
Let event A_i denote the event that person i gets his or her own hat back, for each i from 1 to n. We want to find the probability of the intersection of all events A_i.
Using the principle of inclusion-exclusion, the probability of the intersection of all events A_i can be calculated as follows:
P(A_1 ∩ A_2 ∩ ... ∩ A_n) = 1 - P(A_1' ∪ A_2' ∪ ... ∪ A_n')
where A_i' denotes the complement of A_i.
Since there are n! total possible assignments of hats to persons, and (n-1)! assignments where person 1 does not get his or her own hat back, we have:
P(A_1') = (n-1)! / n!
= 1/n
Similarly, P(A_i') = 1/n for each i from 2 to n.
Applying the principle of inclusion-exclusion, we can calculate:
P(A_1 ∩ A_2 ∩ ... ∩ A_n) = 1 - (nC1 × 1/n - nC2 × 1/n × 1/n + nC3 × 1/n × 1/n × 1/n - ...)
where nCk denotes the number of ways to choose k items from n.
2. To find the probability that each one of persons 1 to m gets his or her own hat back, we can generalize the approach used in part 1. Let event A_i denote the event that person i gets his or her own hat back, for each i from 1 to m.
Using the principle of inclusion-exclusion, the probability can be calculated as:
P(A_1 ∩ A_2 ∩ ... ∩ A_m) = 1 - (mC1 × 1/n - mC2 × 1/n × 1/n + mC3 × 1/n × 1/n × 1/n - ...)
3. To find the probability that each one of persons 1 to m gets back a hat belonging to one of the last m persons (persons n-m+1 to n), we can modify the approach used in part 2.
Let event A_i denote the event that person i gets a hat belonging to one of the last m persons, for each i from 1 to m. We can calculate the probability as:
P(A_1 ∩ A_2 ∩ ... ∩ A_m) = 1 - ((n-m)C1 × 1/n - (n-m)C2 × 1/n × 1/n + (n-m)C3 × 1/n × 1/n × 1/n - ...)
4. To find the probability that persons 1 to m will pick up clean hats, we need to consider both the probability of every person getting his or her own hat back and the probability of hats being clean.
Let event B_i denote the event that person i gets his or her own hat back and that the hat is clean, for each i from 1 to m. The probability can be calculated as:
P(B_1 ∩ B_2 ∩ ... ∩ B_m) = P(A_1 ∩ A_2 ∩ ... ∩ A_m) × p × p × ... × p
where p is the probability that a hat is clean.
5. To find the probability that exactly m persons will pick up clean hats, we need to consider both the probability of each person picking up a clean hat and the probability of hats being dirty for the remaining n-m persons.
Let event C_i denote the event that person i picks up a clean hat, for each i from 1 to n. The probability can be calculated as:
P(C_1 ∩ C_2 ∩ ... ∩ C_m ∩ C_{m+1}' ∩ C_{m+2}' ∩ ... ∩ C_n') = P(A_1 ∩ A_2 ∩ ... ∩ A_m) × p × p × ... × p × (1-p) × (1-p) × ... × (1-p)
where p is the probability that a hat is clean and (1-p) is the probability that a hat is dirty.
To find the probabilities of these events, we need to analyze the possible outcomes and calculate the desired probabilities. Let's break down each event one by one.
1. Every person gets his or her own hat back:
In this case, there is only one favorable outcome - the hats are distributed in such a way that every person gets their own hat back. The total number of possible outcomes is n!, as each person can pick any of the n hats without any restriction. Therefore, the probability is 1/n!.
2. Each one of persons 1,...,m gets his or her own hat back, where 1 ≤ m ≤ n:
To compute this probability, we can think of it as a two-step process. First, we need to determine the probability that persons 1, 2, ..., m pick their own hat from the box. After they have picked their hats, there are (n-m)! hats left for the remaining n-m persons, who can pick them in any order. The probability of this happening is (1/n) * (1/(n-1)) * ... * (1/(n-m+1)). Therefore, the total probability is (1/n) * (1/(n-1)) * ... * (1/(n-m+1)) * (1/(n-m)!).
3. Each one of persons 1,...,m gets back a hat belonging to one of the last m persons (persons n−m+1,…,n), where 1 ≤ m ≤ n:
Similar to the previous event, we can break down this probability into two steps. First, persons n-m+1, n-m+2, ..., n need to pick hats belonging to the last m persons. There are m! ways to arrange these hats among themselves. Then, the remaining persons 1, 2, ..., n-m can still pick any of the remaining (n-m)! hats. The probability is (1/n) * (1/(n-1)) * ... * (1/(n-m+1)) * m! * (1/(n-m)!).
4. Persons 1,...,m will pick up clean hats:
In this scenario, we consider each person picking up a clean hat independently with probability p. The probability that person 1 picks a clean hat is p. After person 1 has picked a clean hat, the probability that person 2 picks a clean hat is (p-1/n-1), as there is one less clean hat in the remaining n-1 hats. From person 3 onwards, the probability decreases in a similar manner. So the total probability is p * (p-1/n-1) * (p-2/n-2) * ... * (p-m+1/n-m+1).
5. Exactly m persons will pick up clean hats:
To find this probability, we can use combinations. The number of ways to choose m persons to pick up clean hats is C(n, m) = n! / (m!(n-m)!). For each of these combinations, the probability that these m persons pick up clean hats is p^m. Then, the remaining (n-m) persons need to pick up dirty hats, which has a probability of (1-p)^(n-m). Therefore, the total probability is C(n, m) * p^m * (1-p)^(n-m).
These formulas should help you calculate the desired probabilities based on the given information.