Expected Run Count in Coin Tosses

Suppose a fair coin is flipped 21 times. A run is a maximal consecutive stretch of identical outcomes. For instance, HHHTTH contains three runs: HHH, TT, and H. Compute the expected number of runs.

Constraints & Assumptions

• The tosses are independent, and each side occurs with probability one half.
• Any nonempty sequence starts with exactly one run.

Clarifying Questions to Ask

• Are the tosses independent and is the coin fair?
• Does a run count once no matter how long it is?

Hint — Count changes between adjacent tosses: After the first toss, a new run starts exactly when the next toss differs from the previous one.

What a Strong Answer Covers

• An indicator-variable expression for the run count.
• The chance that any given adjacent pair differs.
• Applying linearity of expectation without requiring the indicators to be independent.
• The final numeric expected value.

Follow-up Questions

• What is the expectation for $n$ tosses of a coin with head probability $p$?
• How would you compute the variance of the run count?

Overview: Find the expected number of same-side runs in 21 coin tosses, where a run is a maximal consecutive block of identical outcomes.