Expected number of different colored balls in the same bin

546 Views Asked by At

Let's say I have $K$ bins and big jar of balls containing $X$ balls. The jar actually contains $W$ white balls and $B$ black balls.

Now I'll extract one ball from the jar and throw in one of the $K$ bins with uniform probability $\left(\frac{1}{K}\right)$. The extraction/throwing process continues until no balls are left in the original jar.

What is the expected number of bins containing at least two balls of different colors?

1

There are 1 best solutions below

4
On BEST ANSWER

For $i=1$ to $K$, let random variable $X_i$ be $1$ if Bin $i$ has at least two balls of different colours, and let $X_i=0$ otherwise. We want the expectation of $X_1+\cdots +X_K$. By linearity of expectation this is the sum of the expectations of the $X_i$.

We have $E(X_i)=\Pr(X_i=1)$, so we want to find the probability Bin $i$ has at least two balls of different colours.

We find the probability of at least one white. This is $1$ minus the probability of no white. The probability of no white is the probability all the $W$ white balls miss Bin $i$.

On one throw, the probability a ball misses Bin $i$ is $\frac{K-1}{K}$. So the probability all the $W$ white balls miss Bin $i$ is $\left(\frac{K-1}{K}\right)^W$. It follows that the probability of at least one white is $$1-\left(\frac{K-1}{K}\right)^W.$$

Similarly, we can find the probability of at least one black. For the probability of at least one of each in Bin $i$, multiply. For the final answer about the expected number with at least one of each, multiply by $K$.