2
$\begingroup$

We have an urn containing $n_a$ tiles labelled "A", $n_b$ ones labelled "B", and $n_c$ tiles labelled "C". We also have a string of letters consisting of $s_a$ occurrences of the letter "A", $s_b$ occurrences of the letter "B" and $s_c$ occurrences of the letter "C". If I draw $j$ tiles at random from the urn, what is the probability that I will be able to match exactly $k$ of them with letters from our string? Also what's the probability that I will be able to match at least $k$ of them with letters from our string?

Edit: When I say "match", I mean that if 3 "A" tiles and 2 "B" tiles are drawn from the urn, and the string contains 1 "A" and 3 "B"s, then I will have matched 1 "A" and 2 "B"s, i.e. I will have matched 3 (=1+2) tiles.

$\endgroup$
  • $\begingroup$ I need the solution for a project. I've been 16 years out of University and have forgotten how to deal with this. I'm curious first of all whether it's possible to find a solution that is relatively fast to compute on a computer. Also I would be grateful for a few pointers that could point me towards the solution, if one is too tired to write it out explicitly. $\endgroup$ – alex k Jul 14 '14 at 23:32
  • 1
    $\begingroup$ Would you specify what 'match exactly $k$ of them with letters from our string' mean? Suppose we have $a+b+c=j$ where $a$ things of type $A$, $b$ things of type $B$ and $c$ things of type $C$. Then, is $k=a\cdot s_a+b\cdot s_b+c\cdot s_c$ ? $\endgroup$ – talegari Jul 15 '14 at 5:47
  • $\begingroup$ I'm not sure I understand the question. Could you explain what you mean? $\endgroup$ – Oria Gruber Jul 15 '14 at 6:07
  • 1
    $\begingroup$ @talegari I edited my question to explain what I mean by "match". In your example, k = min(a, $s_a$) + min(b, $s_b$) + min(c, $s_c$) $\endgroup$ – alex k Jul 15 '14 at 10:18
  • $\begingroup$ I think there is no other way than listing the combinations for the condition and applying the formula for hypergeometric distribution. $\endgroup$ – gar Jul 15 '14 at 17:12
0
$\begingroup$

Here is an outline -- we count the number of possibilities of getting exactly $k$ matches. Suppose we choose $0\le m_a\le n_a$ of type A, $0\le m_b\le n_b$ of type B and $0 \le m_c \le n_c$ of type C where $m_a+m_b+m_c=j$. We say "A overflows" if $m_a>s_a$. We break into four cases:

  • None of A, B, C overflow

This is true only if $j=k$. This is given by the coefficient of $x^j$ in the expression $(1+x+\dots +x^{s_a})(1+x+\dots +x^{s_b})(1+x+\dots +x^{s_c})$

  • Exactly one them overflows.

Lets suppose that A overflows. If $n_a-s_a\ge j-k$, the coefficient of $x^{k-s_a}$ in the expression $(1+x+\dots +x^{s_b})(1+x+\dots +x^{s_c})$ counts it. We can find similar expressions for B and C.

  • Exactly two of them overflow.

Lets suppose that A and B overflow. If $(n_a-s_a)+(n_b-s_b)\ge j-k$ and $0\le k-(s_a+s_b)\le s_c$, we look at the coefficient of $x^{j-k}$ in $(1+x+\dots +x^{n_a-s_a})(1+x+\dots +x^{n_b-s_b})$. We can find similar expressions when A does not overflow and B does not overflow.

  • All of them overflow.

Then, $k\ge (s_a+1)+(s_b+1)+(s_c+1)$. This is given by the coefficient of $x^{j-k}$ in $(1+x+\dots +x^{n_a-s_a})(1+x+\dots +x^{n_b-s_b})(1+x+\dots +x^{n_c-s_c})$

$\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.