# Variance for the number of trials before success in an urn problem without replacement

This question is asked as an extension of: Expectation of number of trials before success in an urn problem without replacement

(Note: I am not the author of the original question.)

We have $b$ blue balls and $r$ red balls in an urn. Sampling the urn sequentially and without replacement, we remove red balls until we select a blue ball. In the previous question, Byron Schmuland (and others) calculated that the expected number of balls drawn before drawing a blue ball should be:

$\mathbb{E}(\mbox{number of balls drawn})=1+\sum_{i=1}^r \mathbb{E}(Z_i)=1+r\left({1\over b+1}\right)$

And therefore, we have that:

$\mathbb{E}(\mbox{number of red balls drawn})=1+\sum_{i=1}^r \mathbb{E}(Z_i)-1=1+r\left({1\over b+1}\right)-1$

My question is:

What is the variance for the number of red balls drawn, i.e. $Var[\mbox{number of red balls drawn}]$?

Edit: The indicator random variables have been radically changed, so that one gets a very quick computation of the mean and variance.

Let $Y$ be the number of reds drawn before the first blue. Suppose that the red balls have labels $1, 2, 3,\dots,r$. Let $X_i=1$ if red ball with label $i$ is drawn before the first blue is drawn, and let $X_i=0$ otherwise.

Then $Y=X_1+\cdots+X_r$. Note that the number of draws up to an including the first blue is $Y+1$. But $Y+1$ and $Y$ have the same variance.

To calculate the variance of $X_i$, we first calculate the mean. By linearity of expectation we have $$E(Y)=E(X_1)+E(X_2)+\cdots+E(X_r).$$ By symmetry, all the $E(X_i)$ are the same. The probability red with label $i$ comes before any of the $b$ blue is $\frac{1}{b+1}$. It follows that $E(Y)=\frac{r}{b+1}$.

To calculate the variance of $Y$, calculate $E(X_1+\cdots +X_{r})^2$ and subtract the square of $E(Y)$, which we know.

To find $E(X_1+\cdots+X_r)^2$, expand the square and use the linearity of expectation. We know the expectation of $\sum X_i^2$, since $X_i^2=X_i$. So we need the expectations of the cross terms.

For $i\ne j$, $X_iX_j=1$ if both red ball $i$ and red ball $j$ come before any blue. This has probability $\frac{2}{(b+2)(b+1)}$. Multiply by $2\binom{r}{2}$ to get the sum of the cross terms.

• Am I correct in assuming that $\mathrm{E}(X_j)=\left.\binom{r}{j}\middle/\binom{b+r}{j}\right.$? Congrats on setting the mark :-)
– robjohn
Commented May 7, 2013 at 19:24
• Yes, that would be an expression for it. Commented May 7, 2013 at 19:37
• Is there another expression for it that is easier to sum. Otherwise, it seems that this requires about as much computation as my method. There is nothing wrong with that; I was just hoping you had something that was computationally easier.
– robjohn
Commented May 7, 2013 at 21:39
• @robjohn: Revised answer completely rewritten, so that we get variance also in a couple of lines, with minimal computation. Agree that my previous one was computationally unattractive. Commented May 8, 2013 at 13:40
• This is much nicer than before (and it agrees with my answer) (+1)
– robjohn
Commented May 8, 2013 at 14:25

The probability of drawing $n$ red balls then a blue ball is $$\frac{r}{b+r}\frac{r-1}{b+r-1}\frac{r-2}{b+r-2}\cdots\frac{r-n+1}{b+r-n+1}\frac{b}{b+r-n} =\frac{\binom{\vphantom{b+}r}{n}}{\binom{b+r-1}{n}}\frac{b}{b+r}\qquad\tag{1}$$ Since a blue ball must be drawn eventually, $(1)$ indicates that $$\sum_{n=0}^r\frac{\binom{\vphantom{b+}r}{n}}{\binom{b+r-1}{n}}=\frac{b+r}{b}\tag{2}$$ which can be proven by induction on $r$.

