Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Thirty people are invited to a holiday party, where a gift exchange will take place. Each person brings a gift to put into the pot, and at the end of the night each person selects—at random—one gift from the pot to take home.

The probability of one (1) person accidentally choosing their own gift from the pot is equal to $\frac{1}{30} \approx 3.33\%$, obviously.

What is the probability that at least one person will accidentally choose their own gift? In other words, how unlikely is it that all 30 guests will take home a new present?

share|improve this question
Also related: – cardinal Dec 2 '12 at 20:33
Also called the matching problem, the envelope-matching problem, the envelope-letter problem, the forgetful(/absent-minded) secretary problem (among other names). e.g. see here – Glen_b Dec 2 '12 at 23:27

Why not build a stochastic simulation? You can get an empirical estimate.

number the gifts according to who brought them. Gift 1 was brought by person 1. Uniformly randomly draw gifts without replacement count how many gifts were drawn at their number. So if gift 10 was the tenth one drawn, count it. store the value in an array repeat a couple hundred thousand times.

Make a CDF of the distribution of the sums. See if you can fit it to something analytic.

Part of the fun of a stochastic simulation is that you can change the rules, even in nonlinear ways, and have near-immediate results.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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