# sample all pairs without repeats

Assuming I have a very large number of $$K$$ colored balls and we know the fraction of each color. If we randomly sample all pairs so that all pairs have two balls of different colors then what is the fraction of pairs with a given color combinations?

For example if there are 3 colors with fractions, $$f_{blue}=0.5$$, $$f_{red}=0.25$$ and $$f_{green}=0.25$$ then if you sample all pairs of balls such that each pairs consists of two different colors. Then I would expect that $$50\%$$ of pairs will be $$(blue/red)$$, $$50\%$$ will be $$(blue/green)$$ and $$0\%$$ $$(red/green)$$ (if 50% is blue then there must be a blue in each pair). This scenario is easy since there is only one way to sample all unordered pairs.

If more than $$50\%$$ of balls have the same color there will be no solution and if $$50\%$$ of balls are a certain color there is only one way to sample all balls (unordered) as above.

If the fraction of 3 colors are then same $$f_{blue}=1/3$$, $$f_{red}=1/3$$ and $$f_{green}=1/3$$ then by symmetry I would expect the fraction of pairs to be $$1/3$$ $$(blue/red)$$, $$1/3$$ $$(blue/green)$$ and $$1/3$$ $$(red/green)$$ if they where randomly sampled.

Is there a general way to calculate the expected fraction of colored pairs given you know the fraction of each of the $$K$$ colors?

Edit/update Ertxiem gave the solution in the case of K=3 where you do not use the assumption of randomly drawing all pairs (pairs of different colors without replacement).

Here is what I have tried so far. Let $$f=(f_1,f_2,\ldots,f_K)$$ be the fraction of each colored ball assuming K colors.

For the case of K=3 then we can calculate the fraction of pairs of ball by solving the following $$Ax=f$$ where $$A= \left( \begin{array}{ccc} 0.5 & 0.5 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 0.5 &0.5 \end{array} \right)$$, $$f= \left( \begin{array}{c} f_1\\ f_2 \\ f_3 \end{array} \right)$$, $$x= \left( \begin{array}{c} \pi_{12}\\ \pi_{13} \\ \pi_{23} \end{array}\right)$$ where $$\pi_{ij}$$is the probability of a pair of color $$i$$ and $$j$$.

This gives the solution for $$K=3$$. For $$K>3$$ we cannot use the same approach because there will be multiple solutions for example for $$K=4$$. Solving $$Ax=f$$ where $$A= \left( \begin{array}{cccccc} 0.5 & 0.5 & 0.5 & 0 & 0 & 0 \\ 0.5 & 0 & 0 &0.5 &0.5 &0 \\ 0 & 0.5 &0 & 0.5 & 0 & 0.5 \\ 0 & 0 &0.5 & 0& 0.5& 0.5 \end{array} \right)$$, $$f= \left( \begin{array}{c} f_1\\ f_2 \\ f_3 \\ f_4 \end{array} \right)$$ and $$x= \left( \begin{array}{c} \pi_{12}\\ \pi_{13} \\ \pi_{14} \\ \pi_{23} \\ \pi_{24} \\ \pi_{34}\end{array}\right)$$ gives multiple multiple solutions. Is there a way to solve it by assuming the color combinations are independent given that they are different?

update with example and simulations For the $$K=4$$ case then I have tried to solve $$Ax=f$$ for $$x$$ using Moore-Penrose generalized inverse (pseudoinverse using least squared solution) however, this does not give the same results as simulations (rejection sampling using $$5e7$$ balls). For the case of $$f=(3/8,1/8,2/8,2/8)$$ I get the following results

$$\begin{array}{c|c|c} \hat{\pi} & pseudo inverse & simulations\\ \pi_{12} & 4/24 & 31/236\\ \pi_{13} & 7/24 & 73/236\\ \pi_{14} & 7/24 & 73/236\\ \pi_{23} & 1/24 & 14/236\\ \pi_{24} & 1/24 & 14/236\\ \pi_{34} & 4/24 & 31/236 \end{array}$$. So I am still not able to find a analytical solution (for K>3).

Suppose you have $$K$$ colours of balls with respective numbers $$n_1,...,n_K$$, with a total of $$n = \sum n_i$$ balls. Let $$\mathscr{S}$$ denote the set of all pairs of distinct balls and let $$\mathscr{C}$$ denote the set of all pairs of distinct balls of the same colour. Since $$\mathscr{C} \subset \mathscr{S}$$ the number of ways you can sample two balls of different colours is:

\begin{aligned} |\mathscr{S} - \mathscr{C}| = |\mathscr{S}| - |\mathscr{C}| &= {n \choose 2} - \sum_{k=1}^K {n_k \choose 2} \\[6pt] &= \frac{n(n-1)}{2} - \sum_{k=1}^K \frac{n_k (n_k-1)}{2} \\[6pt] &= \frac{1}{2} \Big[ n(n-1) - \sum_{k=1}^K n_k (n_k-1) \Big] \\[6pt] &= \frac{1}{2} \Big[ (n-1) \sum_{k=1}^K n_k - \sum_{k=1}^K n_k (n_k-1) \Big] \\[6pt] &= \frac{1}{2} \sum_{k=1}^K n (n-n_k). \\[6pt] \end{aligned}

Let $$\mathscr{M}_{a,b}$$ denote the set of all pairs of distinct balls with colours $$a \neq b$$. The number of ways you can sample two balls with a given (different) colour combination is:

$$|\mathscr{M}_{a,b}| = \frac{n_a n_b}{2}$$

Hence, the fraction of sample-pairs of different colours that are of the specified colour pair $$a \neq b$$ is:

