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?

$\endgroup$
  • $\begingroup$ Apparently this has an easy solution. $\endgroup$ – KalEl Aug 19 '10 at 1:38
  • 1
    $\begingroup$ Want to post it ? $\endgroup$ – Tal Galili Aug 19 '10 at 2:28
  • $\begingroup$ why has this question/answer pair been imported in toto from the math SE? $\endgroup$ – shabbychef Sep 20 '10 at 21:28
3
$\begingroup$

Suppose $X_n$ denotes the color of the $n$th card in the shuffled deck.

Then note that the last card always denotes the end of a run. Other ends of runs are characterized by $X_n\ne X_{n+1}$ which indicates a run ending at $n$.

Note that $P(X_n\ne X_{n+1})=26/51$ (since once you fix a card, you can choose another card from remaining 51 out of which 26 will have a different color).

So summing up the indicators $X_n\ne X_{n+1}$ we get the number of runs -

$\#runs=1+\sum_{n=1}^{51}\mathbb{I}_{X_n\ne X_{n+1}}$.

So $E(\#runs)=1+\sum_{n=1}^{51}P(X_n\ne X_{n+1})=1+\sum_{n=1}^{51}26/51=27$.

$\endgroup$
  • $\begingroup$ I am not convinced -- is P(X_n != X_(n+1)) independent from n? $\endgroup$ – Karsten W. Aug 19 '10 at 21:36
  • 8
    $\begingroup$ You ought to credit the person who really answered this question (George Lowther), especially because you copied his answer with only trivial changes. See math.stackexchange.com/questions/2763/… . $\endgroup$ – whuber Aug 21 '10 at 17:17
  • $\begingroup$ @whuber Yes definitely, it's not my credit. I merely reproduced it here. Thanks for putting up that note. @Karsten It is shown by a counting argument - once you have fixed $X_n$ in 52 ways, there are 26 ways you can select non-matching $X_{n+1}$. So $P(X_n\ne X_{n+1})=\frac{52*26}{52*51}$. $\endgroup$ – KalEl Aug 22 '10 at 12:35
  • $\begingroup$ @Karsten If you are asking if the events $X_n \ne X_{n+1}$ are independent of $n$, they are not. But that doesn't matter since expectation of sum = sum of expectations even if the quantities are dependent. $\endgroup$ – KalEl Aug 22 '10 at 12:38
  • $\begingroup$ See also en.wikipedia.org/wiki/Wald–Wolfowitz_runs_test , where the mean number of runs matches that given here. $\endgroup$ – shabbychef Sep 20 '10 at 4:51

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.