Red Balls, Green Balls and Expectations

[TenaliRaman]

Suppose r red balls and g green balls are mapped randomly among b bins. Calculate the expected number of bins where red balls are in majority.

My attempt,
Let x_ijk
= 1 (when kth bin contains i red balls and j green balls)
= 0 otherwise

Then,
F = $$\sum_{k=1}^{b} \sum_{i=1}^{r} \sum_{j=0}^{i-1} x_{ijk}$$
Then i calculated E[F]
with E[x_ijk]= (1/b)^(i+j) .. (*)

The final answer is completely in terms of b and r alone and this is quite suspicious. I expect g to be in the expression.

I think i am making some obvious mistake but what is it or is it a mistake at all is something which i am not able to identify.

-- AI

 

[LeonhardEuler]

OK, here's a long way of doing it. You calculate the probability that there are more red balls than green in one particular bin. The expectation of the number of bins with more red than green balls is that probability times the number of bins. The long part is calculating that probability:

Each ball is equally likely to go in anyone of the "b" bins, so the probability that it goes into a particular bin is 1/b. Number each of the green balls from 1 to g and each of the red balls from 1 to r. Introduce the random variable $G_i$ which is equal to 1 if green ball number i goes into the bin we are considering and 0 otherwise. Simmilarly introduce $R_j$, which is 1 if the jth red ball goes into this bin and 0 otherwise. The probablity that the number of red balls is greater than the number of green balls is the probabilty that
$$\sum_{i=1}^r R_i > \sum_{i=1}^g G_i$$
The problem now is to find the p.m.f's of these sums for certain values. The probability that there are more red balls than green is equal to the probability that there is 1 red ball and no green + probability of 2 red, 0 green + 2 red 1 green, +... +r red, min[(r-1),g] green. Each of these probabilities can be calculated as a Binomial distribution: the probability of x red balls is $\binom{r} {x} (\frac{1} {b})^x(\frac{b-1} {b})^{r-x}$. Simmilarly the probability of y green balls is $\binom{g} {y} (\frac{1} {b})^y(\frac{b-1} {b})^{g-y}$. Since these probabilities are independent the probability of y green balls and x red balls is
$$\binom{r} {x} (\frac{1} {b})^x(\frac{b-1} {b})^{r-x}\binom{g} {y} (\frac{1} {b})^y(\frac{b-1} {b})^{g-y}$$.
To get the probability that the number of red balls exceeds the number of green balls you have to do one of the following sums:
case 1: g is greater than or equal to (r-1)
$$\sum_{k=1}^r\sum_{i=0}^{(k-1)} \binom{r} {k}\binom{g} {i}(\frac{1} {b})^k(\frac{b-1} {b})^{r-k} (\frac{1} {b})^i(\frac{b-1} {b})^{g-i}$$
case 2: g is less than (r-1)
$$\sum_{k=1}^{(g+1)}\sum_{i=0}^{(k-1)} \binom{r} {k}\binom{g} {i}(\frac{1} {b})^k(\frac{b-1} {b})^{r-k} (\frac{1} {b})^i(\frac{b-1} {b})^{g-i} + \sum_{k=(g+2)}^r\sum_{i=0}^g \binom{r} {k}\binom{g} {i}(\frac{1} {b})^k(\frac{b-1} {b})^{r-k} (\frac{1} {b})^i(\frac{b-1} {b})^{g-i}$$
Maybe there is some easier way of doing it, but it doesn't strike me.

 

[TenaliRaman]

(Sorry for the late reply).

Yeah that's is a long way around, i was hoping there was some way to avoid it. I was trying to simplify the above expression in order to gain some insight maybe. It only got messy that way. Oh well, that's the only way left for now i guess :-/.

Thanks for the help btw.

-- AI