1
$\begingroup$

This is a problem from an exam that I took a while back, so I might not be remembering it completely correct. I checked other questions on the forum but I didn't find anything that answers my question.

Problem:

Upon entering a restaurant, each customer leaves their coat on a coat hanger uniformly at random. A total of 12 customers arrive at the restaurant and leave their coat there. After finishing their meal, each customer (one at a time, no order in particular), will take their coat at random and leave.

  1. What is the probability that everyone gets their own coat?
  2. What is the expected number of people who get their own coat?

I think it's the fact that each customer is leaving one by one that is confusing me the most.

My attempt:

Define a variable $X_i$, for $i=1,...,12$ such that

$$ X_i :=\begin{cases} 1 &\text{if person $i$ gets coat $i$},\\ 0 &\text{otherwise}. \end{cases} $$

Then, initially, the probability that any person gets their own coat is

$$P(X_i = 1) = \frac{1}{12}.$$ However, after the first person picks up a coat, we have $11$ people and coats left, and we don't know whether the previous customer took their own coat or not. So I thought about finding the conditional probability $$P(X_i = 1 \vert X_\text{prev}) = \frac{P(X_i = 1, X_\text{prev} = 1)}{P(X_\text{prev})}$$but I'm not sure how to evaluate it.

On the other hand, if we consider all 12 people taking a coat from the coat hanger at the same time, we could find the probability that each person took their own coat (thus, $X_i \sim \text{Bernoulli}\left(\frac{1}{12}\right)$).

We could compute the probability that the $k$ coats are given to the correct customers by considering the derangement of $k$ coats $$P(\mathcal{C}_k) = 1 - \frac{!k}{12!},$$where we define $\mathcal{C}_k := \{X_i : X_i = 1, i = 1,...,k\}$ to be the $k$-set of $X_i$'s such that a coat is given to the correct person. Then, all 12 people get their own coat with probability $$P(\mathcal{C}_{12}) = 1 - \frac{!12}{12!} = 1 - \frac{1}{12!}\cdot\left[\frac{12!}{e}\right] \approx 1 - \frac{1}{e} \approx 1 - 0.3678794413 = 0.6321205587.$$

For the expected number of customers that get their own coat, we need to compute $$\mathbb{E}[X_1 + X_2 + ... + X_{12}] = \sum_{i = 1}^{12} \mathbb{E}[X_i] = \sum_{i =1}^{12} P(X_i = 1).$$But I'm not sure how to proceed here because it changes whether we consider that the customers pick the coats up one at a time or simultaneously.

If they all pick it up simultaneously, then we would just have that $$\mathbb{E}[X_1 + X_2 + ... + X_{12}] = 1$$since it is equally likely that they pick up their own coat. (Although, I can't make sense of the result, as to why the expected number of people who pick up the correct coat is just 1, for any $n$).

However, if they take one at a time, the probability $P(X_i = 1)$ would change as the coats are taken and I don't know how to approach this computation.

I guess what I need help with is how to compute (1) and (2) considering that only one customer leaves at a time (randomly), instead of all of them leaving together. But I'm also wondering whether there is even enough information to find that out.

$\endgroup$
4
  • 1
    $\begingroup$ Each person has an equal chance of getting any particular coat, that's all you need. Whether they all choose at once or one at a time isn't important here. $\endgroup$
    – lulu
    May 30 at 23:25
  • $\begingroup$ @lulu But if they take one coat at a time, wouldn’t that change how likely it is that someone else takes a coat depending on whether the previous customer took theirs or not, and due to the fact that there are less coats? So wouldn’t (at least) the expected value depend on that? $\endgroup$
    – Lea
    May 31 at 5:43
  • $\begingroup$ You are dealt 5 cards face down in a poker game. There is a certain probability that you get a royal flush as your hand. Suppose your cards are instead dealt face down but are then turned face up one by one instead of all at once. Does that change the initial probability of a royal flush? What about if they were dealt face up to begin with? $\endgroup$
    – Jaap Scherphuis
    May 31 at 8:12
  • $\begingroup$ The only thing that matters is that each person is equally likely to get each coat, and that should be clear (which coat do you think is more likely than some other coat?). If you want to write out a proof, do it by induction. For two people, two coats, this is clear (right?). Now say we know it for $n-1$ people/coats. What's the probability that person $2$ gets coat $1$, say? Well, if person $1$ gets coat $1$, then it is $0$ otherwise it is $\frac 1{n-1}$ by induction. Thus it is $\frac 1n\times 0 +\frac {n-1}n\times \frac 1{n-1}=\frac 1n$ as desired. $\endgroup$
    – lulu
    May 31 at 10:30

2 Answers 2

Reset to default
0
$\begingroup$

Let's start with numbering each coat on the hanger with numbers 1-12. Also assign the numbers 1-12 to each customer. So for each possible final coat distribution across customers we can create a 12-number sequence, where n-th number describes who have taken the n-th coat.

For example, in

1 2 3 4 5 6 7 8 9 10 11 12

everyone has taken his coat, and in

12 1 2 3 4 5 6 7 8 9 10 11

only 10 people did it.

Also notice that only even number of customers can take the wrong coat (if one take wrong coat, then other one has to take first one's).

With such a sequence we can compute the probability of N customers taking the correct coat. For example,

P(12) = $\frac{1}{12!}$, for there is the only one case where every one take the correct coat and 12! possible coat arrangements

P(8) = $\frac{{8 \choose 12} * 3!} {12!}$, for there are ${8 \choose 12}$ ways to choose the customers who gets their coat and 3! ways to arrange coats "the wrong way" across the rest of the customers.

And so on.

With these probabilities we can answer both the questions:

  1. This is P(12)
  2. Sum N*P(N) for all even N
$\endgroup$
-1
$\begingroup$

For (1): $\frac1{12!}$. How many ways each of them gets their own coat? How many ways do you have in total?

For (2): your argument is correct.

$\endgroup$
2
  • $\begingroup$ For (2) their argument is still wrong. $\endgroup$
    – Malady
    May 31 at 0:53
  • $\begingroup$ @Malady what is wrong about it? $\endgroup$
    – Kroki
    May 31 at 1:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .