Given a population of $n$ black and $m$ green balls, the expected number of black balls in a random sample of $r$ balls can be calculated as follows

We define a random variable $X_k$ taking values 1 or according as the $k$-th element in the sample is black or not. Then $P(X_k = 1) = \frac{n}{n+m}$ and the expected number of black balls in a random sample of $r$ balls is $\frac{nr}{n+m}$.  This is the answer given in Feller's Book (Vol 1). The reason given by Feller is "For reasons of symmetry".

But I am not convinced by this approach. How can we assume a constant probability $P(X_k = 1) = \frac{n}{n+m}$ ?  The sampling process is without replacement and probability of success changes in every trial. I don't understand what is meant by "For reasons of symmetry".


The following seems to be a more rigorous argument.

I think you agree that $P(X_1 = 1) = \frac{n}{n+m}$.

Then \begin{align}P(X_2=1) &= P(X_2=1 \mid X_1=1)P(X_1=1) + P(X_2=1 \mid X_1=0)P(X_1=0) \\ &{= \frac{n-1}{n+m-1} \cdot \frac{n}{n+m} + \frac{n}{n+m-1} \cdot \frac{m}{n+m}} \\ &= \frac{n}{n+m}, \end{align}

if you simplify the expression on the second line. If you feel like it, you can show that $P(X_k=1) = \frac{n}{n+m}$ for all $1 \leq k \leq r$ similarly, by induction (d.k.o's answer is the induction step).


Let $S_k:=\sum_{i=1}^k X_i$. Then for $k<n$, \begin{align} \mathsf{P}(X_{k+1}=1)&=\sum_{i=0}^k\mathsf{P}(S_k=i)\mathsf{P}(X_{k+1}=1\mid S_k=i) \\ &=\sum_{i=0}^k\frac{\binom{n}{i}\binom{m}{k-i}}{\binom{n+m}{k}}\times\frac{n-i}{n+m-k} \\ &=\frac{n}{n+m}\sum_{i=0}^k\frac{\binom{n-1}{i}\binom{m}{k-i}}{\binom{n+m-1}{k}}=\frac{n}{n+m}. \end{align}


The solution stems from the linearity of expectation, which applies even if the random variables are not independent. At more length,

Let $X_k$ be an indicator random variable that is $1$ if the $k_{th}$ element is black, and $0$ if not

Now black balls (or those of any other color) have no preference for position, thus if you randomly pick up the $k_{th}$ ball,

$\Bbb P(X_k) = \Bbb P(X_1) = \frac {n}{n+m}$

Now the expectation of an indicator random variable is just the probability of the event it indicates, thus

$\Bbb E(X_k ) = \frac{n}{n+m},$

and $\Bbb E(X) = \Bbb E(X_1) + \Bbb E(X_2) + ...+\Bbb E(X_r) = \frac{rn}{n+m}$


The sequence $(X_1, \dotsb, X_r)$ is exchangeable. Indeed the joint distribution of the $X_i$ is only dependent on the number of $X_i$ that are equal to $1$.

To see this consider the case $r=3$. Then $$ P(X_1=1, X_2=0, X_3=1)=\frac{n(m)(n-1)}{(n+m)(n+m-1)(n+m-2)}=P(X_2=1, X_3=0, X_1=1). $$

by using the decomposition $P(X_1=1, X_2=0, X_3=1)=P(X_1=1)P(X_2=0\mid X_1=1)P(X_3=1\mid X_2=0, X_1=1)$ for the first equality and something similar for the scond. More simply we are considering the number of red and black balls still left after each draw and multiplying the appropriate probabilites.

In general for any binary tuple $(x_1, x_2, x_3)$ the probability $P(X_1=x_1, \dotsc, X_3=x_3)$ will be a fraction with the same denominator as above and a numerator of the form $n(n-1)\dotsb(n-a+1)\times m(m-1)\dotsb(m-u+1)$ where $a$ is the number of ones in the sequence $(x_1, \dotsc, x_3)$ and $u$ the number of zeroes. This probability is invariant to permuatations of the indices of the $X_i$. We can argue similarly in the general case for given $r\geq 0$.

In particular, this means that all the marginal distributions of the $X_i$ are equal to one another. For example $$ P(X_2=1)=\sum P(X_2=1, X_1=a_1, \dotsc, X_r=a_r)=\sum P(X_1=1, X_2=a_1, \dotsc, X_r=a_r)=P(X_1=1) $$ where in the second equality we use exchangeability, interchanging the indices of $X_1$ and $X_2$ and fixing all other indices. But of course $$ P(X_1=1)=\frac{n}{n+m}. $$ The number of black balls drawn in the r draws $X$ is then found by linearity of expecation. Indeed $X=\sum_{i=1}^r X_i$ whence $$ EX=\sum_{i=1}^r EX_i=\sum_{i=1}^r P(X_i=1)=\frac{rn}{n+m} $$


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.