# Paper 2, Section II, F

(a) State Markov's inequality.

(b) Let $r$ be a given positive integer. You toss an unbiased coin repeatedly until the first head appears, which occurs on the $H_{1}$ th toss. Next, I toss the same coin until I get my first tail, which occurs on my $T_{1}$ th toss. Then you continue until you get your second head with a further $H_{2}$ tosses; then I continue with a further $T_{2}$ tosses until my second tail. We continue for $r$ turns like this, and generate a sequence $H_{1}, T_{1}, H_{2}, T_{2}, \ldots, H_{r}$, $T_{r}$ of random variables. The total number of tosses made is $Y_{r}$. (For example, for $r=2$, a sequence of outcomes $t t h|t| t t t h \mid h h t$ gives $H_{1}=3, T_{1}=1, H_{2}=4, T_{2}=3$ and $Y_{2}=11$.)

Find the probability-generating functions of the random variables $H_{j}$ and $T_{j}$. Hence or otherwise obtain the mean values $\mathbb{E} H_{j}$ and $\mathbb{E} T_{j}$.

Obtain the probability-generating function of the random variable $Y_{r}$, and find the mean value $\mathbb{E} Y_{r}$.

Prove that, for $n \geqslant 2 r$,

$\mathbb{P}\left(Y_{r}=n\right)=\frac{1}{2^{n}}\left(\begin{array}{c} n-1 \\ 2 r-1 \end{array}\right)$

For $r=1$, calculate $\mathbb{P}\left(Y_{1} \geqslant 5\right)$, and confirm that it satisfies Markov's inequality.