Katkat
Back

Compare Two Strategies for Getting Ten Consecutive Heads

Virtu FinancialQuantitative Researcher · Onsite
HardQuantitative ResearcherOnsiteStatistics & Math

Last updated

This problem tests your ability to model probability through recursion and expectation, specifically comparing the efficiency of two distinct strategies for achieving a target streak of coin tosses.

The Problem

Consider a fair coin that lands on heads (H) or tails (T) with probability 0.5 each. You want to achieve a sequence of 10 consecutive heads (H-H-H-H-H-H-H-H-H-H).

Compare the expected number of total flips required under the following two strategies:

Strategy A: The Continuous Stream You flip the coin continuously until you see 10 consecutive heads.

Strategy B: The Batch Reset You flip the coin in blocks of 10. If the sequence is not 10 consecutive heads, you discard all results and start a brand new block of 10 flips. You repeat this until a block results in 10 heads.

Requirements

  1. Define the recurrence relation for the expected number of flips for Strategy A.
  2. Calculate the expected number of total flips for Strategy B.
  3. Identify which strategy is more efficient and explain the intuition behind the difference in expected values.

Constraints

  • The coin is fair: P(H) = 0.5, P(T) = 0.5.
  • Provide the exact expected value for both strategies.

Examples

  • If the target were 2 consecutive heads:
    • Strategy A (Continuous): The expected flips is 6 (derived from E = 2 + 1/20 + 1/2E).
    • Strategy B (Batch): The probability of success in one batch is (1/2)^2 = 1/4. The expected number of batches is 4, and each batch takes 2 flips, resulting in 8 total flips.

Hints

Hint 1

For Strategy A, let E be the expected number of flips; consider the state transition after a single flip results in a tail at any position in the sequence.

Hint 2

For Strategy B, treat the process as a sequence of Bernoulli trials where each trial represents a batch of 10 flips, and the probability of success per batch is (1/2)^10.

Hint 3

Observe that Strategy A benefits from 'overlapping' sequences, where a failure at the 10th flip doesn't necessarily force a reset to the beginning of the progress.

Follow-up questions

  • How does the expected value of Strategy A change if the coin is biased with P(H) = p?
  • If you are allowed to stop the 'continuous stream' and restart at any time, could you ever outperform the standard Strategy A?
  • What is the variance of the number of flips required for Strategy A compared to Strategy B?