6
$\begingroup$

Suppose we have a standard, $52$-card deck that's been shuffled using a strong RNG and an unbiased shuffling algorithm. We draw one card at a time, without replacement, and stop as soon as we observe all four Aces.

Given $k$, what is the probability that we observe all four Aces before we observe four of any other rank on the $k$th card, where $k = 4, 5, \ldots, 40$?

In other words, and for example, if $k = 20$, what is the probability that the first $20$ cards contain exactly four Aces, with the fourth Ace being drawn on the $20th$ card and that the remaining sixteen cards are not four of any other rank?

For $k = 4, 5, 6, 7$ this looks to be straightforward. But for $k \geq 8$ this feels increasingly headache-y.

Thoughts on an approach

For the $k = 20$ case from above, it seems like I have to, among other things, count the number of ways to partition $16$ [the remaining cards] with $12$ objects [the remaining ranks] where each object can get no more than three of a copy and then weighting each of these partitions. For example, I could observe a partition like $3 + 3 + 3 + 3 + 3 + 1$ as permutations of KKKQQQJJJTTT9998AAAA where one of the As is always at the end. Then I would weight each partition of $16$ from $12$ by the number of permutations and number of ways of choosing similar ranks.

I can always simulate this, but for fun, I'm trying to see if there is a practical, exact approach.

EDIT 6/9/2017

I seem to have caused some confusion with my example and original wording. Here is (hopefully) better wording of what I'm after.

Fix $k$. The sample space is the set of permutations in which the fourth ace is drawn on the $k$th card. What proportion of those permutations contain only three or fewer occurrences of all other ranks in the first $k$ cards?

$\endgroup$
2
$\begingroup$

For $k=20$, say, you need the $32$ remaining cards to contain no aces, and at least one of every other rank. Let's choose those $32$ cards first. If our choice is successful, then we also need the $20$th card to be an ace; conditional on what we already know this is a $4/20=1/5$ chance, since there are $4$ aces in the first $20$ cards.

The total number of choices for the remaining $32$ cards is $\binom{52}{32}$. The number of those choices which have no aces is $\binom{48}{32}$. Now we have to subtract the number of choices with no aces which are also missing some other rank; we can do this using inclusion-exclusion.

There are $\binom{44}{32}$ combinations missing one specified other rank, $\binom{40}{32}$ combinations missing two specified other ranks, and so on. So the total number of combinations missing aces and at least one other rank is $$\binom{12}1\binom{44}{32}-\binom{12}2\binom{40}{32}+\binom{12}3\binom{36}{32}-\binom{12}4\binom{32}{32}.$$ For general $k$, keep taking terms in the pattern $(-1)^{i+1}\binom{12}i\binom{48-4i}{52-k}$, but cut off any terms where $48-4i<52-k$.

Overall, then, your probability is $$\frac{\binom{48}{32}-\binom{12}1\binom{44}{32}+\binom{12}2\binom{40}{32}-\binom{12}3\binom{36}{32}+\binom{12}4\binom{32}{32}}{\binom{52}{32}}\times\frac{4}{20}\approx 0.003.$$

$\endgroup$
2
$\begingroup$

Math Misery has clarified the question further in the comments below. It's now apparent that I misinterpreted the question. The answer I wrote addresses what I thought the question was, not what it is.

First, we say what the probability is that you'll draw your fourth ace on the $k$th card. There $\binom{52}{4}$ possible ways that the four aces could be positioned in the 52 cards, and exactly $\binom{k-1}{3}$ of them satisfy the condition. So the probability for this is $\binom{k-1}{3}\big/\binom{52}{4}$.

Now we look at the remaining 48 cards and ignore aces. The question is, what is the probability $p$ that of the 12 card values, none will appear four times in the first $k-4$ cards of 48?

If we let $A_K, A_Q, A_J, A_{10},\dots$, be the event that all four kings, queens, jacks, 10s, etc., appear in the first $k-4$ cards, then applying the inclusion-exclusion formula, we find that $$ \begin{align} p &= 1 - 12P(A_K) + \binom{12}{2}P(A_K \cap A_Q) - \binom{12}{3}P(A_K \cap A_Q \cap A_J) + \dots \\ &= \sum_{i=0}^{12} (-1)^i \binom{12}{i}\frac{\binom{48-4i}{52 - k}}{\binom{48}{52-k}}. \end{align} $$ For example, when $i = 3$, the expression $\binom{48-4i}{52 - k}\big/\binom{48}{52-k}$ represents the probability that none of the $12 = 4i$ kings, queens and jacks appear in the final $52-k$ cards of the $48$ that are left.

So the overall probability is $$ \frac{\binom{k-1}{3}}{\binom{52}{4}}\sum_{i=0}^{12} (-1)^i \binom{12}{i}\frac{\binom{48-4i}{52 - k}}{\binom{48}{52-k}}. $$