$$P_n(a,b) = \frac{|\mathscr{M}_{a,b}|}{|\mathscr{S} - \mathscr{C}|} = \frac{n_a n_b}{\sum_{k=1}^K n_k (n-n_k)}.$$

Taking $$n \rightarrow \infty$$ and letting $$p_1,...,p_K$$ be the respective limiting sample proportions of the balls of each colour, you have:

$$P_\infty(a,b) = \lim_{n \rightarrow \infty} \frac{|\mathscr{M}_{a,b}|}{|\mathscr{S} - \mathscr{C}|} = \frac{p_a p_b}{\sum_{k=1}^K p_k (1-p_k)}.$$

Application to your problem: In your example you have $$K=3$$ colours with proportions $$\mathbf{p} = (\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{4})$$ for the respective colours $$\text{Blue}, \text{Red}, \text{Green}$$. This gives:

$$P_\infty(a,b) = \frac{p_a p_b}{\tfrac{1}{2} \cdot \tfrac{1}{2} + \tfrac{1}{4} \cdot \tfrac{3}{4} + \tfrac{1}{4} \cdot \tfrac{3}{4}} = \frac{p_a p_b}{5/8} = \tfrac{8}{5} \cdot p_a p_b.$$

So you have:

\begin{aligned} P_\infty(\text{Blue}, \text{Red}) &= \tfrac{8}{5} \cdot \tfrac{1}{2} \cdot \tfrac{1}{4} = \tfrac{1}{5}, \\[6pt] P_\infty(\text{Blue}, \text{Green}) &= \tfrac{8}{5} \cdot \tfrac{1}{2} \cdot \tfrac{1}{4} = \tfrac{1}{5}, \\[6pt] P_\infty(\text{Red}, \text{Green}) &= \tfrac{8}{5} \cdot \tfrac{1}{4} \cdot \tfrac{1}{4} = \tfrac{1}{10}. \\[6pt] \end{aligned}

• Thanks for suggestions. I will have a look at it right away Apr 15, 2019 at 10:46
• As far as I can tell your solution works assuming we sample pairs with replacement and is the same as Ertxiem old solution. For the ${\bf p}=(1/2,1/4,1/4)$ then the correct solution should be $P(Blue,Red)=1/2$, $P(Blue,Green)=1/2$ and $P(Red,Green)=0$ since if we sample all pairs then there must be a Blue in each pair in order for all pairs to contain different colors Apr 15, 2019 at 11:21

Let $$r$$, $$g$$ and $$b$$ be the number of red (R), green (G) and blue (B) coloured balls, with $$r+g+b=K$$, where $$K$$ is the total number of balls (note that this notation is different from notation in the old answer). $$K$$ must be an even number (otherwise it would be impossible to every ball to have their pair, so we can write $$K = 2k$$.

Assume, for simplicity, that $$0 < r \leq g \leq b < k$$. So, I've excluded the trivial cases as you already solved them.

In this setting, we must have $$l = k - b > 0$$ pairs of one red and one green ball. The other $$b$$ pairs will be made by $$m = g - l$$ blue and green balls, and by $$n = r - l$$ blue and red balls.

If it happens that $$l \geq r$$, we can't make the pairing for that distribution of the number of balls (and it's game over :) ).

So, assuming that $$l \geq 0$$, $$m \geq 0$$ and $$n \geq 0$$, that is, this distribution is possible, then the probability of getting each pair is simply given by: $$P(BG) = \frac{m}{k} \\ P(BR) = \frac{n}{k} \\ P(GR) = \frac{l}{k}$$

Note that $$l + m + n \\ = l + (g - l) + (r - l) \\ = g + r - l \\ = g + r + b - k \\ = 2k - k \\ = k$$

Old answer for reference: (Note that notation here is different from notation in the new answer above.)

I'm not able to solve the case without replacement, as you intended. However, what I've written is too big to be in a comment. I hope it is useful for you to search for a solution.

I can approach the case with replacement using conditional probability.

Let $$r$$, $$g$$ and $$b$$ be the fraction of red (R), green (G) and blue (B) coloured balls, with $$r+g+b=1$$. Assume, for simplicity, that $$0 < r \leq g \leq b < 1/2$$. So, I've excluded the trivial cases as you already solved them.

If the pairing was totally random, we could have a pair of balls of the same colour with probability: $$P_{eq} = P(RR) + P(GG) + P(BB) = r^2 + g^2 + b^2$$

And the case with different colours is just the complementary probability: $$P_{dif} = 1 - P_{eq}$$

So, the probability of getting a pair of different colours, say, red and green, when we exclude the equal coloured cases can be computed with the conditional probability: $$P(RG | dif) = \frac{P(RG \cap dip)}{P_dif} = \frac{2rg}{1-r^2 - g^2 - b^2}$$ the factor $$2$$ appears because the red ball can be the first or the second one.

• Thanks for taking the time to help me out. When trying the with replacement approach it gives me problems when all 3 fractions are not the same. E.g. in my first example where $b=0.5$ and $r=g=0.25$ then $P(RG|dif)=\frac{2\times 0.25\times 025}{1-0.5^2-0.25^2-0.25^2}=0.2$ instead of 0. Apr 14, 2019 at 14:43
• Yes, I'm aware that my answer is imperfect because it accounts for the case with replacement, which is different from what you intended. I'll try to think on another solution and add something later if I come up with something useful. Apr 14, 2019 at 17:04
• I think I was able to solve it, can you please check if the new answer is correct? Apr 14, 2019 at 17:34
• I think it works :-). Im just going to test it out some more and see if I can generalize it to more colors. Apr 15, 2019 at 8:40
• For more colours you will have another degree of freedom and you may have multiple solutions for the distribution, so you might not have a formula like in the case of 3 solutions. Apr 15, 2019 at 8:59