HMMT-Feb 2020 comb, Problem 10

Max repeatedly throws a fair coin in a hurricane. For each throw, there is a $4 \%$ chance that the coin gets blown away. He records the number of heads $H$ and the number of tails $T$ before the coin is lost. (If the coin is blown away on a toss, no result is recorded for that toss.) What is the expected value of $|H-T|$ ?

Solution: Solution 1: (Dilhan Salgado) 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=2 k+1$ is odd, where the probability that the first $n$ coin flips occur is $(1-p)^{2 k+1}$ and the probability that $D=0$ after the first $n-1$ flips is $\frac{\left(\begin{array}{c}2 k \\ k\end{array}\right)}{4^{k}}$. Therefore \[ \begin{aligned} \mathbf{E}(D) & =(1-p) \sum_{k=0}^{\infty}\left(\frac{1-p}{2}\right)^{2 k}\left(\begin{array}{c} 2 k \\ k \end{array}\right) \\ & =\frac{1-p}{\sqrt{1-(1-p)^{2}}} \end{aligned} \] using the generating function \[ \sum_{k=0}^{\infty}\left(\begin{array}{c} 2 k \\ k \end{array}\right) x^{k}=\frac{1}{\sqrt{1-4 x}} \] Plugging in $p=\frac{1}{25}$ yields $\mathbf{E}(D)=\frac{24}{7}$. Solution 2: 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{2 k+1}{2 k} \] 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}\left(\begin{array}{c} n \\ i \end{array}\right) \cdot(n-2 i)}{2^{n-1}} & =n-\frac{\sum_{i=0}^{(n-1) / 2}\left(\begin{array}{c} n \\ i \end{array}\right) \cdot 2 i}{2^{n-1}} \\ & =n \cdot\left(1-\frac{2 \cdot \sum_{i=0}^{n-3) / 2}\left(\begin{array}{c} n-1 \\ i \end{array}\right)}{2^{n-1}}\right) \\ & =n \cdot \frac{\left(\begin{array}{c} n-1 \\ (n-1) / 2 \end{array}\right)}{2^{n-1}} \end{aligned} \] \[ \begin{aligned} & =\frac{n !}{(n-1) ! !^{2}} \\ & =\frac{n ! !}{(n-1) ! !} \\ & =\prod_{k=1}^{(n-1) / 2} \frac{2 k+1}{2 k} \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{2 k+1}{2 k}\right) \\ & =p(1-p)(2-p) \sum_{m=0}^{\infty}\left((1-p)^{2 m} \prod_{k=1}^{m} \frac{2 k+1}{2 k}\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 3: 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 \[ 2 E_{n}=(1-p) E_{n-1}+(1-p) E_{n+1}+2 p n \] 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}-2 x+(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}+2 p n\right) \\ & \left.=\alpha(1-p) E_{0}+\alpha^{2}(1-p) E_{1}+\sum_{n=1}^{\infty} 2 p n \alpha^{n}+\sum_{n=2}^{\infty}\left((1-p) \alpha^{n-1}+(1-p) \alpha^{n+1}\right)\right) E_{n} \\ & =\alpha(1-p) E_{0}+(2 \alpha-(1-p)) E_{1}+\sum_{n=1}^{\infty} 2 p n \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} 2 p n \alpha^{n}=\frac{2 p \alpha}{(1-\alpha)^{2}} \] As $E_{0}=(1-p) E_{1}$, this gives \[ E_{0}(1-\alpha(1-p))=\frac{2 p \alpha}{(1-\alpha)^{2}} \] Plugging in $p=\frac{1}{25}$ and $\alpha=\frac{3}{4}$ gives $E_{0}=\frac{24}{7}$. $\fbox{\frac{24}{7}}$.

Answer: \frac{24}{7}