4
$\begingroup$

Suppose we have a deck of 40 cards which has, 5 Aces, 6 Kings, 9 Queens, 20 Jacks. A game is played where a contestant will continuously draw cards until they have 5 matching cards (not necessarily in order). The cards are drawn without replacement.

I'm trying to find the probability of the contestant getting the five matching cards they get are all Aces (i.e. they have to get this before they get any other five matching cards).

Does anyone have any idea on how to approach this?

$\endgroup$
8
$\begingroup$

Suppose a win occurs when the fifth ace is drawn on draw $r+1$, for $0 \le r \le 16$. On the previous draw, the hand must have contained four aces and no more than four of any of the other ranks, and then the contestant must draw an ace on draw $r+1$.

Let's try to find the probability of being in a favorable state on draw $r$. There are $\binom{40}{r}$ possible hands of $r$ cards, all of which we assume are equally likely. We would like to count the number of hands containing exactly four aces and no more than four of any other rank, which we will call a "favorable hand". To do this, we will find the generating function of the number of favorable hands. Numbering the ranks from ace to jack as $1$ through $4$, let's say $n_i$ is the initial number of cards in the deck of rank $i$, for $i=1,2,3,4$, so $n_1 = 5$, $n_2=6$, etc. If we consider only cards of rank $i$, then the generating function for the number of hands containing zero to four of those cards is $$\sum_{j=0}^4 \binom{n_i}{j} x^j$$ The generating function for the number of ways to draw exactly four aces is simply $\binom{5}{4}x^4$; so the generating function for the number of favorable hands containing cards of all ranks is $$f(x) = \binom{5}{4}x^4 \prod_{i=2}^4 \sum_{j=0}^4 \binom{n_i}{j} x^j$$ I.e., the coefficient of $x^r$ when $f(x)$ is expanded, which which we will denote by $[x^r]f(x)$, is the number of hands containing exactly four aces and no more than four of any other rank. After some computation (I used Mathematica, but a pencil and paper computation should not be difficult), $$f(x) = 5 x^4+175 x^5+2975 x^6+32725 x^7+261800 x^8+ \\ 1544980 x^9+6741525 x^{10}+21960225 x^{11}+53723775 x^{12}+ \\ 96756975 x^{13}+122906250 x^{14} +102343500 x^{15}+45785250 x^{16}$$

The probability of a favorable hand of $r$ cards is then $$\frac{[x^r]f(x)}{\binom{40}{r}}$$ In order to win on draw $r+1$ the player must have a favorable hand on draw $r$ and then draw an ace on draw $r+1$, when there is one ace left in the deck and $40-r$ cards total. So the probability of a win on draw $r+1$ is $$\frac{[x^r]f(x)}{\binom{40}{r}} \cdot \frac{1}{40-r}$$ and the overall probability of winning is $$\sum_{r=0}^{16} \frac{[x^r]f(x)}{\binom{40}{r}} \cdot \frac{1}{40-r} = \boxed{0.00194347}$$ Edit (deleted)

Edit to the Edit

Prompted by one of the comments, I provided a list of learning resources for people who are new to generating functions and would like to learn about them. I have moved that list to a new question and answer here because it seems more suitable for development as a community resource. Please take a look.

$\endgroup$
  • $\begingroup$ @user What do you mean by $p_1$? $\endgroup$ – awkward Mar 8 at 18:20
  • $\begingroup$ @user Oh I see, you mean $p_i$ is the probability that rank $i$ is the first rank to get 5 cards. I haven't computed those other probabilities, but the probability I computed for aces is consistent with Monte Carlo results, so I'm pretty sure it's correct. If you see something wrong with the solution, please be specific. $\endgroup$ – awkward Mar 8 at 19:59
  • $\begingroup$ @user OK, what are your numbers? $\endgroup$ – awkward Mar 8 at 20:04
  • $\begingroup$ @awkward my monte carlo simulation comes up with the same answer as you awkward. Do you have any material to read about generating functions as I have not come across them before? $\endgroup$ – DH. Mar 8 at 20:12
  • $\begingroup$ @DH. I would recommend actuarial course notes (if you can get your hands on them) great source for material on generating functions! $\endgroup$ – The Problem Mar 8 at 20:14
0
$\begingroup$

Since I didn't quite understand some of the details of awkward's answer, I computed the probabilities by modelling the process as an inhomogeneous Markov chain with the $5$ absorbing states: $5$ aces first, $5$ kings first, $5$ queens first and $5$ jacks first, and $5^4$ non-absorbing states: $\ j_1\ \mathrm{aces,}$ $j_2\ \mathrm{kings,}$ $j_3\ \mathrm{queens,}$ and $j4\ \mathrm{jacks}$, for $\ j_i\in \{0,1,2,3,4\}$. I got exactly the same numbers he did for aces and jacks to be the first to five. The probabilities for all four cards being first to five were: \begin{eqnarray} \mathrm{aces} &:& 0.00194347\\ \mathrm{kings} &:& 0.00824479\\ \mathrm{queens} &:& 0.07001983\\ \mathrm{jacks} &:& 0.91979191 \end{eqnarray}

Details of the Markov chain

Let $\ T_{t,c}\ $ be the probability that the process has terminated by step $\ t\ $ with $\ 5\ $ of card $\ c\ $, $\ t=0,1,\dots,17\ $, and $\ c=1,2,3,4\ $ indicating ace, king, queen and jack respectively. Since $\ 17\ $ cards will have been drawn after step $\ 17\ $, there must be $\ 5\ $ cards of one of the denominations, so $\ \sum_{c=1}^4 T_{17,c}=1\ $, and $\ T_{17,1}\ $ is the probability that that denomination is the ace.

Let $\ P_t\left(j_1,j_2,j_3,j_4\right)\ $ be the probability that after step $\ t\ $ there are $\ j_1\ $ aces, $\ j_2\ $ kings, $\ j_3\ $ queens and $\ j_4\ $ jacks in the hand drawn. For convenience in the the following description, extend the domain of definition of $\ P_t\left(j_1,j_2,j_3,j_4\right)\ $ to include quadruples $\ j_1, j_2, j_3, j_3\ $ of which any member, or combination of mmbers, can take the value $\ -1\ $, by putting $\ P_t\left(j_1,j_2,j_3,j_4\right)= 0\ $ whenever that is the case.

Initially, we have $\ T_{0,c} = 0\ $ for all $\ c\ $, $\ P_0\left(0,0,0,0\right)=1\ $, and $\ P_0\left(j_1,j_2,j_3,j_4\right)=0\ $ if any $\ j_i\ne 0\ $, and \begin{eqnarray} P_{t+1}\left(j_1,j_2,j_3,j_4\right) = \frac{6-j_1}{40-t} &P_t&\left(j_1-1,j_2,j_3,j_4\right)+\frac{7-j_2}{40-t}P_t\left(j_1,j_2-1,j_3,j_4\right)\\ &+&\frac{10-j_3}{40-t} P_t\left(j_1,j_2,j_3-1,j_4\right)+\frac{21-j_4}{40-t} P_t\left(j_1,j_2,j_3,j_4-1\right)\ , \end{eqnarray} \begin{eqnarray} T_{t+1,1} &=& T_{t,1}+\left(t-40\right)^{-1}\sum_{j_2=0}^{\mathrm{min}(4,t-4)}\sum_{j_3=0}^{\mathrm{min}(4,t-j_2-4)}P_t\left(4,j_2,j_3,t-j_3-j_2-4\right)\\ T_{t+1,2} &=& T_{t,2}+\frac{2}{t-40}\sum_{j_1=0}^{\mathrm{min}(4,t-4)}\sum_{j_3=0}^{\mathrm{min}(4,t-j_1-4)}P_t\left(j_1,4,j_3,t-j_3-j_1-4\right)\\ T_{t+1,3} &=& T_{t,3}+\frac{5}{t-40}\sum_{j_1=0}^{\mathrm{min}(4,t-4)}\sum_{j_2=0}^{\mathrm{min}(4,t-j_1-4)}P_t\left(j_1,j_2,4,t-j_2-j_1-4\right)\\ T_{t+1,4} &=& T_{t,4}+\frac{16}{t-40}\sum_{j_1=0}^{\mathrm{min}(4,t-4)}\sum_{j_2=0}^{\mathrm{min}(4,t-j_1-4)}P_t\left(j_1,j_2,t-j_2-j_1-4,4\right) \end{eqnarray}

$\endgroup$
  • $\begingroup$ DO you have details of the modelling you done so I can replicate it? $\endgroup$ – DH. Mar 11 at 9:18

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.