HMMT February, 2020

Solution:

In all solutions, $p=\frac{1}{25}$ will denote the probability that the coin is blown away. Let $D=|H-T|$. Note that if $D \neq 0$, the expected value of $D$ is not changed by a coin flip, whereas if $D=0$, the expected value of $D$ increases by $1$. Therefore $\mathbf{E}(D)$ can be computed as the sum over all $n$ of the probability that the $n$th coin flip occurs when $D=0$. This only occurs when $n=2k+1$ is odd, where the probability that the first $n$ coin flips occur is $(1-p)^{2k+1}$ and the probability that $D=0$ after the first $n-1$ flips is $\frac{\binom{2k}{k}}{4^k}$. Therefore
$$\begin{aligned} \mathbf{E}(D) & =(1-p) \sum_{k=0}^{\infty}\left(\frac{1-p}{2}\right)^{2k}\binom{2k}{k} \\ & =\frac{1-p}{\sqrt{1-(1-p)^{2}}} \end{aligned}$$
using the generating function
$$\sum_{k=0}^{\infty}\binom{2k}{k} x^{k}=\frac{1}{\sqrt{1-4x}}$$
Plugging in $p=\frac{1}{25}$ yields $\mathbf{E}(D)=\frac{24}{7}$.

Solution:

For each $n \geqslant 0$, the probability that Max made $n$ successful throws (not counting the last throw) is $p(1-p)^{n}$.

Claim: Assuming Max made $n \geqslant 1$ throws, the expected value of $|H-T|$ is given by
$$\prod_{k=1}^{\lfloor(n-1)/2\rfloor} \frac{2k+1}{2k}.$$

Proof. If $n$ is odd then the expected value for $n+1$ will be equal to that for $n$; since $|H-T|$ will be nonzero, it will be equally likely to increase or decrease after the coin is flipped. Therefore, it suffices to compute the expected value for the $n$ odd case. This is
$$\begin{aligned} \frac{\sum_{i=0}^{(n-1)/2}\binom{n}{i} \cdot (n-2i)}{2^{n-1}} & = n - \frac{\sum_{i=0}^{(n-1)/2}\binom{n}{i} \cdot 2i}{2^{n-1}} \\ & = n \cdot \left(1 - \frac{2 \cdot \sum_{i=0}^{(n-3)/2}\binom{n-1}{i}}{2^{n-1}}\right) \\ & = n \cdot \frac{\binom{n-1}{(n-1)/2}}{2^{n-1}} \end{aligned}$$
$$\begin{aligned} & = \frac{n!}{(n-1)!!^{2}} \\ & = \frac{n!!}{(n-1)!!} \\ & = \prod_{k=1}^{(n-1)/2} \frac{2k+1}{2k} \end{aligned}$$
as desired.

Using the claim, we have
$$\begin{aligned} \mathbf{E}(|H-T|) & = p\left(\sum_{n=1}^{\infty}(1-p)^{n} \prod_{k=1}^{\lfloor(n-1)/2\rfloor} \frac{2k+1}{2k}\right) \\ & = p(1-p)(2-p) \sum_{m=0}^{\infty}\left((1-p)^{2m} \prod_{k=1}^{m} \frac{2k+1}{2k}\right) \\ & = p(1-p)(2-p)\left(1-(1-p)^{2}\right)^{-3/2} \\ & = \frac{1-p}{\sqrt{p(2-p)}}. \end{aligned}$$
Plugging in $p=\frac{1}{25}$ gives
$$\mathbf{E}(|H-T|) = \frac{24}{25} \cdot 5 \cdot \frac{5}{7} = \frac{24}{7}.$$

Solution:

Let $E_{n}$ be the expected value of $|H-T+n|$. By symmetry, $E_{-n}=E_{n}$ for all $n$. Considering what happens in the next throw gives
$$2E_{n} = (1-p)E_{n-1} + (1-p)E_{n+1} + 2pn$$
for all $n \geqslant 0$. Now let $\alpha = \frac{1-\sqrt{p(2-p)}}{1-p} < 1$ be the smaller root of $(1-p)x^{2} - 2x + (1-p) = 0$. From
$$\begin{aligned} \sum_{n=1}^{\infty} 2\alpha^{n} E_{n} & = \sum_{n=1}^{\infty} \alpha^{n}\left((1-p)E_{n-1} + (1-p)E_{n+1} + 2pn\right) \\ & = \alpha(1-p)E_{0} + (2\alpha - (1-p))E_{1} + \sum_{n=1}^{\infty} 2pn\alpha^{n} + \sum_{n=2}^{\infty} 2\alpha^{n}E_{n} \end{aligned}$$
we have
$$(1-p)E_{1} - \alpha(1-p)E_{0} = \sum_{n=1}^{\infty} 2pn\alpha^{n} = \frac{2p\alpha}{(1-\alpha)^{2}}$$
As $E_{0} = (1-p)E_{1}$, this gives
$$E_{0}(1-\alpha(1-p)) = \frac{2p\alpha}{(1-\alpha)^{2}}$$
Plugging in $p=\frac{1}{25}$ and $\alpha=\frac{3}{4}$ gives $E_{0}=\frac{24}{7}$.