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

Call the normalization constant $K$ to distinguish it from the moment index used later. A probability density function must have total integral one, soTherefore $K=\theta c^{\theta }$, the value denoted $k$ in the density. This is the Pareto distribution with scale $c$ and shape $\theta$.

For $x\le c$, the cumulative distribution function is zero. For $x>c$, integrate the normalized probability density function:It is continuous at $c$, increases to one, and is the cumulative distribution function of the stated Pareto distribution.

Write $r$ for a positive integer moment index. The moment isThis improper integral converges exactly when $r-\theta -1<-1$, namely $r<\theta$. For those indices,At $r=\theta$ the divergence is logarithmic; for $r>\theta$ it is a power divergence. Thus, in the source's moment notation, the positive integers $k$ allowed are exactly $k<\theta$. If $\theta \le 1$, no positive integer moment is finite.

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.