Given n flips, what is the expected number of times the sequence HT shows up?

Question

Suppose a fair coin is flipped $n$ times - what is the expected number of appearances of the sequence HT?

I know it's $\sqrt n$, can anyone provide an explanation why this is true?

Answer 1

Consider all sequences of n Hs and Ts. How many HTs are there in all?

---

Not the simplest argumen but an instructive one:

Construct a directed graph with vertices $TT$, $TH$, $HT$, $TT$, and an edge from the vertex $xy$ to the vertices $yH$ and $yT$ (here $x$ and $y$ are either $H$ or $T$) A path starting at the vertex $TH$ of length $n$ in this graph corresponds precisely to a sequence in $H$ and $T$ of length $n+2$ starting with $TH$, and similarly for other starting vertices; for example, the path $TH\to HH\to HH\to HT\to TT$ corresponds to the sequence $THHHTT$.

Now introduce a variable $q$, and consider the matrix $$B=\begin{pmatrix}1&0&1&0\\q&0&q&0\\0&1&0&1\\0&1&0&1\end{pmatrix},$$ the the column vector $w=(1,q,1,1)$ and the row $\def\uu{\mathbf1}\uu=(1,1,1,1)$. Now the $i$th entry of the vector $B^nw$ is a polynomial in $q$ such that the coefficient of $q^r$ in it is the number of sequences of length $n+2$ of $H$s and $T$s which have exactly $r$ appearances of $TH$. You can prove this by induction.

Similarly, $\uu B^n w$ is a polynomial in $q$ such that the coefficient of $q^r$ is the number of sequences of length $n+2$ of $H$s and $T$s which contain exactly $r$ appearances of $TH$. Then $\def\d{\tfrac{\mathrm d}{\mathrm dq}}2^{-(n+2)}\d(\uu B^nw)\big|_{q=1}$ is the expected number $\alpha_{n+2}$ of $TH$s in sequences of length $n+2$.

Consider next the series $F(t,q)=\tfrac14\sum_{n\geq0}\uu B^n wt^n/2^n$. This can be rewritten simply as $$F(t,q)=\tfrac14\uu(1-Bt/2)^{-1} w$$ and from this we can actually compute that $$F(t,q)=\frac{-q (t+1)+t-3}{t ((q-1) t+4)-4}.$$ It follows that $$\d F(t,q)=\frac{4}{\left((q-1) t^2+4 t-4\right)^2}$$ and evaluating this at $q=1$ we get $$\d F(t,q)\big|_{q=1}=\frac{1}{4 (t-1)^2}=\tfrac14\sum_{n\geq0}(n+1)t^n$$ and we therefore conclude that the number we are after is $$\alpha_n=\frac{n-1}4.$$

Answer 2

By symmetry, the occurrences of HT and TH will, on average, be the same. Therefore we can find the expected number of both and then average the two.

Clearly the way to get either a HT or a TH is to switch the event. After the first flip, we will switch on average $$\frac{n-1}{2}$$ times. Dividing this in half gives $$\text{Expected HT}=\frac{n-1}{4}$$ which is consistent with the $3.75=(16-1)/4$ that I got in my simulation (see the comment I put on the post).

Following the argument suggested by Mariano, there are $2^n$ possible sequences in all. If we fix the $i$'th spot and demand that a HT occurs there, we are free to pick the other $n-2$ spots however we like, so the probability of any given spot having the HT is just $$\frac{2^{n-2}}{2^n}=\frac{1}{4}$$ Since there are $n-1$ possible spots, we get $$\frac{n-1}{4}$$ again as the expected value.

I also ran a test with $25$ flips and got $\approx 6$ which is $(25-1)/4$ so I think your formula is incorrect or some kind of approximation.

Answer 3

For $k=1$ to $n-1$, let $X_k=1$ if we get an H on the $k$-th toss and a T on the $(k+1)$-th toss. Then the number of times HT appears is $X_1+X_2+\cdots+X_{n-1}$.

If $X$ is the number of appearances of HT, then $X=X_1+\cdots+X_{n-1}$, so by the linearity of expectation we have $E(X)=E(X_1)+\cdots+E(X_{n-1})$.

Easily, $E(X_i)=\frac{1}{4}$, since $\Pr(X_i=1)=\frac{1}{4}$.

Thus $E(X)=\frac{n-1}{4}$.

Answer 4

With probability ${1\over2}$ the next toss will be different from the previous one, and there are $n-1$ places where such a change can occur. Therefore we may expect ${n-1\over2}$ changes in all, and half of them will be $HT$, by symmetry.