Skip to content

Expected colour runs in a shuffled deck

Question

A run is a maximal stretch of consecutive cards of the same colour; for instance BBRRBBB contains three runs.

(a) For a well-shuffled standard deck (2626 red, 2626 black), find the expected number of runs.

(b) Describe a program that, for a deck of XX cards divided equally among YY colours and shuffled at random, returns the mean number of runs.

Short answer

(a) 2727. (b) X−X/Y+1X-X/Y+1, computed in O(1)O(1). Runs equal 11 plus the number of adjacent pairs whose colours differ. A given adjacent pair differs with probability 1−X/Y−1X−11-\tfrac{X/Y-1}{X-1}, and linearity over the X−1X-1 pairs gives X−XY+1X-\tfrac XY+1; for 5252 cards and 22 colours this is 2727. A Monte Carlo shuffle can be used to check it.

Adapted from OpenQuant; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Expectation, Variance and Covariance is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free