Probability of a run of $n$ cards of the same color?

Question

A magician friend hit me with this one: given a shuffled deck, what is the probability that it contains at least one run of at least $n$ cards of the same color — for example, four reds or four blacks in a row?

Answer 1

It's not easy to give an exact result, but if you want a simple upper bound, you can compute the expected number of runs of length $n$ easily. Any given block of $n$ cards is a run with probability $$ \frac{{{52-n}\choose{26}}}{{52}\choose{26}}=\frac{(52-n)!26!}{(26-n)!52!}, $$ so the expected number of runs of length $n$ is just $$ E_n = (53-n)\frac{(52-n)!26!}{(26-n)!52!}=\frac{53\cdot {{26}\choose{n}}}{{53}\choose{n}}. $$ (Here we are allowing non-maximal runs in the count... so a run of length $8$, say, contains three runs of length $6$.) The expected number of runs of length $n$ is greater than or equal to the probability of there being at least one run of length $n$. The first nontrivial result comes for $n=6$: the probability of at least one run of length $6$ satisfies $$ P_6 \le E_6 = \frac{53\cdot{{26}\choose{6}}}{{53}\choose{6}}=\frac{26\cdot 25\cdot 24\cdot 23 \cdot 22\cdot 21}{52 \cdot 51\cdot 50 \cdot 49\cdot 48}=0.5315... $$ Since the exact result is $P_6=0.46424\ldots$, this isn't too loose; and it will yield closer approximations for longer run lengths.

Answer 2

Suppose we have $m$ red and $m$ black cards and we ask about the $(2m)!$ shuffled decks containing a run of at least $n$ cards of the same color. We will compute the probability of the complementary event, i.e. there not being a run of $n$ colors or all runs having length at most $n-1.$

Using $z$ for red cards and $w$ for black cards we have by inspection that the count is $$[z^m w^m] G(z, w)$$

where $G$ is the generating function

$$G(z, w) = [z^m w^m] (1+\cdots+z^{n-1})(1+\cdots+w^{n-1}) \\ \times \sum_{q=0}^m w^q z^q (1+\cdots+z^{n-2})^q(1+\cdots+w^{n-2})^q.$$

The polynomials that appear in this generating function have $O(n^2 m^2)$ terms (contribution from the sum), in a different league from the $4^m/\sqrt{\pi m}$ of the binomial coefficient. Where we pay is in the size of the coefficients which are $m$ digits worst case.

As an aside note that we need to multiply the coefficents from $G(z,w)$ by $(m!)^2$ because that is the number of decks corresponding to a binary pattern of colors where we have assumed that cards of the same color and value but from a different suit are considered distinct.

In particular the answer for a deck of cards where we have $26$ reds and $26$ blacks not having a run of length four is (this value is exact)

$${52\choose 26}^{-1} 12911299418962 \sim 0.02603512182$$

so the probability that it does contain a run of length four is $$97.4\%.$$

Obviously we have not checked all $495918532948104$ possible binary sequences containing $26$ zeros and ones to obtain this answer.

Interestingly enough when we set $n=2$ and there are only two possible candidates alternating between zero and one the formula produces

$$[z^m w^m] (1+z)(1+w) \sum_{q=0}^m w^q z^q.$$

As the terms in the sum are matched in their exponents we must select an equally matched pair from the product in front and these are $1$ and $wz$ and we do obtain two as the answer when we match them to $z^m w^m$ and $z^{m-1}w^{m-1}$ from the sum.

Finally observe that the formula given above allows us to generate sequences for fixed $n$ and consult the OEIS for more information. These OEIS entries contain some very sophisticated closed form expressions that show that we can find formulas in binomial coefficients for $n$ fixed.

For example, not permitting runs of length $3$ yields $$2, 6, 14, 34, 84, 208, 518, 1296, 3254, 8196, 20700, \\ 52404, 132942, 337878, \ldots$$

which is OEIS A177790.

Similarly not permitting runs of length $4$ yields $$2, 6, 20, 62, 194, 616, 1972, 6344, 20498, 66486, 216352, \\ 705982, 2309246, 7569420, \ldots$$

which is OEIS A177792.

The reader who wishes to initiate additional studies of these numbers may wish to consult the following Maple code where a total enumeration routine is presented and the generating functions are provided. To showcase these I point out that with $50$ cards each and no runs of more than seven being permitted we get the value

$${100\choose 50}^{-1} 52686377360486324043397253174$$

which gives $$47.78\%$$ for the complementary event (there is a run of at least seven cards).

RL :=
proc(m, n)
    option remember;
    local iter, res;

    res := 0;

    iter :=
    proc(zc, oc, d)
        local  pos, cur, runlen;

        if zc = 0 and oc = 0 then
            cur := -1; pos := 1; runlen := 0;

            while pos <= 2*m do
                if d[pos] <> cur then
                    cur := d[pos];
                    runlen := 1;
                else
                    runlen := runlen + 1;

                    if runlen >= n then
                        break;
                    fi;
                fi;

                pos := pos + 1;
            od;

            if pos = 2*m+1 and runlen<n then
                res := res + 1;
            fi;

            return;
        fi;

        if zc >= 1 then
            iter(zc-1, oc, [op(d), 0]);
        fi;
        if oc >= 1 then
            iter(zc, oc-1, [op(d), 1]);
        fi;

    end;

    iter(m, m, []);

    res;
end;

Q1 :=
proc(m, n)
    option remember;
    local H;

    H := (1-z^n)*(1-w^n)*
    1/((1-z)*(1-w)-w*z+w*z^n+z*w^n-w^n*z^n);

    coeftayl(coeftayl(H, z=0, m), w=0, m);
end;

Q3 :=
proc(m, n)
    option remember;
    local K;

    K := add(z^q, q=0..n-1)*add(w^q, q=0..n-1)*
    add(w^q*z^q*add(z^q, q=0..n-2)^q*add(w^q, q=0..n-2)^q,
        q=0..m);


    coeff(coeff(expand(K), z, m), w, m);
end;

The following plot shows the probabilities when we have sixteen cards of each color. We get all configurations when we permit runs of length at most sixteen, obviously.

1 +                                HHHHHHHHHHHHHHHHHHHHHHHHHH
  +                           HHHHH
  +                        HHH
  +                       HH
  +                     HH
0.8                    H
  +                    H
  +                   H
  +                  H
  +                 HH
0.6                 H
  +                 H
  +                H
  |                H
  +               H
  +               H
0.4              H
  +              H
  +             H
  +             H
  +            H
0.2            H
  +           H
  +          H
  +         HH
  +        H
  +********+-++-++-++-++-+-++-++-++-++-++-++-++-+-++-++-++-++-
0      2      4       6       8     10      12      14     16