Combinatorics: probability of drawing only pairs of same colors from two boxes

55 Views Asked by At

There are two boxes $B_1,B_2$; $B_1$ contains $n$ white balls, and $B_2$ contains $n$ black balls.

There are $2n-2$ rounds. At each round $1\leq i\leq n$, two balls are drawn randomly, uniformly among all the remaining balls. If the pair of balls is of same color (i.e. either $\langle$white,white$\rangle$ or $\langle$black,black$\rangle$), we place back one of the two picked balls into the corresponding box. If the colors are different, we stop the experiment.

Intuitively, it makes sense that the probability of successfully finishing the $2n-2$ rounds (i.e., the probability that each one of the $2n-2$ pairs drawn is of same color) is about $(\tfrac12)^{2n-2}$, since at each round the probability of drawing a pair of same color is roughly $\tfrac12$.

Nonetheless, I struggle to find a rigorous argument to prove this, since at each round the probability of drawing a pair of same color depends on the previous rounds in a non-trivial way. Any help would be greatly appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

Label each of the balls so they are all distinct. Further, let us draw balls one after the other rather than two at the same time. As a final simplification, even if we were to have "lost" and had non-matching colors pulled, let us go ahead and continue pulling anyways.

Without loss of generality, when we pick two and are asked to put one back... let us always put back the smaller labeled number of the two (ties go to black).

Recognize that there are $\frac{(2n)!(2n-1)!}{2}$ orders in which we can draw the balls and these orders are all equally likely. Of these, we count how many ways there are to have successfully at each round pulled two balls of the same color. To explain this in more detail, we begin by picking one of the $2n$ balls and then one of the $2n-1$ balls in the first round. After putting one back, in the second round we now pick one of the $2n-1$ remaining balls and then one of the $2n-2$ remaining balls after that. Repeating this for the $2n-2$ total rounds and rearranging this would be $(2n)\cdot (2n-1)\cdot (2n-2)\cdots 3$ corresponding to the first selections of the rounds and $(2n-1)(2n-2)\cdots 2$ corresponding to the second selections of each round, for a total of $2n-2$ terms in each product.

Since after each successful round, one more of the corresponding balls is removed of that color, we see that after a color has been chosen $n-1$ times there is only one left of that color and it becomes impossible to pull a pair of that color again. To have survived $2n-2$ rounds implies then that exactly half of the rounds will be where we pull a pair of whites while the other half of the rounds we pull a pair of blacks. Select which rounds will be for pulling whites in $\binom{2n-2}{n-1}$ ways.

Next, for each of those rounds designated to be where we pull two whites... pick which two whites they are, noting that each round the available list decreased by one. This gives $n(n-1)\cdot (n-1)(n-2)\cdot (n-2)(n-3)\cdots 2\cdot 1$ for a total of $n!(n-1)!$ ways to organize the whites. Similarly for the blacks.

Taking the ratio, this gives a probability of:

$$\frac{\binom{2n-2}{n-1}\cdot n!(n-1)!\cdot n!(n-1)!}{\frac{(2n)!(2n-1)!}{2}}$$

Trying to simplify this a bit:

$$\frac{2}{(2n-1)\binom{2n}{n}}$$


For sanity-checking we can brute force the calculation for the first few cases. In the case of $n=1$ we end before we even begin with a success.

In the case of $n=2$ our first selection will be whatever and our second selection must match for a probability of $\frac{1}{3}$. Without loss of generality, let our first match be white. Then, our next selection must be a black with probability $\frac{2}{3}$ and then our final selection must be black again with probability $\frac{1}{2}$ for a probability of $\frac{1}{3}\cdot\frac{2}{3}\cdot\frac{1}{2}=\frac{1}{9}$. These of course match what the proposed formula gives.

Given a bit of tedious effort, one can even check the case of $n=3$ which would yield the calculation $\frac{2}{5}\cdot\left(\frac{2}{5}\cdot\frac{1}{4}\cdot\frac{3}{4}\cdot\frac{2}{3}\cdot\frac{2}{3}\cdot\frac{1}{2} + \frac{3}{5}\cdot\frac{2}{4}\cdot \frac{1}{9}\right)=\frac{1}{50}$ as the above formula predicted. (We could cheat a bit and use $\frac{1}{9}$ in that calculation as it was already calculated for the $n=2$ case and we were back in that situation)