Solution: 2015 Fall Final - 19

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

For each $i = 1,2,\dots,n$, let $v_i$ be the value (in dollars) of the gift that student $S_i$ buys. Let $Y$ be the value of the gift that student $S_1$ receives, and let $Z$ be the value of the gift that student $S_2$ receives. What is $\mathbb{E}(2 \cdot Y - Z)$?

(a)

$2 \sum_{i=2}^{n} v_i/n - (v_1/n + \sum_{i=3}^{n} v_i/n)$

(b)

$2v_1 - v_2$

(c)

$\sum_{i=1}^{n} v_i/n$

(d)

$\sum_{i=3}^{n} v_i/n$

Solution

Okay. This is a loaded question, so let’s break it down

Let's find the expected value of $Y$
The first student has a $ \frac{1}{n} $ chance of receiving a gift of $v_1$
The second student has a $ \frac{1}{n} $ chance of receiving a gift of $v_2$
...
The $n$th student has a $ \frac{1}{n} $ chance of receiving a gift of $v_n$
$ \mathbb{E}(Y) = \sum_{i=1}^{n} \frac{v_i}{n} $
$ \mathbb{E}(Y) = \frac{1}{n} \sum_{i=1}^{n} v\_i $
Let's find the expected value of $Z$
The first student has a $ \frac{1}{n} $ chance of receiving a gift of $v_1$
The second student has a $ \frac{1}{n} $ chance of receiving a gift of $v_2$
...
The $n$th student has a $ \frac{1}{n} $ chance of receiving a gift of $v_n$
$ \mathbb{E}(Z) = \sum_{i=1}^{n} \frac{v\_i}{n} $
$ \mathbb{E}(Z) = \frac{1}{n} \sum_{i=1}^{n} v\_i $

$ \mathbb{E}(2 \cdot Y - Z) $

$ = \mathbb{E}(2 \cdot Y) - \mathbb{E}(Z) $

$ = 2 \cdot \mathbb{E}(Y) - \mathbb{E}(Z) $

$ = 2 \cdot \frac{1}{n} \sum_{i=1}^{n} v_i - \frac{1}{n} \sum_{i=1}^{n} v_i $

$ = \frac{2}{n} \sum_{i=1}^{n} v_i - \frac{1}{n} \sum_{i=1}^{n} v_i $

$ = \frac{2 - 1}{n} \sum_{i=1}^{n} v_i $

$ = \frac{1}{n} \sum_{i=1}^{n} v_i $

$ = \sum_{i=1}^{n} \frac{v_i}{n} $