6
$\begingroup$

My question was inspired by this numberphile video on the maths of secret santa.

So suppose you have a group of $n$ people who are all randomly choosing another person in the group at random. The probability the any given person chooses themselves is $p = 1/n$ and the expected value of $X$ (the number of people who choose themselves) is equal to $np = n \times 1/n = 1$. If someone(s) chooses themselves, then everyone has to choose another person at random again.

Let's define the random variable $Y$ as the number of attempts the group will have to make until everyone chooses someone who is not themselves.

My question is, find the expected value of $Y$, $E(Y)$.

I didn't know how to compute this mathematically but when I ran a bunch of simulations I found that the answer rounded to $e$ ($2.71828\ldots$)!

Can someone please explain why $e$ is showing up here.

$\endgroup$
1
  • 2
    $\begingroup$ If people choose independently, s.t. it is possible for two people to choose the same person, then the answer by @eyeballfrog is correct. Curiously, even if people are somehow guaranteed to choose differently (i.e. the choices are dependent and indeed forms a random permutation), the answer is still $e$. This is because a random permutation has a $1/e$ chance of being a derangement $\endgroup$ – antkam Dec 27 '19 at 2:55
11
$\begingroup$

The probability that a person chooses someone not themself is $1-1/n$, and since everyone chooses independently, the probability that no person chooses themself is $$ p = \left(1-\frac{1}{n}\right)^n $$ If $n$ is large, then $p\approx 1/e$. Since the average number of times it takes for an event with probability $p$ to happen is $1/p$, we have $E(X) \approx e$.

$\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.