Skip to main content
2 of 3
edited body
Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171

Expected number of coin flips before you see a $k$-term arithmetic progression of heads

Let $\{X_i\}_{i \in \mathbb Z_+} $ be independent fair coin flips. Write $S := \{i \in \mathbb Z_+\, | \, X_i \text{ is heads}\}$, and define, for an integer $k \geq 3$,

$$Y := \inf \{n \in \mathbb N \, | \, \text{There exists a }k\text{-term arithmetic progression in } S \cap \{1, \dots, n\}\}.$$

What is the expected value of $Y$?

Nate River
  • 6.3k
  • 2
  • 23
  • 100