Expectancy and Variance of getting different-colored pairs of marbles from two urns

Question

I have two urns, each containing $N$ marbles. Urn $A$ has $K_A$ blue marbles and the rest are red, while Urn $B$ has $K_B$ blue marbles and the remaining marbles are red.

I then sample pairs of marbles, one from each urn, without replacement. If I repeat this $k \leq N$ times, on average how many pairs of marbles will have mismatched colours? What is the variance of this random variable?

---

My first attempt

Let $X$ be the random variable denoting the number of pairs of marbles with mismatched marbles. $$E[X] = \sum_{i=1}^{k}i\cdot P(X=i)$$ where $$P(X=i) = \frac{\# \text{ microstates with exactly $i$ mismatches}}{\# \text{ all possible microstates}}\,.$$ For the denominator, we may enumerate all possible combinations as in the hypergeometric distribution and use Vandermonde's identity to simplify: $$ \sum_{l} \ {K_A \choose l}{N-K_A \choose k-l}\sum_{m} {K_B \choose m}{N-K_B \choose k-m} = {N \choose k}^2\,.$$

Though it remains to find a similar combinatoric expression for the numerator...

My second attempt

Let $I_i$ be an indicator variable denoting occurrence of a mismatch in the $i^{th}$ pair of marbles. Note that $X = \sum_{i=1}^{k} I_i$. Invoking linearity of expectation: $$ E[X] = E[\sum_{i=1}^{k} I_i] = \sum_{i=1}^{k} E[I_i] $$ Since $E[I_i] = P(I_i = 1)$,

$$ \begin{align} E[X] &= \sum_{i=1}^{k} P(I_i = 1) = \sum_{i=1}^{k}\sum_{\mathbf{I} \in \{0,1\}^{i-1}} P(I_i = 1\;|\;\mathbf{I}) \\ &= \sum_{i=1}^{k}\sum_{\mathbf{I} \in \{0,1\}^{i-1}} P(I_i = 1\;|\;I_{i-1} \land I_{i-2} \dots \land I_{1})P(I_{i-1} \;|\;I_{i-2} \land I_{i-3} \dots \land I_{1})\cdots P(I_1 ) \end{align}$$

This method requires calculating exponentially many conditional probabilities unless there is some recursive relationship (which I'm struggling to derive):

$$ \begin{align}P(I_1 = 1) &= \frac{K_A}{N}(1-\frac{K_B}{N}) + \frac{K_B}{N}(1-\frac{K_A}{N}) = \frac{K_A}{N}+\frac{K_B}{N}-2\frac{K_A}{N}\frac{K_B}{N}\\ \\ P(I_1 = 0) &= 1 - P(I_1 = 1)\\ \\ P(I_2 = 1\;|\;I_1 = 0) &=\;?\end{align}$$

CORRECTION

It seems that $$E[X] = \sum_{i=1}^{k} E[I_i] = k\cdot E[I_1] = k\cdot P(I_1 = 1)$$ But it is not clear to me why it can be argued from symmetry that $E[I_i] = E[I_1]$?

Answer 1

Terminology:

• There are $N$ marbles in each urn.

• The first urn has $B_1$ blue marbles, and $N-B_1$ red marbles.

• The second urn has $B_2$ blue marbles, and $N-B_2$ red marbles.

• As you did, for each $i\in \{1,\dots,k\}$, we let $I_i$ be an indicator random variables which is $1$ if the $i^\text{th}$ pair is mismatched, and zero otherwise.

---

In your post, you correctly deduced that $E[I_1]=P(I_1=1)=[B_1(N-B_2)+B_2(N-B_1)]/N^2$. It turns out that for all $i$, $E[I_i]=E[I_1]$; let me give two explanations why this is true.

Explanation 1

Let $E_i$ be the event that the $i^\text{th}$ marble drawn from the first urn is blue. We will show that $P(E_i)=B_1/N$.

To compute $P(E_i)$, we use the formula probability = (# favorable outcomes)/(# total outcomes).

Our probability space consists of sequences of $k$ distinct marbles, representing the entire sequence of draws from the first urn. The size of the probability space is $$ N\times (N-1)\times \dots\times (N-k+1)=\frac{N!}{(N-k)!}, $$ because there are $N$ possible marbles that can be chosen first, there are $N-1$ that can be chosen second, and so on. We now count the number of favorable outcomes. We need the $i^\text{th}$ marble to be blue, so there are $B_1$ choices for the marble the the $i^\text{th}$ slot. There are then $k-1$ remaining slots to fill, with $N-1$ choices for the next slot, then $N-2$, and so on. Therefore, the number of favorable sequences is $$ B_1\times (N-1)\times (N-2)\times \dots \times (N-k+1)=B_1\times \frac{(N-1)!}{(N-k)!} $$ Dividing these two counts, we conclude that $$ P(E_i)=\frac{B_1\times (N-1)!}{N!}=\frac{B_1}{N} $$ Therefore, each marble has a probability of $B_1/N$ of being blue, just like the first marble. This proves that the probability of $\{I_i=1\}$ is exactly the same as that of $\{I_1=1\}$.

Explanation 2

Instead of drawing the marbles one at a time, imagine we reached in and took a scoop of $k$ marbles all at once, and then put them in a random order. I claim that this is the exact same process as the original problem. Indeed, the first marble is equally likely to be any marble in the urn. Conditional on the first marble, the second marble is equally likely to be any remaining marble, and so on.

However, the symmetry of this process shows that each spot behaves the same way; there is nothing special about the first spot, each spot receives a random marble from the urn. Therefore, $P(I_1=1)=P(I_i=1)$, for each $i$.

---

Computing the variance

The following general method allows you to compute the variance of a random variable which has been written as a sum of indicator random variables. We use the formula $$ \text{Var }X=E[X^2]-(E[X])^2 $$ You already know what $E[X]$ is, so all the remains is to compute $E[X^2]$. Since $X=I_1+\dots+I_k$, we have $$ E[X^2]=E[(I_1+\dots+I_k)^2] =E\left[\sum_{i=1}^k\sum_{j=1}^k I_iI_j\right] =\sum_{i=1}^k\sum_{j=1}^k E[I_iI_j]\\ =\sum_{i=1}^k\sum_{j=1}^k P(I_i=1\text{ and }I_j=1) $$ The equation $(I_1+\dots+I_k)^2=\sum_{i=1}^k\sum_{j=1}^k I_iI_j$ comes from expanding the square using the distributive property. For example, when $k=3$, $(I_1+I_2+I_3)^2=I_1I_1+I_1I_2+I_1I_3+I_2I_1+I_2I_2+I_2I_3+I_3I_1+I_3I_2+I_3I_3$.

To evaluate $P(I_i=1\text{ and }I_j=1)$, proceed in two cases. If $i=j$, then this event is exactly the same as $P(I_i=1)$, which we already found before. If $i\neq j$, then you need to find the probability of a mismatch occurring at both positions numbered $i$ and $j$. There are four ways this can happen, depending on whether the mismatch at $i$ is red-blue or blue-red, and whether the mismatch at $j$ is red-blue or blue-red.

For the case with a red-blue mismatch at $i$ and a red-blue mismatch at $j$, the probability is $$ \underbrace{\frac{N-B_1}{N}} _{\substack{\text{probability $i^{th}$ ball} \\\text{from first urn red}}}\times \underbrace{\frac{B_2}{N}} _{\substack{\text{probability $i^{th}$ ball} \\\text{from second urn blue}}}\times \underbrace{\frac{N-B_2-1}{N-1}} _{\substack{\text{conditional probability $j^{th}$ ball} \\\text{from first urn red}}}\times \underbrace{\frac{B_2-1}{N-1}} _{\substack{\text{conditional probability $j^{th}$ ball} \\\text{from second urn blue}}} $$ I leave the three other cases to you. They are all analogous to the case I illustrated.

Answer 2

Imagine the marbles from each urn laid out randomly in two rows

Consider first blue marbles matching

Let $X(i)$ be an indicator r.v. = 1 if the $i(th)$ column is matched, and $0$ otherwise.

$P(X(i) = \dfrac{K_A}{N}\dfrac{K_B}{N} = \dfrac{K_A\cdot K_B}{N^2}$

The expectation of an indicator variable is just the probability of the event it indicates,
thus $E[X(i) = \dfrac{K_A\cdot K_B}{N^2}$

and by linearity of expectation which operates even when the random variables are not independent, $E[X] = k\dfrac{K_A\cdot K_B}{N^2} = B\;$ say

Work out similarly for red marbles $ = R$ say

Then, finally, P(mismatches) = $\dfrac{N- B - R}{N}$