Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 7 / b

Let $E_0$ be the expected additional flips when there is no immediately preceding tail, and $E_1$ the expectation when the preceding flip is a tail. A one-step first-step analysis givesSolving gives $E_1=4$ and $\mathbb{E}[F]=E_0=6$. To justify finiteness before manipulating these expectations, split the flips into independent two-flip blocks. Each block has probability $1/4$ of being $TT$; hence $\mathbb{P}(F>2m)\le (3/4{)}^m$. This geometric tail bound from a uniform escape probability makes the expectation finite. The state $E_1$ is essential because successive possible pairs overlap: the waiting time is not itself a geometric distribution with parameter $1/4$.

Write $G(s)=\mathbb{E}[s^F]$. The initial possibilities are $H$ with probability $1/2$, after which a fresh wait begins; $TH$ with probability $1/4$, after which a fresh wait begins; or $TT$ with probability $1/4$, which ends the experiment. Accounting for the flips already made in each case gives the probability generating function equationTherefore $G_F(s)=\frac{s^2}{4-2s-s^2}$ for $0\le s\le 1$. In particular, $G_F(1)=1$ and there is no mass below two flips, as required.

Set $D(s)=4-2s-s^2$, so $D(s)G(s)=s^2$. Differentiate once and evaluate at $s=1$, using $D(1)=1$, $D^{\prime }(1)=-4$, $G(1)=1$:A second differentiation gives $D^{\prime \prime }G+2D^{\prime }{G}^{\prime }+D{G}^{\prime \prime }=2$, henceThe derivatives of a probability generating function give $G^{\prime }(1)=\mathbb{E}[F]$ and $G^{\prime \prime }(1)=\mathbb{E}[F(F-1)]$. Consequently $\mathrm{Var}(F)=52+6-6^2=22$. The earlier geometric tail bound from a uniform escape probability ensures the needed moments are finite.