连续 N 次正面

递推可得

$$E_N = 2E_{N-1}+2,\quad E_1=2.$$

解得

$$E_N = 2^{N+1}-2.$$

---

Original Explanation

Recurrence form: $E_N = 2E_{N-1} + 2$; Closed form: $E_N = 2^{N+1}-2$

Solution

Method 1

We can simply reuse the method from problem "Innocent Monkey" (the law of total probability)

Define let $X_N$ = number of tosses to get $N$ consecutive heads

$E_N$ = expected number of coin tosses we require from now on, to get $N$ consecutive heads.

Note that if we already have $N-1$ Heads, then with probability (1/2), we can get $N$ consecutive heads, and with probability (1/2), we get a tail, and the state is reset.

$E_N = \frac{1}{2}( E_{(N-1)} + 1) + \frac{1}{2}(E_{N-1} + 1 + E_N)$

the extra 1 is because we just used a toss

$E_N = 2E_{N-1} + 2$

This is a recurrence relation and a good enough solution. But we can solve this into its closed form too.

The right way to solve this is by using generating functions or characteristic equations. But we will use a more intuitive approach.

We can tell it is an exponential function, involving powers of $2$ because the $N$th term is about 2 times $N-1$th term. Suppose $E_N = C_1 \cdot 2^{N} + C_2$

Assume that $E_0 = 0$ (no tosses needed) $\implies 0 = C_1 + C_2$

And $E_1 = 2$ (refer to method 2, step 1) $\implies 2 = C_1\cdot 2 + C_2$

Simplify to get $C_1 =2, C_2 = -2$

This simplifies to $E_N = 2^{(N+1)}-2$

---

Method 2

This approach is more rigorous and algebraic.

Let us solve a simpler question first.

Step 1: What's the expected number of coin tosses to get $N=1$ heads?

There are two possibilities:

1. We get a head in the first toss itself. This happens with probability $1/2$.
2. We get a tail in the first toss, and then we start a new game, where number of chance is 1 more than the expected value.

$E_1 = \dfrac{1}{2} \cdot 1 + \dfrac{1}{2} \cdot (1 + E_1)$

Simplify to get $E_1 = 2$

Step 2: What's the expected number of coin tosses to get $N=2$ consecutive heads?

There are three possibilities:

1. We can get two heads in the first two tosses itself. This happens with probability $1/4$, and takes 2 tosses.
2. We can get a tail in the first toss, and then we start a new game, where number of attempts is 1 more than the expected value.
3. We can get a heads in the first toss, and then tails in the second. Then we start a new game, where number of attempts is 2 more than the expected value.

$E_2 = \dfrac{1}{4} \cdot 2 + \dfrac{1}{2} \cdot (1 + E_2) + \dfrac{1}{4} \cdot (2 + E_2)$

Simplify to get $E_2 = 6$

Step 3: What's the expected number of coin tosses to get $N$ consecutive heads?

There are $N+1$ possibilities.

1. We can get $N$ heads in the first $N$ tosses itself. This happens with probability $1/2^N$, and takes $N$ tosses.
2. We can get a tail in the first toss, and then we start a new game, where number of attempts is 1 more than the expected value.
3. We can get a heads in the first toss, and then tails in second. Then we start a new game, where number of attempts is 2 more than the expected value.
4. $\vdots$
5. We can get $N-1$ heads in the first $N-1$ tosses, and then a tail in the $N^{th}$ toss. Then we start a new game, where number of attempts is $N$ more than the expected value.

$E_N = \dfrac{1}{2^N} \cdot N + \dfrac{1}{2} \cdot (1 + E_N) + \dfrac{1}{2^2} \cdot (2 + E_N) + \ldots + \dfrac{1}{2^{N}} \cdot (N + E_N)$

This looks quite complex, but be assured that this can be simplified. I did not spend time on solving this.

Simplify to get $E_N = 2^{N+1}-2$

---

Method 3 (for $N=1$ only)

We can use linearity of expectation for $N=1$

Let $X$ be the number of tosses required to get 1 head.

Define indicator variable, $X_i = 1$ if no Heads appeared before the $i$th step and $0$ otherwise. Once we get a "heads", we stop tossing, so all the later $X_i=0$.

Note that $X = \sum_{i=1}^{\infty} X_i$

$E[X] = E[\sum_{i=1}^{\infty} X_i] = \sum_{i=1}^{\infty} E[X_i]$ (using linearity of expectation)

$E[X_1] = 1 \cdot \dfrac{1}{2} + 1 \cdot \dfrac{1}{2} = 1$ (if heads, then also count 1, if tails, then also count 1)

$E[X_2] = P(\text{First toss was Tails}) \cdot 1$

$E[X_3] = P(\text{First two toss were Tails}) \cdot 1 = \dfrac{1}{4}$

$\vdots$

$E[X] = \sum_{i=1}^{\infty} E[X_i] = 1 + \dfrac{1}{2} + \dfrac{1}{4} + \ldots = 2$

Okay, same answer as before.

Unfortunately, I'm unable to extend this solution to $N=2$ and further because of the presence of the state.

---

Method 4 (for $N=1$ only)

This method uses the basic definition of expected value.

$E[X] = P(X=1) \cdot 1 + P(X=2) \cdot 2 + \ldots$

$P(X=1) = 1/2$ (because we can get a head in the first toss itself)

$P(X=2) = 1/4$ (first tails, and second hands)

$\vdots$

$E[X] = \dfrac{1}{2} \cdot 1 + \dfrac{1}{2^2} \cdot 2 + \dfrac{1}{2^3} \cdot{3}$

This is an Arithmetic Geometric Progression of type $a, (a+d)r, (a+2d)r^2, \ldots, [a + (n-1)d] r^{n-1}$ with $a=0, d=1, r=1/2$

The sum of infinite such terms is $S = \dfrac{a}{1-r} + \dfrac{dr}{(1-r)^2} = \dfrac{1/2}{1/4} = 2$