连续 n 个正面的期望抛掷次数

一个经典结果（可用马尔可夫链或停时鞅证明）是

$$\mathbb{E}[\tau_n]=2^{n+1}-2.$$

其中 $\tau_n$ 表示首次出现 $n$ 连 H 的抛掷次数。

---

Original Explanation

Let $E[f(n)]$ be the expectation. A known result (via Markov chain or a martingale stopping argument) is: $$E[f(n)] = 2^{n+1} - 2.$$

Martingale Sketch (brief)

• Imagine a sequence of “gamblers” each betting on hitting $n$ heads in a row.
• Once a gambler achieves $n$ heads in a row, they win $2^n$ dollars and the game stops.
• An analysis of the stopping-time martingale shows the stopping time $i$ has expectation $2^{n+1}-2$.

Thus, on average, $2^{n+1} - 2$ tosses are needed to see $n$ consecutive heads.