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