Solution: 2018 Fall Final - 24
Author: Michiel SmidQuestion
Let $n \geq 2$ be an integer. There are $n$ students $S_1,S_2,\dots,S_n$ writing this exam. Each
student has brought one backpack with them. Before the exam starts, all students have to leave their
backpacks at the front of the examination room.
At the end of the exam, the proctor places the backpacks in a uniformly random order $b_1,b_2,\dots,b_n$, and, for each $i = 1, 2, ..., n$, gives backpack $b_i$ to student $S_i$.
Define the following random variable $X$:
Hint: Use indicator random variables.
At the end of the exam, the proctor places the backpacks in a uniformly random order $b_1,b_2,\dots,b_n$, and, for each $i = 1, 2, ..., n$, gives backpack $b_i$ to student $S_i$.
Define the following random variable $X$:
- X = the number of students who get their own backpack.
Hint: Use indicator random variables.
(a)
1
(b)
$\left. (n + 1) \middle/ n \right.$
(c)
$\left. (n - 1) \middle/ n \right.$
(d)
2
Solution
Let $X_i$ be 1 if student $S_i$ gets their own backpack and 0 otherwise
$ Pr(X_i = 1) = \frac{1}{n} $
Now, we do this for every student
$ \mathbb{E}(X) = \mathbb{E}(X_1 + X_2 + \text{…} + X_n) $
$ \mathbb{E}(X) = \sum_{k=1}^{n} \mathbb{E}(X_i) $
$ \mathbb{E}(X) = \sum_{k=1}^{n} \frac{1}{n} $
$ \mathbb{E}(X) = \frac{n}{n} $
$ \mathbb{E}(X) = 1 $