There are $m$ black and $n$ red balls in an urn. One randomly picks a ball from the urn. If the picked ball is the black one, person changes it with the red ball and returns to the urn. If the picked ball is red, he does nothing and just returns the ball to the urn.
The questions are as follows:
- Find the expected value of number of red balls in the urn after $k$ iterations.
- Find the variance of number of red balls in the urn after $k$ iterations.
Also, there was given a note that answer are compact expressions, i.e. they do not contain summation signs.
I tried solving this problem in rather straightforward way, made a few steps and realised it would be really complicated to go that way. So, let $\xi$ be our random variable of number of red balls after $k$ iterations, and let $N = n + m$.
-
If there was no black balls picked, namely, $k$ red balls are taken out in a row, the probability is simple to write:
$$P(\xi = n) = \left( \frac{n}{N} \right)^k$$ -
If there is one black ball picked. Let $j$ be a position where the black ball appeared. This means that at from $1$-st to $(j – 1)$-th positions there were sampled only red ball with probability $\frac{n}{N}$, and from $(j + 1)$-th to $k$-th there were again red balls but with probability $\frac{n + 1}{N}$ altogether:
$$P(\xi = n + 1) = \sum\limits_{j = 1}^k \left( \frac{n}{N} \right)^{j – 1} \frac{m}{N} \left( \frac{n + 1}{N} \right)^{k – j – 1}.$$
And I stucked already at this point as have no idea how to write this sum compactly, moreover, if in this manner star looking at $\xi = n + 2, \ldots, \xi = n + k$ there will be to many inner summations to handle.
I also tried to think about possible standard way of handling that kind of problems with indicators, but also failed creating one.
So, I think there should be a smarter solution. Would appreciate any help with this problem!
Best Answer
For the Expected Value: Just use indicator values.
Of course all of the red ones are still red at the end, so define $X_1, \cdots, X_m$ to be the indicator variables for the $m$ balls that start out black. That is $X_1=1$ if black ball $\#1$ is red at the end and it $=0$ otherwise. Then, of course, All the $X_i$ have the same expectation so $$E=n+m\times E[X_1]$$
What is $E[X_1]$? Well, in order to stay black the ball must be missed in each of the $k$ selections. The probability of being missed in any given selection is $\frac {m+n-1}{m+n}$ so the probability it is missed in all $k$ selections is $\left(\frac {m+n-1}{m+n}\right)^k$. Thus $$E[X_i]=1-\left(\frac {m+n-1}{m+n}\right)^k$$ which implies that $$E=n+m\times \left(1-\left(\frac {m+n-1}{m+n}\right)^k\right)$$
Sanity checks: if $k=0$ then $E=n$ as it should. As $k\to \infty$ we have $E=n+m$, again as it should. And if $n=m=k=1$ then $E=1.5$ which is easily verified. More broadly, if $k=1$ and $m,n$ are arbitrary then this gives the correct answer of $n+\frac m{m+n}$.
For the Variance we can proceed along the same lines. Letting $$Z=X_1+\cdots +X_m+n$$ we see that $E=E[Z]$ and that the variance is given by $$E[Z^2]-E^2$$
To compute $E[Z^2]$ we remark that $$Z^2=X_1^2+\cdots +X_m^2+n^2+2n\sum X_i+2 \sum_{i<j}X_iX_j$$ $$=n^2+(2n+1)\sum X_i+2\sum_{i<j}X_iX_j$$
Where we have used the fact that $X_i^2=X_i$ for all $i$. The only tricky terms to compute are those of the form $E[X_iX_j]$ for $i\neq j$. To do that, we need to compute the probability that both the $i^{th}$ and the $j^{th}$ black balls are selected at least once. I think it is easier to compute the complement. The probability that neither are selected at all is just $$\left( \frac {m+n-2}{m+n}\right)^k$$ and the probability that one is selected and the other is not is $$2\times \left( \frac {m+n-1}{m+n}\right)^k\times \left(1-\left(\frac {m+n-2}{m+n-1}\right)^k\right)$$
The rest is just a matter of putting the pieces together. The algebra should be messy, but not all that difficult.