Question

A building has n floors numbered 1,2,...,n, plus a ground floor g. at the ground floor, m people get on the elevator together, and each gets off at a uniformly random one of the n floors (independently of everybody else). what is the variance of the number of floors the elevator does not stop at? (in fact, the variance of the number of floors the elevator does stop at must be the same (do you see why?) but the former is a little easier to compute.)

Answer 1

Let $X_i$ be the random variable indicating whether the elevator does not stop at floor $i$, with

$X_i=\begin{cases}1&\text{if the elevator does not stop at floor }i\\0&\text{otherwise}\end{cases}$

Let $Y$ be the random variable representing the number of floors at which the elevator does not stop. Then

$Y=X_1+X_2+\cdots+X_{n-1}+X_n$

We want to find $\mathrm{Var}(Y)$. By definition,

$\mathrm{Var}(Y)=\mathbb E[(Y-\mathbb E[Y])^2]=\mathbb E[Y^2]-\mathbb E[Y]^2$

As stated in the question, there is a $\dfrac1n$ probability that any one person will get off at floor $n$ (here, $n$ refers to any of the $n$ total floors, not just the top floor). Then the probability that a person will not get off at floor $n$ is $1-\dfrac1n$. There are $m$ people in the elevator, so the probability that not a single one gets off at floor $n$ is $\left(1-\dfrac1n\right)^m$.

So,

$\mathbb P(X_i=x)\begin{cases}\left(1-\dfrac1n\right)^m&\text{for }x=1\\\\1-\left(1-\dfrac1n\right)^m&\text{for }x=0\end{cases}$

which means

$\mathbb E[Y]=\mathbb E\left[\displaystyle\sum_{i=1}^nX_i\right]=\displaystyle\sum_{i=1}^n\mathbb E[X_i]=\sum_{i=1}^n\left(1\cdot\left(1-\dfrac1n\right)^m+0\cdot\left(1-\left(1-\dfrac1n\right)^m\right)$
$\implies\mathbb E[Y]=n\left(1-\dfrac1n\right)^m$

and

$\mathbb E[Y^2]=\mathbb E\left[\left(\displaystyle\sum_{i=1}^n{X_i}\right)^2\right]=\mathbb E\left[\displaystyle\sum_{i=1}^n{X_i}^2+2\sum_{1\le i$

Computing $\mathbb E[{X_i}^2]$ is trivial since it's the same as $\mathbb E[X_i]$. (Do you see why?)

Next, we want to find the expected value of the following random variable, when $i\neq j$:

$X_iX_j=\begin{cases}1&\text{if }X_i=1\text{ and }X_j=1\\0&\text{otherwise}\end{cases}$

If $X_iX_j=0$, we don't care; when we compute $\mathbb E[X_iX_j]$, the contributing terms will vanish. We only want to see what happens when both floors are not visited.

$\mathbb P(X_iX_j=1)=\left(1-\dfrac2n\right)^m$
$\implies\mathbb E[X_iX_j]=\left(1-\dfrac2n\right)^m$
$\implies2\displaystyle\sum_{1\le i$

where we multiply by $n(n-1)$ because that's how many ways there are of choosing indices $i,j$ for $X_iX_j$ such that $1\le i$.

So,

$\mathrm{Var}[Y]=n\left(1-\dfrac1n\right)^m+2n(n-1)\left(1-\dfrac2n\right)^m-n^2\left(1-\dfrac1n\right)^{2m}$