Find the expected value of $|H-T|$

Question

Bob repeatedly throws a (fair) coin. For each throw, there is a $4\%$ chance that Bob decides to stop throwing the coin. He records the number of heads H and the number of tails T before he stops flipping the coin (if he decides to stop flipping the coin on a toss, he doesn't record anything for that toss). Find the expected value of $|H-T|$.

Let $p=1/25$.

I'm not sure whether the expected value of $|H-T|$ after n+1 throws given that it is nonzero after n throws equals the expected value after n throws. Note that the probability that $H-T < 0$ after n flips and the (n+1)st throw is an H equals the probability that $H-T > 0$ and the (n+1)st throw is a T (we can simply replace H's with T's in the corresponding sequences). Also, the probability $H-T < 0$ and the (n+1)st throw is a T equals the probability that $H-T>0$ and the (n+1)st throw is an H. Also, the probability $H-T < 0$ after n throws and the (n+1)st throw is an H equals the probability $H-T<0$ after n throws and the (n+1)st throw is a T. Let $I$ be an indicator random variable equal to $-1$ if $H-T < 0$ and the (n+1)st throw is an H or $H-T > 0$ and the (n+1)st throw is a T and $1$ if $H-T > 0$ and the (n+1)st throw is a T or $H-T < 0$ and the $(n+1)$st throw is an H. I'm not sure about how to proceed from here.

Alternatively, I think it should be possible to find the expected value of $|H-T|$ assuming $n$ tosses were performed directly from the definition, and then compute the desired expected value using the fact that the probability n successful flips were performed (not including the last flip) is $p(1-p)^n$. Now if i is nonzero, then the probability that $|H-T| = i$ equals the probability $H-T = i$ plus the probability $H-T = -i$. In the first case, since $H+T = n, H = \dfrac{n+i}2, T = \dfrac{n-i}2$ while in the second case, $H = \dfrac{n-i}2, T = \dfrac{n+i}2.$ And clearly the probability $|H-T| = 0$ is ${n\choose n/2}$ assuming n is even; if not the probability is zero. So the expected value of $|H-T|$ is just $1/2^n \sum_{i=1}^n 2 {n\choose \dfrac{n+i}2} i,$ where ${n\choose k} := 0$ if $n$ is an integer but k is not. In particular, if $n$ is odd, then the expected value is $\dfrac{1}{2^n} \sum_{i=0}^{(n-1)/2} 2{n\choose \dfrac{n+2i+1}2} (2i+1)$ while if n is even, the expected value is $\dfrac{1}{2^n} \sum_{i=1}^{n/2} 2{n\choose \dfrac{n+2i}2}(2i).$

Question: how can I simplify the latter expression or come up with the expected value using a different method?

By computing a few small values, it seems that the last expression actually equals $\prod_{i=1}^{\lfloor (n-1)/2\rfloor } \dfrac{2i+1}{2i}$. Let us call the latter assumption assumption (*). I'm not sure how to prove this, so I'll just assume this is true from now on.

We have \begin{align} E(|H-T|) &= p\sum_{n=1}^\infty (1-p)^n \prod_{i=1}^{\lfloor (n-1)/2\rfloor } (2k+1)/(2k))\\ &= p(\sum_{m=0}^\infty (1-p)^{2m+1} \prod_{k=1}^m \dfrac{2k+1}{2k} + \sum_{m=0}^\infty (1-p)^{2m+2} \prod_{k=1}^m \dfrac{2k+1}{2k}) \\ &= p(1-p)(2-p) \sum_{m=0}^\infty (1-p)^{2m} \prod_{k=1}^m \dfrac{2k+1}{2k} \\ &= p(1-p)(2-p) (1-(1-p)^2)^{-3/2}\\ &= (1-p)/\sqrt{p(2-p)}, \end{align}

and so plugging in $p=1/25$ gives that the expected value is $24/7$ under assumption (*).

Answer 1

I'm not simplifying OP's expression. Here is an alternative approach to showing that $$E_{n} |H-T| = \prod_{i=1}^{\lfloor (n-1)/2\rfloor } \dfrac{2i+1}{2i}.$$

We'd prove this by induction.
Let $A_n$ denote the act of throwing $n$ coins. We say that $ a_n = k$ if $|H-T| = k$. Let $ E_n$ denote the expected value of $|H-T|$ when throwing $n$ coins.

For $A_n$, first consider the cases where $ |H - T | =k > 0$.
Restricting to these cases, when we flip an additional coin, the expected value stays the same, namely $$E_{n+1} ( |H-T| \mid a_n = k ) = \frac{1}{2} (k+1) + \frac{1}{2} (k-1 ) = k = E_n ( a_n = k).$$

Let's first focus on an odd number of coin flips, and what happens when we add an additional coin flip.
$|H-T| $ is odd, so by Linearity of Iterated Expectation, $$ E_{2n} = \sum_{k=1}^{n} P(a_{2n-1} = 2k-1) \times E_{2n-1} (|H-T| \mid a_{2n-1} = 2k-1 ) \\ = \sum P(a_{2n-1} = 2k-1) E_{2n-1} ( a_{2n-1} = 2k-1 ) \\= E_{2n-1}.$$ Notice that $E_{2n} = E_{2n-1}$ is reflected in the closed form.

Now we focus on the $n=2k$ even number of coin flips, and what happens when we add an additional coin flip.
$|H-T|$ is even. We understand what happens when $|H-T| \geq 2$, so let's investigate when $|H-T| = 0$.
This occurs with probability $P(a_{2k} = 0 ) = \frac{2k \choose k } { 2^{2k}}$.
With the next coin flip, we have $|H-T| = 1$ always, so $E_{2k+1} ( |H-T| \mid a_{2k} = 0 ) = E_{2k} ( |H-T| \mid a_{2k} = 0 ) + 1$.
Thus, by Linearity of Iterated Expectation,

$$ E_{2n+1} = \sum_{k=0}^{n} P(a_{2n} = 2k) \times E_{2n+1} (|H-T| \mid A_{2n} = k )\\ = P(a_{2n} =0) + \sum_{k=0}^n P(a_{2n} = k) E_{2n} ( a_{2n}= k ) \\ = \frac{2k \choose k } { 2^{2k}} + E_{2n}.$$

By induction (check the math), $E_n$ has the closed form as given above.