# $e$ showing up in expected value

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.

• 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 – antkam Dec 27 '19 at 2:55

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