6
$\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?

1 Answers 1

10

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

  • 2
    More generally, a deck with $2k$ cards, $k$ of each color, has expected number of runs $k+1$.2010-08-19
  • 0
    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).2010-08-20