Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 9 down vote accepted

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

share|improve this answer
1  
More generally, a deck with $2k$ cards, $k$ of each color, has expected number of runs $k+1$. –  Michael Lugo Aug 19 '10 at 2:44
    
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). –  KalEl Aug 20 '10 at 14:40
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.