## Interview question: what is the expected number of occurrences of a “HH” pattern in n tosses of an unbiased coin?

Problem: You toss a fair coin $n$ times. What is the expected number of occurrences of HH pattern?
Math solution.
Let $E_{n}$ to denote the expectation we are looking for. Let $E_n^H$ to denote the conditional expectation given that the first toss is Head. Conditioning on the first toss, we get
$E_n = \frac{1}{2} E_{n-1} + \frac{1}{2} E_n^H$
Conditioning on the outcome of the second toss:
$E_n^H = \frac{1}{2}E_{n-2} + \frac{1}{2}(1 + E_{n-1}^H)$
Plugging this equation into previous one, we get
$E_n = \frac{1}{2} E_{n-1} + \frac{1}{2} (\frac{1}{2}E_{n-2} + \frac{1}{2}(1 + E_{n-1}^H))$
We can use the first equation to express $E_{n-1}^H$ in terms of $E_{n-1}$ and $E_{n-2}$ to get recursion:
$E_n = \frac{1}{4} + E_{n-1}$
It has solution:
$E_n = \frac{(n - 1)}{4}$
We could have arrived to this solution in a much easier way.
Physics solution.
It is very reasonable to conjecture that $E_n$ should be a linear function in $n$. If the assumption is correct, we can write two boundary conditions which are easy to compute: $E_1 = 0,\; E_2 = \frac{1}{4}$. From this we get the same solution as above.
Why $E_n$ must be linear? This can be shown as follows:
Let $X_i = 1$ if $i$-th toss begins the HH pattern; $X_i = 0$ otherwise. The number of HH patterns is $N = \sum\limits_{i=1}^n X_i$.
$E[N]= \sum\limits_{i=1}^n E[X_i] = \sum\limits_{i=1}^{n-1} E[X_i] = \sum\limits_{i=1}^{n-1} P(X_i = 1) = p(n - 1)$
Here we used that $P(X_n = 1) = 0$, and that $P(X_i = 1)$ is constant for $i < n$. This shows that $E_n$ is a linear function in $n$. We can see that linearity directly arises from the linearity of expectation, and from the fact that $N$ can be represented as a sum of indicator random variables with expectations that do not depend on the position (except for the last one).