An urn contains $n + m$ balls, of which n are red and m are black. They are withdrawn from the urn, one at a time and without replacement. Let $X$ be the number of red balls removed before the first black ball is chosen. Find the expected value $\mathbb{E}[X]$.


In the solution, of this problem , from here,

Finding the number of red balls drawn before the first black ball is chosen

It has been said that, there are $m+1$ special black balls. But, from the problem description we know that, there are m black balls.

i) Why are $m+1$ balls considered? In a post I read that it has to do with some ordering, but I am not sure what ordering is being mentioned there.

[ $X_i$ is $1$ if i-th red ball is picked before any black ball]


ii) Why is the probability of picking the $i$'th red ball $\mathbb{P}\{X_i=1\}= 1/(m+1) $

iii) Can we pick the $i$-th ball before picking $(i-1)$ th ball ?

If that's true then, if i-th ball is removed then should that not imply that, all the other i-1 balls before it have already been removed ?

In that case, should the probability, $\mathbb{P}\{Xi=1\}$, not be the following?


Since we are picking one red ball from the urn and not returning it? And, if we pick the $i$-th ball then, have the $1$ st to $(i-1)$th balls are already been removed from the urn?

  • $\begingroup$ i) Whether the particular $i$-th red ball is before all the black ball depends solely on their relative orders of these $m+1$ balls. The orders of other red balls will not affect them - you can freely insert them into the $m+1$ balls without affecting the value of $X_i$. ii) Each of the ball is equally likely to be the first one to be picked. iii) Again since all other reds ball are irrelevant (nuisance to be considered) so it is not the main point. $\endgroup$ – BGM Jun 19 '16 at 16:29

Let $R$ be any one of the red balls, and imagine that we temporarily paint $R$ black, so that there are $n-1$ red balls and $m+1$ black balls in the urn. What is the probability that $R$ is the first black ball picked? There are $(m+1)!$ equally likely different orders in which the $m+1$ black balls can be picked, and $R$ is the first ball in $m!$ of those orders, so the probability that $R$ is the first black ball picked is $\frac{m!}{(m+1)!}=\frac1{m+1}$. Note that it doesn’t matter in what order or exactly when in the process the $n-1$ red balls are picked: at the moment we’re interested only in the order in which the $m+1$ black balls are picked.

Now just pretend that we temporarily repaint $R$ black: the same argument shows that the probability that $R$ is drawn before any of the $m$ black balls is $\frac1{m+1}$. The point is that this depends only on the order in which these $m+1$ balls are picked, not on anything that happens to the other $n-1$ red balls, and each of these $m+1$ balls is equally likely to be picked first.

Now label the $n$ red balls $R_1$ through $R_n$.

This labelling has nothing to do with the order in which the red balls are picked; it’s just a way to give each of them a convenient name. We could name them George, Emily, Sa‘id, Hedwig, Bergþóra, and so on, and it wouldn’t change the argument at all — except to make it very, very hard to talk about the names systematically.

For $k=1,\ldots,n$ let

$$X_k=\begin{cases} 1,&\text{if }R_k\text{ is chosen before all of the black balls}\\ 0,&\text{if at least one black ball is chosen before }R_k\;. \end{cases}$$

We’ve just seen that $\Bbb P[X_k=1]=\frac1{m+1}$ for each $k=1,\ldots,n$, and of course it follows that $\Bbb E[X_k]=\frac1{m+1}$ for each $k=1,\ldots,n$ and hence by linearity of expectation that

$$\Bbb[X]=\sum_{k=1}^n\Bbb E[X_k]=\frac{n}{m+1}\;,$$

where $X=\sum_{k=1}^nX_k$, the number of red balls drawn before the first black ball is drawn.

  • $\begingroup$ Thank you, that cleared my confusions! $\endgroup$ – Skynet094 Jun 20 '16 at 3:06
  • $\begingroup$ @Salman: You're welcome; glad it helped! $\endgroup$ – Brian M. Scott Jun 20 '16 at 3:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.