Quote:

Originally Posted by

**chil2e** Five probabilists at a meeting remove their name tags and put them in a bag. Then they each randomly choose one of the tags. What is the probability that exactly one of them gets the correct name tag?

Let's first determine the probability that the first person picks his own name and the remaining 4 people do __NOT__ pick their own names.

Knowing this, we cast the first person aside for right now, and consider the the following question: Four people remove their name tags and put them in a hat. Then they each randomly choose one of the tags. What is the probability that exactly **none** picks their own name?

Let E denote the event that **NO** matches occur. Since the probability depends on n, the number of people choosing, we write $\displaystyle P_n=P(E) $. We are going to go about this solution recursively, so we begin by conditioning on whether or not the first (of 4) people draws his own name tag. Let's denote these events $\displaystyle I \text{ and } I^c $. So,

$\displaystyle

P_n = P(E) = P(E|I) P(I) + P(E|I^c) P(I^c)

$

Note that $\displaystyle P(E|I) = 0 $, and thus

$\displaystyle P_n = P(E|I^c) P(I^c) = P(E|I^c) (\tfrac{n-1}{n}) $.

Now, $\displaystyle P(E|I^c) $ is the probability that none of n-1 people pick their own name tag when selecting from a hat containing n-1 tags with exactly one of the tags not belonging to any of the n-1 people. (So, there 1 "extra person" whose name tag is not in the hat, and there is 1 extra tag in the hat which does not belong to any of the men choosing.) This can happen in two mutually exclusive ways:

1) No matches and extra man does NOT select the extra hat (hat of man who chose first). The probability of this event is $\displaystyle P_{n-1} $ (which we get if we assume the extra hat belongs the extra person).

2) No matches and extra man DOES INDEED select the extra hat. The probability of this event is $\displaystyle \tfrac{1}{n-1}P_{n-2} $.

Since the two ways described above are mutually exclusive, $\displaystyle P(E|I^c) $ is simply the sum of the two probabilities; i.e.,

$\displaystyle P(E|I^c) = P_{n-1} + \tfrac{1}{n-1} P_{n-2}$

.

Now, we can plug this information into the equation for $\displaystyle P_n $:

$\displaystyle

P_n = P(E|I^c) \tfrac{n-1}{n} = \tfrac{n-1}{n} P_{n-1} + \tfrac{1}{n} P_{n-2} \implies P_n - P{n-1} = -\tfrac{1}{n} (P_{n-1} - P_{n-2})

$

Aha! Recursion! It can do the rest of our dirty work.

So we have $\displaystyle P_n $ is the probability of n people all selecting a name tag that is NOT their own (no matches). Thus,

$\displaystyle

P_1 = 0

$

$\displaystyle

P_2 = \tfrac{1}{2}

$

Now we take advantage of that recursion.

$\displaystyle

P_3 - P_2 = -\tfrac{p_2 - P_1}{3} = -\tfrac{1}{3!} \implies P_3 = \tfrac{1}{2!} - \tfrac{1}{3!}

$

$\displaystyle

P_4 - P_3 = -\tfrac{p_3 - P_2}{4} = -\tfrac{1}{4!} \implies P_4 = \tfrac{1}{2!} - \tfrac{1}{3!} + \tfrac{1}{4!}

$

Therefore, the probability of 4 people each selecting name tags (each person's name included) that are NOT their own is $\displaystyle P_4 = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} = 0.375 $.

Now, let's bring back the real first person to select from the hat. The probability that he, selecting first, selected his name own tag is 1/5. So the probability of (HIT, MISS, MISS, MISS, MISS) is (3/8)/(1/5). However, not __only__ must we consider this person being "the one" to select his own hat (while the others don't), we must also consider the separate events whereby each of the other four people is "the only one" to select his name tag. So, we multiply (3/8)/(1/5) by (1/5), which cancels out the (1/5) in (3/8)/(1/5). Thereforeforeforefore, the probability of EXACTLY ONE person selecting his own name tag in our problem is 3/8 = 0.375.

-Andy