3
$\begingroup$

This problem comes from something we do each Thanksgiving. This past Thanksgiving we had 19 (N) people at dinner. Each person writes something for which they are thankful and puts the slip of paper into a bowl. The slips are mixed up and each person draws a slip. This past holiday, someone got their own slip. My question is given an N (19 for example) what is the probability no one gets their own slip? I give a solution below but have some questions (perhaps you'd like to try to solve it without peeking at the answer I provide). Perhaps you can find a more elegant solution. Here are my questions: Is there a name for this problem? The probability oscillates which surprises me; can you offer a similar problem where the problem oscillates? By the way the probability converges a N increases to what I am calling the Turkey Ratio. Does this value appear elsewhere?

So here are the probabilities for 2 to 25:
2: 0.5
3: 0.66666666666666674
4: 0.625
5: 0.6333333333333333
6: 0.63194444444444442
7: 0.63214285714285712
8: 0.63211805555555556
9: 0.63212081128747788
10: 0.63212053571428573
11: 0.63212056076639411
12: 0.63212055867871841
13: 0.63212055883930884
14: 0.63212055882783802
15: 0.63212055882860274
16: 0.632120558828555
17: 0.63212055882855789
18: 0.63212055882855767
19: 0.63212055882855767
20: 0.63212055882855767
21: 0.63212055882855778
22: 0.63212055882855767
23: 0.63212055882855767
24: 0.63212055882855789
25: 0.63212055882855767

So here is the process to generate the probability given that there are n guests.
1. Create a list of the factorials from n! to 0!. (For n=4, we’d have 24, 6, 2, 1, 1)
2. Save first value in the list (24).
3. Create a list of the difference in successive values of the list. (18, 4, 1, 0)
4. Save the first value in the list (18).
5. Repeat steps 3 to 4 until you have saved n+1 values (24, 18, 14, 11, 9)
6. The answer is 1 – the last number divided by the first number (0.625 = 1 - 9/24)

I'm thankful for Cross-Validated and whatever help you provide.

$\endgroup$
3
  • $\begingroup$ In classification problems there is a bootstrap estimator called the 632 estimator. It is in the limit the percentage of original observations samples that appear in a bootstrap sample. This happens because the bootstrap samples with replacement and so some of the original observations are repeated in a bootstrap sample. See this covered in my book Bootstrap Methods: A Guide to Practitioners Chernick (2007) Wiley. This is also 1-1/e as mentioned by Lukasz Grad in his answer. $\endgroup$ Jan 27 '17 at 20:43
  • 2
    $\begingroup$ This has various names (but due to partial name clashes with other problems, it's hard to search for). It's often called the absent minded secretary problem (which leads to confusion with the secretary problem, also called the marriage problem), sometimes called the letters in envelopes problem (which leads to confusion/search clashes with the two envelope problem), and sometimes called the matching problem (clashing with an alternative name for the stable marriage problem) -- though it has other names. See the Matching problem $\endgroup$
    – Glen_b
    Jan 28 '17 at 0:38
  • 2
    $\begingroup$ There's also a discussion of it here as Matching Envelopes and Letters (it's also sometimes called the letters in envelopes problem and sometimes the hat problem and sometimes the airplane seat problem. There are one or two other questions on site relating to this problem, such as this one: stats.stackexchange.com/questions/188503/… $\endgroup$
    – Glen_b
    Jan 28 '17 at 0:44
5
$\begingroup$

Your turkey ratio is simply $1 - \frac{1}{e}$ = 0.63212055882... (as N approaches infinity)

Try to prove it. It's a nice exercise. You can also check https://en.wikipedia.org/wiki/Derangement

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.