Our group did a yankee swap yesterday, which got me thinking about a probability question, re: a simplified version without actual "stealing".
Players numbered $1, 2, ..., N$ each brings a wrapped gift. Then in order, player $1, 2, ..., N-1$ each uniformly-randomly picks a wrapped gift which is NOT the one he/she brought, and unwraps it. (By unwrapping it, this gift cannot be picked by any subsequent player.)
Question: What is the probability $p$ that the last wrapped gift was brought by the last player, i.e. $N$? (Or in yankee swap terminology, the last player would be forced to unwrap the gift he/she brought.)
Further thoughts:
- Clearly $1/N$ is not the answer since $N=2 \implies p=0$ (player $1$ is forced to pick the gift brought by player $2$).
- A bit of calculation shows $N = 3 \implies p=1/4$:
- Player $1$ can pick $2$ or $3$, with prob $1/2$ each.
- If player $1$ picked $3$, then player $2$ must pick $1$ and player $3$ will pick $2$.
- If player $1$ picked $2$, then player $2$ can pick $1$ or $3$, with conditional probability $1/2$ each.
- Therefore, the only case of gift $3$ being the last wrapped gift is $1$ picks $2$ and $2$ picks $1$, which happens with probability $1/2 \times 1/2 = 1/4$.
- I would think for large $N$ the probability approaches $1/N$, but stays slightly below. I.e. I imagine $p = 1/N - \epsilon(N)$ where the error term $\epsilon(N) > 0$ and approaches $0$ very very fast (much faster than $1/N$).
- For any $N$, we can solve this exactly using a system of recurrences (involving $3N$ variables, I think...), but I'm wondering if there is a smarter way. E.g. if my second bullet above is correct, is there a good way to calculate or bound the error term?