1
$\begingroup$

I think this is right, just want to double check. Let's say I have a bucket of n items. Those n items have k colors uniformly distributed. Then the probability that I get two items from the same color is:

$$ P = \frac{\binom{k}{1}\binom{n/k}{2}}{\binom{n}{2}} $$

So, for a bucket of 200 items with 10 colors, this is: $$ P = \frac{\binom{10}{1}\binom{200/10}{2}}{\binom{200}{2}} $$

And the intuition being: There's a population n where I want to choose two items (denominator). From this population there are 10 colors and I want to pick 1 (numerator). And from a particular color i want to choose 2. Since there is an equal number of colors, then I can set that up as items/colors, n/k.

Are the formulation and intuition correct?

$\endgroup$
6
  • $\begingroup$ So you choose two items and both items have the same color, right? $\endgroup$
    – callculus
    May 18 '19 at 16:45
  • $\begingroup$ Yup, both same color $\endgroup$
    – xela
    May 18 '19 at 16:51
  • $\begingroup$ I'm not sure but I think this is more correct- $$\displaystyle \dfrac{{n \choose 1}{{\frac{n}{k}-1}\choose 1}}{n \choose 2}$$ $\endgroup$ May 18 '19 at 17:02
  • $\begingroup$ ^The above expression basically says that we first choose $1$ item from $n$ items and choose the next item with the same color as the first one. Initially there are $n/k$ items of each color. After choosing the first item we're left with $\frac{n}{k}-1$ items in that particular color. I'm not entirely sure though. And when I substitute the values in the example of 200 items and 10 colors, I ended up with $\frac{38}{199}$, is this correct? $\endgroup$ May 18 '19 at 17:06
  • $\begingroup$ @ExtremeRaider Your answer is exactly twice the correct probability, because for each pair of items whose colors match, you count it twice--once when you choose one of the items first, and again when you choose the other item first. OP's method is better. $\endgroup$
    – David K
    May 18 '19 at 17:32
2
$\begingroup$

Your method is a good one if you choose exactly two items. If you chose three items and the question was whether any two were the same (so the alternative, which we don't want, is items of three different colors) then the probability would be higher. If you chose $k+1$ items the probability of a matching pair would be $1.$ That's why you get questions like, "How many items are you choosing?"

Choosing just two items from the bucket, you have (as you say) $\binom{200}{2}$ possible pairs of items that you could choose, and the assumption is that no pair is more likely to be chosen than any other pair, so all $\binom{200}{2}$ pairs are equally likely. Because of that, you just have to count the "successful" pairs and divide by the total number of possible pairs to get the probability.

Another approach is as follows. For convenience, let $m = n/k.$

You pick one item from the bucket. It has a color. Now you pick an item from the $n - 1$ items remaining in the bucket. That item is either one of the $m - 1$ remaining items of the color you already picked, or one of the $(k-1)m$ items of the other $k-1$ colors. The chance that you choose the same color twice is therefore $$ \frac{m - 1}{n - 1} = \frac{\frac nk - 1}{n - 1}.$$

If you have $200$ items, of which $20$ are in each of $10$ colors, the answer comes out to $\frac{20-1}{200-1} = \frac{19}{199}.$

Now, recalling that $$\binom xy = \frac{x!}{(x-y)! y!} = \frac{x (x-1)(x-2) \cdots (x - y + 1)}{y!},$$ in particular $\binom x1 = x$ and $\binom x2 = \frac{x(x-1)}{2},$ your approach gives us $$ \frac{\binom k1\binom{n/k}{2}}{\binom n2} = \frac{\binom k1\binom{m}{2}}{\binom n2} = \frac{k \left(\frac{m(m-1)}{2}\right)}{\left(\frac{n(n-1)}{2}\right)} = \frac{km\left(m - 1\right)}{n(n-1)} = \frac{m - 1}{n - 1} = \frac{\frac nk - 1}{n - 1}. $$ So we get the same answer either way.

$\endgroup$
1
  • $\begingroup$ awesome! thanks for helping generalize this1 $\endgroup$
    – xela
    May 18 '19 at 17:33
1
$\begingroup$

Yes, this is the right expression. We can also say that we firstly choose one item with color $k=1$. The probability is $\frac{\frac{n}{k}}{n}=\frac1k$. Then we choose the next item with color $k=1$. The probability is $\frac{\frac{n}{k}-1}{n-1}$. Since we have k colors the probability to choose two items with same colors is $\frac1k\cdot \frac{\frac{n}{k}-1}{n-1}\cdot k=\frac{\frac{n}{k}-1}{n-1}$. This term is equal to $$\frac{\binom{k}{1}\binom{n/k}{2}}{\binom{n}{2}}=\frac{\frac{k}{1}\cdot \frac{n/k\cdot (n/k-1)}{2\cdot 1} }{\frac{n\cdot (n-1)}{1\cdot 2}}=\frac{k\cdot n/k\cdot (n/k-1)}{n\cdot (n-1)}=...$$

$\endgroup$

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.