0

There are $n$ marbles and $r$ boxes. One at a time, each marble is selected and randomly (uniformly) placed in one of the $r$ boxes. Let $S$ be the number of empty boxes. Compute $E(S)$ and $Var(S )$.

Here is my work:

Let $X$ = the box is empty

This gives me:

\begin{equation} X_i = \begin{cases} 1 \text{ if box is empty} \\ 0 \text{ if box is not empty} \end{cases} \end{equation}

This means that $S = \sum_i^rX_i$

This leads me to:

\begin{equation} E(S) = E(X_1 + X_2 + ...X_r) \end{equation} \begin{equation} E(S) = E(X_1) + E(X_2) + ...E(X_r) \end{equation} \begin{equation} E(S) = r p \quad \text{ $p$ is the probability that box is empty} \end{equation}

so I need to figure out $p$ which I said is simpy $\frac{r-n}{r}$

Therefore \begin{equation} E(S) = r\frac{r-n}{r} = r-n \end{equation}

Am I correct? Or am I missing something?

I'm also stuck in variance at

\begin{equation} Var(S) = Var(X_1 + X_2 + ... X_r) \end{equation}

user3904534
  • 127
  • Everything look fine until you figure out $p$. So the probability of an empty box is negative if you have $2$ boxes and $3$ marbles? That doesn't sound right. – bof Dec 04 '15 at 01:48
  • You can get $Var(S)$ from $E(S)$ and $E(S^2)$. – bof Dec 04 '15 at 01:50
  • 1
    E($S^2)=E(X_1^2+\cdots+X_r^2+2X_1X_2+2X_1X_3+\cdots+2X_{r-1}X_r)$ – bof Dec 04 '15 at 01:55

1 Answers1

2

The probability a particular box is empty is $$\left(\frac{r-1}{r}\right)^n.$$ For the probability the throw lands in another box is $\frac{r-1}{r}$, and for the probability this happens $n$ times in a row we take the $n$-th power.

Remark: For the variance, we will need to calculate $E(\sum X_i)^2-(E(\sum X_i))^2$. To calculate the first term, expand the square. We get something of the shape $\sum X_i^2 +\sum_{i\ne j} X_iX_j$.

To find $E(X_iX_j)$ we will need the probability that boxes $i$ and $j$ are both empty. That is done using reasoning similar to that of the answer above.

André Nicolas
  • 507,029
  • You are welcome. The variance calculation is somewhat not fun, but each step is straightforward. Of course $E(\sum X_i^2)$ is easy since $X_i^2=X_i$. But the cross terms are a bit of a nuisance, and then we have to subtract the square of the (already known) expectation of $\sum X_i$. But when one finishes things end up looking quite nice. – André Nicolas Dec 04 '15 at 02:04
  • is $S^2$ a binomial expansion? can I use that? – user3904534 Dec 04 '15 at 02:09
  • Well, it is a special case of a multinomial expansion, but saying so doesn't add anything. It is a simple fact that in general $(u_1+\cdots+u_n)^2=(u_1^2+\cdots+u_n^2)+\sum_{i\ne j}u_iu_j$, where there are $n(n-1)$ terms in the second sum. That part can be replaced by $2\sum_{i\lt j}u_iu_j$, where now there are $\binom{n}{2}$ terms in the sum. If this is not clear to you, calculate $(u_1+u_2+u_3)^2$. – André Nicolas Dec 04 '15 at 06:34