$\endgroup$
  • $\begingroup$ I obtain almost exactly the same formula but with a different scalar. Note that with $4\le k\le 7$ and four aces we only have at most three cards left which means the probability of the aces being the first set is one. Your formula returns ${\frac {1}{270725}},{\frac {4}{270725}},{\frac {2}{54145}},{\frac {4}{54145}}$ instead. $\endgroup$ – Marko Riedel Jun 9 '17 at 0:26
  • $\begingroup$ The general formula is included at the end of my post since the first version. Set $k$ to $4,5,6,7$ and you will get one, which looks to be the correct value. The four values from your formula are given in my first comment (values not equal to one). $\endgroup$ – Marko Riedel Jun 9 '17 at 0:35
  • $\begingroup$ @MarkoRiedel When $k = 4$, the question is, what is the probability that the first four cards will be aces? That is $1/270725$, unless I'm mistaken. $\endgroup$ – user49640 Jun 9 '17 at 0:38
  • $\begingroup$ Yes indeed. I interpreted OP to mean that if we see the fourth ace on draw $k$ and stop then what is the probability that the aces form the first complete set, i.e. that all other ranks are present with at most three cards. So if $k\le 7$ no other rank can be represented with four cards, giving probability one. $\endgroup$ – Marko Riedel Jun 9 '17 at 0:48
  • $\begingroup$ @MarkoRiedel Look at the OP's third paragraph. That gives the most precise definition of the probability he or she wants. $\endgroup$ – user49640 Jun 9 '17 at 0:50
1
$\begingroup$

Suppose we work with $q$ ranks, one of which is aces, rather than thirteen. Fixing one of these ranks the sequences of cards being chosen from that rank where there are at most three cards present have EGF

$${4\choose 0} 0! + {4\choose 1} 1! z + {4\choose 2} 2! \frac{z^2}{2!} + {4\choose 3} 3! \frac{z^3}{3!} = 1 + 4z + 6z^2 + 4z^3.$$

We thus get for the favorable outcomes

$${4\choose 3} \times 3! \times {k-1\choose 3} \times (k-4)! [z^{k-4}] (1+4z+6z^2+4z^3)^{q-1}.$$

Similarly for the total outcomes we obtain (we are calculating a conditional probability here, namely what is the probability of the aces being the first set given that the fourth ace appeared at draw $k$)

$${4\choose 3} \times 3! \times {k-1\choose 3} \times (k-4)! [z^{k-4}] (1+4z+6z^2+4z^3+z^4)^{q-1} \\ = {4\choose 3} \times 3! \times {k-1\choose 3} \times (k-4)! [z^{k-4}] (1+z)^{4q-4} \\ = {4\choose 3} \times 3! \times {k-1\choose 3} \times (k-4)! {4q-4\choose k-4}.$$

Divide these to get for the probability

$$\bbox[5px,border:2px solid #00A000]{ {4q-4\choose k-4}^{-1} [z^{k-4}] (1+4z+6z^2+4z^3)^{q-1}.}$$

Simplifying this we get

$${4q-4\choose k-4}^{-1} [z^{k-4}] (-z^4+(1+z)^4)^{q-1} \\ = {4q-4\choose k-4}^{-1} \sum_{p=0}^{q-1} {q-1\choose p} (-1)^p [z^{k-4}] z^{4p} (1+z)^{4q-4-4p}.$$

This is

$${4q-4\choose k-4}^{-1} \sum_{p=0}^{q-1} {q-1\choose p} (-1)^p {4q-4-4p\choose k-4-4p}$$

or alternatively

$$\bbox[5px,border:2px solid #00A000]{ {4q-4\choose k-4}^{-1} \sum_{p=0}^{q-1} {q-1\choose p} (-1)^p {4q-4-4p\choose 4q-k}.}$$

In particular we obtain for a standard deck with thirteen ranks the formula

$${48\choose k-4}^{-1} \sum_{p=0}^{12} {12\choose p} (-1)^p {48-4p\choose 52-k}.$$

Seeing that this is one of those problems where it is very important to get the definition right I include some Maple code to document the model I am working with.

with(combinat);

ENUM :=
proc(q, k)
option remember;
local res_nset, res_all, comb, mset, adm;

    comb := firstcomb(q*4, k);
    res_nset := 0; res_all := 0;

    while type(comb, set) do
        mset :=
        convert(map(p -> p mod q,
                    convert(comb, list)),
                multiset);

        if numboccur(mset, [[0, 4]]) = 1 then
            res_all := res_all + 4*(k-1)!;

            adm :=
            select(ent -> ent[1] <> 0 and ent[2] < 4,
                   mset);

            if nops(adm) = nops(mset)-1 then
                res_nset := res_nset + 4*(k-1)!;
            fi;
        fi;

        comb := nextcomb(comb, q*4);
    od;

    [res_nset, res_all];
end;

X :=
(q, k) ->
[24*binomial(k-1,3)*(k-4)!*
 coeftayl(((1+z)^4-z^4)^(q-1), z=0, k-4),
 24*binomial(k-1,3)*(k-4)!*binomial(4*q-4, k-4)];

P := (q, k) ->
binomial(4*q-4, k-4)^(-1)*
coeftayl(((1+z)^4-z^4)^(q-1), z=0, k-4);

P1 := (q, k) ->
binomial(4*q-4, k-4)^(-1)*
add(binomial(q-1,p)*(-1)^p*binomial(4*q-4-4*p, 4*q-k),
    p=0..q-1);
$\endgroup$
  • $\begingroup$ i acknowledge reading this answer. and thank you for taking the time! i'm in the process of verifying on my end. will be a bit. but it looks like exactly what I was after. $\endgroup$ – Math Misery Jun 12 '17 at 0:03

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.