= Solution
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:
$$
\boxed{\mathbb E\left[\sum_{j=1}^nX_j\right]=\frac n2.}
$$
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> gives
$$
p_i=\frac12p_{i-1}+\frac12p_{i+1},\qquad 1\le i\le n-1.
$$
Thus $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 is
$$
\boxed{p_i=\frac in.}
$$
For 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.
Back to article page