$(2)$ is true for $r=0$. Assume $(2)$ is true for $r-1$, then \begin{align} \sum_{n=0}^r\frac{\binom{\vphantom{b+}r}{n}}{\binom{b+r-1}{n}} &=1+\sum_{n=1}^r\frac{\frac{\vphantom{b+}r}{n}\binom{r-1}{n-1}}{\frac{b+r-1}{n}\binom{b+r-2}{n-1}}\\ &=1+\frac{r}{b+r-1}\sum_{n=0}^{r-1}\frac{\binom{r-1}{n}}{\binom{b+r-2}{n}}\\ &=1+\frac{r}{b+r-1}\frac{b+r-1}{b}\\ &=\frac{b+r}{b} \end{align}

There is a more direct proof of this identity at the end of this answer.

Using $(2)$, the expected number of red balls drawn is \begin{align} \sum_{n=0}^r\frac{\binom{\vphantom{b+}r}{n}}{\binom{b+r-1}{n}}\frac{b}{b+r}n &=\frac{br}{b+r}\sum_{n=0}^r\frac{\binom{r-1}{n-1}}{\binom{b+r-1}{n}}\\ &=\frac{br}{b+r}\sum_{n=0}^r\frac{\binom{r\vphantom{+1}}{n}-\binom{r-1}{n}}{\binom{b+r-1}{n}}\\ &=\frac{br}{b+r}\left(\frac{b+r}{b}-\frac{b+r}{b+1}\right)\\ &=\frac{r}{b+1}\tag{3} \end{align} which agrees with the result in the question.

Using $(2)$ the expected value of $n(n-1)$ is \begin{align} \sum_{n=0}^r\frac{\binom{\vphantom{b+}r}{n}}{\binom{b+r-1}{n}}\frac{b}{b+r}n(n-1) &=\frac{br(r-1)}{b+r}\sum_{n=0}^r\frac{\binom{r-2}{n-2}}{\binom{b+r-1}{n}}\\ &=\frac{br(r-1)}{b+r}\sum_{n=0}^r\frac{\binom{r\vphantom{-1}}{n}-2\binom{r-1}{n}+\binom{r-2}{n}}{\binom{b+r-1}{n}}\\ &=\frac{br(r-1)}{b+r}\left(\frac{b+r}{b}-2\frac{b+r}{b+1}+\frac{b+r}{b+2}\right)\\ &=\frac{2r(r-1)}{(b+1)(b+2)}\tag{4} \end{align} Thus, the variance, which is the mean of the squares minus the square of the mean is $$\frac{2r(r-1)}{(b+1)(b+2)}+\frac{r}{b+1}-\left(\frac{r}{b+1}\right)^2 =\frac{br(b+r+1)}{(b+1)^2(b+2)}\tag{5}$$

$$Z_i$$ is the indicator that red ball $$i$$ is drawn before the first blue ball. (That all blue balls are drawn after it.)

Among the set of $$b+1$$ balls that are: "all blue balls plus red ball $$i$$", each one is equally likely to be drawn first, so the probability for our favoured event happens is $$1/(b+1)$$.$$\mathsf E(Z_i)=\dfrac 1{b+1}\\\mathsf E(\sum_{i=1}^rZ_i)=\dfrac{r}{b+1}$$

Similarly, by considering the set of $$b+2$$ balls that are: "all blue balls, plus two distinct red balls $$i$$ and $$j$$", we may derive the probability for both these red balls being before the blue balls. Then use this $$\mathsf E(Z_iZ_j)$$ to evaluate:

So \begin{align}\mathsf{Var}(Z) &= \mathsf E(Z^2)-\mathsf E(Z)^2\\[1ex] &=\sum_{i=1}^r\mathsf E(Z_i^2)+2\sum_{i=2}^{r}\sum_{j=1}^{i-1}\mathsf E(Z_iZ_j)~-\mathsf E(Z)^2\\[1ex]&=\dfrac r{b+1}+\dfrac{2~r~(r-1)}{(b+2)(b+1)}~-\dfrac{r^2}{(b+1)^2}\\[1ex]&=\dfrac{b r (b + r + 1)}{(b + 1)^2 (b + 2)}\end{align}