2

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

This is my attempt at solving this problem, please correct me and give me some guidance on how to continue, Thank you!

Calculating Expected Value

$A_i$ is our indicator variable that the elevator stopped at floor $i$. If it stops at floor $i$ then $A_i=1$ to calculate that we say $$Pr[A_i = 1] = 1 − Pr[\text{no one gets off at i}]$$ $$Pr[A_i = 1] = 1 - (1-\frac{1}{n})^m = 1 - (\frac{n-1}{n})^m$$

If $A$ is the number of floors the elevator stops at, then our expected value would be $$E[A] = E[A_1 + · · · + A_n] = E[A_1] + · · · + E[A_n]$$ $$E[A] = n [ 1 - (\frac{n-1}{n})^m]$$ (number of floors times the probability the elevator stops at each floor)

Calculating Variance

$$Var(A) = E[A^2] - [E[A]]^2 = np(1-p)$$ A. variance if it does not stop each floor $$Var(A*) = n [(\frac{n-1}{n})^m][1 - (\frac{n-1}{n})^m] $$ B. variance if it stops at each floor $$Var(A) = n [1 - (\frac{n-1}{n})^m][(\frac{n-1}{n})^m] $$ therefore $$Var(A)=Var(A*)$$

(I interpreted the variance formula as the number of floors times the probability it stops at each floor times the probability that it does not stop at each for B and visa versa for A)

Also, is it easier to calculate the variance for the floors the elevator does not stop at because the probability of that is what we use to get the probability it stops at a floor? is there another reason? or am I totally wrong? Thank you so much for your time!

user168915
  • 155

1 Answers1

2

Outline: We change notation a bit, in order to concentrate on the number of floors the elevator does not stop at. Let $X_i=1$ if the elevator does not stop at floor $i$, and let $X_i=0$ otherwise. Then the number $Y$ of floors the elevator does not stop at is $X_1+X_2+\cdots +X_n$.

You know how to find $E(Y)$, so we confine attention to the variance. As is often the case, this is easiest to find by first finding $E(Y^2)$.

Expand $(X_1+X_2+\cdots +X_n)^2$. We get $$\sum_1^n X_i^2 +2\sum_{1\le i\lt j} X_iX_j.$$ The expectation of the $X_i^2$ has already been done, since $X_i^2=X_i$.

For $E(X_iX_j)$, we want to find the probability that $X_i=1$ and $X_j=1$. You know $\Pr(X_i=1)$. To find $\Pr(X_iX_j=1)$, it is enough to find $\Pr(X_j=1|X_i=1)$. This is done in a way similar to the calculation of $\Pr(X_i=1)$. Just one fewer floor.

André Nicolas
  • 507,029
  • 1
    We have $\Pr(X_iX_j)=1)=(n-1)/n)^m((n-1)/(n-2))^{m}=((n-2)/n)^m$ {one can get this directly, of course). For $2\sum E(X_iX_j)$ multiply by $n(n-1)$. – André Nicolas Aug 10 '14 at 18:28
  • I am absolutely grateful, thank you so much... Bless you! Please, If you can look at this for just a bit, $X_i^2$=$X_i$ because $X_i = 0 xor 1$ but for hypothetical case if $X_i = 0 xor 2$ our $X_i^2$ would not be equal to $X_i$. And over here, we used this method of pairs of i,j n(n-1) to figure out $E(X_iX_j) where i does not equal to j$ instead of directly using our linearity of expectation because the two independent probabilities are not pairwise independent (like flipping a coin). I hope I am understanding this better. – user168915 Aug 10 '14 at 19:07
  • 1
    We expanded $(X_1+\cdots +X_n)^2$ and used linearity of expectation. Since $X_i$ and $X_j$ are not independent, some care had to be taken in finding $E(X_iX_j)$. A similar idea can be used to find the variance of the hypergeometric. Also the binomial, but that is easier since in that case $X_i$ and $X_j$ are independent. – André Nicolas Aug 10 '14 at 19:17
  • makes sense now I want to see how this applies to hypergeometric distribution! you made my day André! – user168915 Aug 10 '14 at 19:30
  • 1
    That is the point of MSE, or should be. The method of indicator random variables can be very useful, particularly when the distribution is difficult to get at. – André Nicolas Aug 10 '14 at 19:41