Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 5 / a / iii

Let $X_j$ be the indicator random variable that coin $j$ shows a head. Each expectation is $\mathbb{E}{X}_j=1/2$, so linearity of expectation gives the expected number of heads:For the game, write $p_i$ for the probability that $H$ eventually holds all $n$ coins when starting with $i$. The states $0,n$ are absorbing, so $p_0=0$ and $p_n=1$. Conditioning on the first toss and using the law of total probability givesThus $p_{i+1}-p_i=p_i-p_{i-1}$: successive differences are constant, and $p_i=A+Bi$. The boundary values give $A=0$, $B=1/n$, hence the gambler's ruin answer isFor completeness, the game terminates with probability one. From any nonabsorbing state, a run of $n$ consecutive heads would reach $n$ within the next $n$ tosses, and that run has probability $2^{-n}$. Conditional on survival, the same bound applies to the next block. Therefore the probability of surviving $kn$ tosses is at most $(1-2^{-n}{)}^k$, which tends to zero.