Katkat
Back

Expected Number of Runs in Coin Tosses

Goldman SachsData Scientist · Online Assessment
EasyData ScientistOnline AssessmentStatistics & Math

Last updated

Tests understanding of linearity of expectation and indicator random variables through counting consecutive runs in a sequence of coin tosses.

Scenario

You flip a fair coin 21 times, generating an ordered sequence of outcomes consisting of Heads (H) and Tails (T). A run is defined as a maximal consecutive subsegment of identical outcomes.

For example:

  • In the sequence H H T H T T, there are 4 runs: [H H], [T], [H], and [T T].
  • In the sequence H H H H, there is only 1 run: [H H H H].
  • In the sequence H T H T, there are 4 runs: [H], [T], [H], and [T].

Problem Statement

  1. Define a general analytical formulation for the expected number of runs, E[R], in a sequence of n independent coin tosses where the probability of landing Heads is p and Tails is 1 - p.
  2. Using your formula, calculate the exact expected number of runs when n = 21 and the coin is fair (p = 0.5).

Requirements

  • Provide a rigorous derivation using indicator random variables and the linearity of expectation.
  • Clearly define the condition under which a new run begins.
  • State your final numerical answer for n = 21 and p = 0.5 clearly.

Hints

Hint 1

Express the total number of runs as 1 plus the sum of indicator variables representing whether a change in outcome occurs.

Hint 2

A new run starts at position i (for i from 2 to n) if and only if the outcome at toss i is different from the outcome at toss i - 1.

Hint 3

Apply linearity of expectation to sum the probabilities of starting a new run across all positions from 2 to n.

Follow-up questions

  • How would you compute the variance of the total number of runs in n coin tosses?
  • For what value of p is the expected number of runs maximized, and why?
  • What is the expected length of a run given a sequence of n fair coin flips?