12
$\begingroup$

Standard deck has $52$ cards, $26$ Red and $26$ Black. A run is a maximum contiguous block of cards, which has the same color.

Eg.

  • $(R,B,R,B,...,R,B)$ has $52$ runs.
  • $(R,R,R,...,R,B,B,B,...,B)$ has $2$ runs.

What is the expected number of runs in a shuffled deck of cards?

$\endgroup$

3 Answers 3

20
$\begingroup$

The expected number of runs is 27.

Let $X_n$ be the color of the n'th card. For n<52, the n'th card is the end of a run if and only if $X_n\not=X_{n+1}$ and the last card in the pack is always the end of a run. So, the total number of runs is $$ N=\sum_{n=1}^{51}1_{\{X_n\not=X_{n+1}\}}+1. $$ The expected number of runs is $$ \mathbb{E}[N]=\sum_{n=1}^{51}\mathbb{P}(X_n\not=X_{n+1})+1. $$ Whatever colour the n'th card is, there are 51 remaining cards in the deck of which 26 of them are a different colour from $X_n$. So, $\mathbb{P}(X_n\not=X_{n+1})=26/51$, giving $$ \mathbb{E}[N]=51 (26/51) + 1=27. $$

$\endgroup$
7
  • 3
    $\begingroup$ More generally, a deck with $2k$ cards, $k$ of each color, has expected number of runs $k+1$. $\endgroup$ Commented Aug 19, 2010 at 2:44
  • $\begingroup$ Thanks George. I initially tried induction, it didn't work out well. Then I got the solution through some very dirty calculations involving summing up products of combination terms. It was messy but it worked - though I had a hunch that there must be an easier way. I was also not sure about the answer from my messy calculations (though now after your post I am). $\endgroup$
    – KalEl
    Commented Aug 20, 2010 at 14:40
  • 1
    $\begingroup$ Can anyone explain why $P(X_n \neq X_{n+1}) = 26/51$? It seems like you are assuming $P(X_n \neq X_{n+1})$ are independent for each $n$, but surely it depends on the cards that have come out before? E.g., if you've had a long run, there would be a really high probability for a colour change. $\endgroup$
    – user428487
    Commented Mar 19, 2020 at 21:49
  • $\begingroup$ Couldn't it just be that the minimum runs is 2 (all the black and then all the red cards) and the maximum is 52 (B,R,B,R,B,R .....) so the runs are independently and identically distributed between $[2,52]$ so the expected number of runs is simply the $mean = \frac{52+2}{2} = 27$ ? $\endgroup$
    – Mining
    Commented Sep 27, 2021 at 10:09
  • 2
    $\begingroup$ @user428487: Linearity of expectation does not require that the random variables are independent, nor that they are identically distributed. $\endgroup$ Commented Jan 14, 2023 at 3:31
4
$\begingroup$

Note: This solution works because of the happy "coincidence" that the number of ways to get $k$ runs is the same as the number of ways to get $2n+2 - k$ runs. We will prove that first, then apply it.

Lemma: The number of ways to achieve $k$ runs is $ 2 \times { n-1\choose \lceil \frac{k}{2} \rceil-1} \times { n-1 \choose \lfloor \frac{k}{2} \rfloor - 1 }$.

Proof: A sequence of $k$ runs can be defined as having $a_1$ of the first color, $b_1$ of the second color, $a_2$ of the first color, $b_2$ of the second color, so on and so forth. For the final term, if $i$ is odd, we have $a_{ \lceil \frac{k}{2} \rceil }$ of the first color, and if $k$ is even, we have $b_{\lfloor \frac{k}{2} \rfloor}$ of the second color.

After choosing what the first color is, we have the constraint that $ \sum a_i = n$ and $ \sum b_i = n$, of which there are $ \lceil \frac{k}{2} \rceil $ terms in the first summation and $ \lfloor \frac{k}{2} \rfloor$ terms in this second summation. It is easy to see that this is the only constraint, since given any 2 such summations, we can form a sequence of $i$ runs. This establishes the bijection between a sequence of $k$ runs and solutions to these equations.

We now count the number of ways to get such solutions. By bars and stars, there are $ { n-1 \choose \lceil \frac{i}{2} \rceil - 1 } $ solutions to the first equation, and ${ n-1 \choose \lfloor \frac{i}{2} \rfloor - 1 }$ solutions to the second. Hence the lemma follows.

Corollary: Given $2n$ cards, the number of ways to get $r$ runs is the same as the number of ways to get $2n+2-r$ runs.

Corollary: By symmetry, the expected number of runs is $ \frac{ r + ( 2n+2 - r ) } { 2 } = n+ 1 $.

$\endgroup$
1
$\begingroup$

An alternative thought process following the thinking of Calvin Lin & Mining in the comments of George Lowther's solution. It is more involved, so not the kind of back-of-the-envelop solution this post is looking for, educational nonetheless.

Conjecture

Suppose our deck of cards consists of $n$ red cards and $n$ black cards respectively (usually, $n=26$). Define $U$ as the total number of runs in shuffled sequence of our deck. By empirical observation, it seems that $$ \mathbb{P}\{U=2k\}=\mathbb{P}\{U=2[n-(k-1)]\}. $$ For example, the following charts show average frequencies of runs in the cases of $n=4$ and $n=5$.

enter image description here

