# Expected number of tail before $T_M$.

We flip a coin with head probability $p$. Before the game starts, we have 1 dollars. Each time we flip the coin, if it's head, then our fortune increases by 1; if it's tail, then our fortune returns to 1. Let $S_i$ be our fortune at $i$-th trial (so $S_0 = 1$).

Let $T_M = \min\left\{i: S_i = M \right\}$. Find the expected value of tails before $T_M$, $\mathbb{E}\left[ \sum_{i=1}^{T_M} 1_{Tail}\right]$

I tried to use Wald's identity since $T_M$ is a stopping time, but I still need to find $\mathbb{E}\left[T_M\right]$. I'm not sure how to find it. My vague thought is to use geometric random variable, with the event "getting $M-1$ heads in row" as success (having probability $p^{M-1}$), but I'm not sure how to proceed.

• math.stackexchange.com/questions/1672956/… – d.k.o. Jul 18 '18 at 22:36
• @d.k.o. In this problem, tails returns you back to 1, so this is not a random walk. – E-A Jul 18 '18 at 22:42
• @d.k.o. In asymmetric random walk, the sum either goes up or down by 1. (So, if I have 5 mesos at time $i$, I would now have 4 or 6 mesos.) Here, tails takes you back to 1. (So, I either have 6 mesos or one meso) – E-A Jul 18 '18 at 22:46
• @E.A. Oh, I misread the question! – d.k.o. Jul 18 '18 at 22:46
• Also OP, yes, your intuition should work; you will have success after on average $p^{-(M-1)}$ streaks of heads, and number of expected trials is precisely the number of tails you have. – E-A Jul 18 '18 at 22:50

It requires $M-1$ consecutive heads to stop. The expected number of steps until $M-1$ consecutive heads is given by $$\mathsf{E}T_M=\frac{p^{-M+1}-1}{1-p}.$$
Then the expected number of tails is $(1-p)\mathsf{E}T_M=p^{-M+1}-1$.
• But the correct answer is $\frac{1 - p^{M-1}}{p^{M-1}}$ – 3x89g2 Jul 19 '18 at 2:45
• @3x89g2 Indeed, $$\frac{1-p^{M-1}}{p^{M-1}}=p^{-M+1}-1.$$ – d.k.o. Jul 19 '18 at 3:11
• Sorry. I meant, how do we get $E T_M$? Why $\frac{p^{-M+1} - 1}{1-p}$? – 3x89g2 Jul 19 '18 at 3:15
• @3x89g2 If $E_n$ is the average number of steps until the first run of $n$ heads, then it satisfies the following relation: \begin{align} E_n&=(1-p)(1+E_n)+p(1-p)(2+E_n)+\cdots+p^nn \\ &=E_n-p^nE_n+\sum_{k=0}^{n-1}p^k. \end{align} So $$E_n=\sum_{k=0}^{n-1}\frac{p^k}{p^n}=\frac{p^{-n}-1}{1-p}.$$ – d.k.o. Jul 19 '18 at 3:29