sergazy.nurbavliyev@gmail.com © 2021

## Expected Number of flips until N heads

Question: Assume we have a fair coin. What is the expected number of coin flips needed to get $N$ consecutive heads.

### Intuition

Let us solve this for $N=2$ first. Then we will generalize the idea for any $N$. Let $X$ denote the number of flips that we need to get two consecutive heads. Then we want to find $\mathbb{E}[X]$. We will denote the flip that results in head with $H$ and in tails as $T$. 
Then we can write $\mathbb{E}[X]$ as:
\begin{equation}
\mathbb{E}[X]=\mathbb{P}(H)(1+\mathbb{E}[X|H])+\mathbb{P}(T)(1+\mathbb{E}[X|T])=\frac{1}{2}(1+\mathbb{E}[X|H])+\frac{1}{2}(1+\mathbb{E}[X|T])
\end{equation}
where we conditioned on our first flip. Note that $\mathbb{E}[X|T])=\mathbb{E}[X])$ because after we see tails we need to start over again to see two consecutive heads. Then equation (1) becomes
\begin{equation}
\mathbb{E}[X]=\frac{1}{2}(1+\mathbb{E}[X|H])+\frac{1}{2}(1+\mathbb{E}[X])
\end{equation}
Now we need to solve $\mathbb{E}[X|H]$. We will conditioned further if we can get rid of these terms. Then we have
\begin{equation}
\mathbb{E}[X|H]=\mathbb{P}(H)(1+\mathbb{E}[X|HH])+\mathbb{P}(T)(1+\mathbb{E}[X|HT])=\frac{1}{2}(1+\mathbb{E}[X|HH])+\frac{1}{2}(1+\mathbb{E}[X|HT])
\end{equation}
From here we can see that $\mathbb{E}[X|HH]=0$ because we already see the pattern, and $\mathbb{E}[X|HT])=\mathbb{E}[X])$ since we need to start over again. The equation (3) will be 
\begin{equation}
\mathbb{E}[X|H]=\frac{1}{2}(1+0)+\frac{1}{2}(1+\mathbb{E}[X])=1+\frac{1}{2}\mathbb{E}[X]
\end{equation}
So equation (2) will be 
\begin{equation}
\mathbb{E}[X]=\frac{1}{2}(1+\mathbb{E}[X|H])+\frac{1}{2}(1+\mathbb{E}[X])=\frac{1}{2}(1+(1+\frac{1}{2}\mathbb{E}[X]))+\frac{1}{2}(1+\mathbb{E}[X])=\frac{1}{2}(2+\frac{1}{2}\mathbb{E}[X]))+\frac{1}{2}(1+\mathbb{E}[X])
\end{equation}
After multiplying by 8 both sides we get
\begin{equation}
8\mathbb{E}[X]=4(2+\frac{1}{2}\mathbb{E}[X]))+4(1+\mathbb{E}[X])=8+2\mathbb{E}[X]))+4+4\mathbb{E}[X])\Rightarrow 2\mathbb{E}[X] =12\Rightarrow \mathbb{E}[X] =6
\end{equation}

## Theoritical result

Lets denote $\mathbb{E}_N$ for $N$ consecutive heads. With the same logic above, if we get one more head after $\mathbb{E}_{N-1}$, then we are done because we would have $N$ consecutive heads.  But if it is a tail then  we need to start over again. Thus there are two cases:

If we have a head, $\mathbb{E}_{N-1}+1$.

If we have a tail, $\mathbb{E}_{N}+1$.

\begin{equation}
\mathbb{E}_{N}= \mathbb{P}(H)(\mathbb{E}_{N-1}+1)+\mathbb{P}(T)(\mathbb{E}_{N-1}+\mathbb{E}_{N}+1)=\frac{1}{2}(\mathbb{E}_{N-1}+1)+\frac{1}{2}(\mathbb{E}_{N-1}+\mathbb{E}_{N}+1)
\end{equation}
Multiply by 2 both sides to get 
\begin{equation}
\mathbb{E}_{N}=2\mathbb{E}_{N-1}+2
\end{equation}

## Python code for simulation


```python
def expect(n):
    if n == 0:
        return 0

    return 2*expect(n-1)+2
```


```python
expect(2)
```




    6




```python
expect(3)
```




    14




```python
expect(4)
```




    30




```python
expect(5)
```




    62




```python
expect(11)
```




    4094




```python
expect(100)
```




    2535301200456458802993406410750




```python

```

da15b9ffeeb72cb8f5931f6613c1a5a64b7df76d
ipynb
Jupyter Notebook
Expected number of flips until N heads March 6 2021.ipynb
sernur/probability_stats_interveiw_questions
3144dae00fa83c82ff4e1f7668828349270a1937
MIT
2021-03-04T06:48:28.000Z
2021-04-19T10:04:24.000Z
Expected number of flips until N heads March 6 2021.ipynb
sernur/probability_stats_interveiw_questions
3144dae00fa83c82ff4e1f7668828349270a1937
MIT
2021-03-05T22:00:43.000Z
2021-03-05T22:00:43.000Z
Expected number of flips until N heads March 6 2021.ipynb
sernur/probability_stats_interveiw_questions
3144dae00fa83c82ff4e1f7668828349270a1937
MIT
2021-03-04T05:02:00.000Z
2021-03-16T01:13:40.000Z
Qwen/Qwen-72B
1. YES
2. YES