In our case of $n=26$, this means that $$ \mathbb{P}\{U=2\}=\mathbb{P}\{U=52\},~ \mathbb{P}\{U=3\}=\mathbb{P}\{U=50\},\cdots. $$ If this were true, then, by symmetry, our expected number of runs is simply $$ \dfrac{2k+2[n-(k-1)]}{2} = n+1, $$ or 27 for a normal deck of cards. This is the same answer that George Lowther had calculated.

Proof Part I

Wald and Wolfowitz calculated the closed form probabilities of $\mathbb{P}(U=2k)$ and $\mathbb{P}(U=2k-1)$. I will walk through the former since the latter follows the exact logic.

Following the notation in Wald and Wolfowitz, let $r_{Rj}$ be the length of the $j$-th red run and, similarly, $r_{Bj}$ be the length of the $j$-th black run. Let $e_R$ be the total number of red runs and, similarly, $e_B$ be the total number of black runs. Obviously,

$$ \sum_{j=1}^{e_R}r_{Rj}=\sum_{j=1}^{e_B}r_{Bj}=n,\\ 1\leq e_R, e_B \leq n,\\ \text{and }|e_R-e_B|\leq 1. $$

The last property follows since red and black runs must be alternating by definition of runs. Therefore, if $U=2k$, then $e_R=e_B=k$. There are 2 sub-cases with equal likelihood: whether the sequence starts with red or black. Therefore, the complete sequence is fully described by

  • the color of the first card, and
  • the sequence of run lengths $r_{*j}$, where * can be R or B.

Suppose that the first card is fixed, say red, the number of all possible sequences in this case equal the product of

  1. number of ways to arrange the red runs $r_{Rj}$ such that they partition $n$ into $k$ positive summands. In symbols, $\sum_{j=1}^{k}r_{Rj}=n$, $1\leq k\leq n$.
  2. do the same for black. In symbols, $\sum_{j=1}^{k}r_{Bj}=n$, $1\leq k\leq n$.

Observe that both 1 and 2 are exactly the coefficient of $a^n$ in the expansion of

$$ (a+a^2+a^3+\cdots)^k=\left(\dfrac{a}{1-a}\right)^k. $$

We just need to get that coefficient.

Lemma

If $f(a)=(1-a)^{-1}$, then the $k$-th derivative $f^{(k)}(a)=k!(1-a)^{-(k+1)}$. This implies that $$ \left(\dfrac{1}{1-a}\right)^k = \dfrac{1}{(k-1)!}f^{(k-1)}(a). $$

On the other hand, by differentiating the geometric expansion of $f(a)=1+a+a^2+\cdots$, we have $$ f^{(k-1)}(a)=\sum_{n=0}^{\infty}\dfrac{(n+k-1)!}{(k-1)!}a^n. $$

Plugging this into the previous equation, we get $$ \left(\dfrac{a}{1-a}\right)^k = \dfrac{a^k}{(k-1)!}\sum_{n=0}^{\infty}\dfrac{(n+k-1)!}{(k-1)!}a^n =\sum_{n=k}^{\infty}{{n-1}\choose{k-1}}a^n. $$

Proof Part II: Conclusion

To conclude, we've shown that there are ${n-1}\choose{k-1}$ ways to satisfy 1 and 2 above. Their product ${{n-1}\choose{k-1}}^2$ is the total number of sequences that have $U=2k$ runs starting with a red card. We conclude by observing the cases of $U=2k$ and $U=2[n-(k-1)]$ and that ${{n-1}\choose{k-1}} = {{n-1}\choose{n-(k-1)-1}}$, hence justifying our conjecture.

Reference

A. Wald, J. Wolfowitz "On a Test Whether Two Samples are from the Same Population", The Annals of Mathematical Statistics, Ann. Math. Statist. 11(2), 147-162, (June, 1940), accessed from Project Euclid

Code Listing

The following Python code is used to generate the above plots.

import numpy as np
from itertools import permutations
from matplotlib import pyplot as plt

def count_runs(outcome:str):
    outcome=np.array(list(outcome))
    cuts = np.where(outcome[:-1]!=outcome[1:])[0]
    lengths = np.diff(cuts, prepend=-1, append=len(outcome)-1)
    return 1+len(cuts), lengths

###########################
# Customize the Following #
###########################
num_of_cards = [8, 10] # easy on this number, remember this is factorial time!
#######################
# Customize the Above #
#######################

fg, ax = plt.subplots(1, len(num_of_cards), figsize=(10,4))

for i in range(len(num_of_cards)):
    n = num_of_cards[i]
    if n % 2:
        raise ValueError("num_of_cards needs to be even.")

    deck = (n//2)*"B"+(n//2)*"R"
    all_outcomes = tuple({''.join(p) for p in permutations(deck)})
    print("There are {} possible shuffling outcomes.".format(len(all_outcomes)))
    runs_counts = np.zeros(len(deck))

    for j in all_outcomes:
        count = count_runs(j)[0]
        runs_counts[count-1] += 1
        #print(i, count)

    ax[i].bar(np.array([i+1 for i in range(1,len(runs_counts))]), runs_counts[1:])
    ax[i].set_xlabel('Number of Runs in Outcome with {} Cards ($n={}$)'.format(n, n//2))
    ax[i].set_ylabel('Frequency Count');
    #ax[i].grid()
$\endgroup$
1
  • 1
    $\begingroup$ +1 There's a much more immediate proof. I added it as a solution. $\endgroup$
    – Calvin Lin
    Commented Feb 25, 2022 at 1:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .