Solution: 2015 Fall Final - 18

Author: Michiel Smid

Question

The $n$ students $S_1,S_2,\dots,S_n$ decide to organize a Secret Santa: They take a uniformly random permutation $P_1,P_2,\dots,P_n$ of $S_1,S_2,\dots,S_n$. For each $i = 1,2,\dots,n$, student $S_i$ buys a gift and gives it, anonymously, to student $P_i$.

Let $X$ be the number of students who give their gift to themselves. What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use an indicator random variable for each student.

(a)

$1$

(b)

$2 + 1/n$

(c)

$2$

(d)

$1 + 1/n$

Solution

The first student has a $ \frac{1}{n} $ chance of giving a gift to themselves.

The second student has a $ \frac{1}{n} $ chance of giving a gift to themselves.

…

The $n$th student has a $ \frac{1}{n} $ chance of giving a gift to themselves.

$ E(X) = \sum_{i=1}^{n} \frac{1}{n} $

$ E(X) = n \cdot \frac{1}{n} $

$ E(X) = 1 $