Past exam of the mathematics course of the University of Cambridge / 2011 / ia / Paper 2 / 10F (Probability)

For any nonnegative random variable $X$ with finite expectation and any $a>0$, Markov's inequality statesIndeed $X\ge a{1}_{\{X\ge a\}}$, and taking expectations proves the bound. Nonnegativity is essential.

Each waiting time has the geometric distribution on $1,2,\dots$ with success probability $1/2$: a wait of length $n$ consists of $n-1$ failures followed by the prescribed success, so its probability is $2^{-n}$. HenceDisjoint successive blocks of independent tosses give independent waiting times. More explicitly, any specified list of block lengths determines exactly one allowed sequence of heads and tails and has probability $2^{-{\sum }_j(h_j+t_j)}$, the product of the individual block probabilities.

There are $2r$ waiting times. Multiplication of their probability generating functions and addition of their expectations giveTo recover its probability mass function, expand by the negative binomial series:The coefficient of $s^n$ is thereforeand it is zero below $2r$. Equivalently there are $\left(\genfrac{}{}{0ex}{}{n-1}{2r-1}\right)$ compositions of $n$ into $2r$ positive block lengths, each with probability $2^{-n}$. This is the negative binomial distribution for a sum of geometric waiting times, even though the desired outcome alternates between blocks.

For $r=1$,Since $\mathbb{E}{Y}_1=4$, Markov's inequality gives $\mathbb{P}(Y_1\ge 5)\le 4/5$, and indeed $5/16<4/5$.