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.

  • $\begingroup$ math.stackexchange.com/questions/1672956/… $\endgroup$ – d.k.o. Jul 18 '18 at 22:36
  • $\begingroup$ @d.k.o. In this problem, tails returns you back to 1, so this is not a random walk. $\endgroup$ – E-A Jul 18 '18 at 22:42
  • $\begingroup$ @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) $\endgroup$ – E-A Jul 18 '18 at 22:46
  • 1
    $\begingroup$ @E.A. Oh, I misread the question! $\endgroup$ – d.k.o. Jul 18 '18 at 22:46
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ But the correct answer is $\frac{1 - p^{M-1}}{p^{M-1}}$ $\endgroup$ – 3x89g2 Jul 19 '18 at 2:45
  • $\begingroup$ @3x89g2 Indeed, $$ \frac{1-p^{M-1}}{p^{M-1}}=p^{-M+1}-1. $$ $\endgroup$ – d.k.o. Jul 19 '18 at 3:11
  • $\begingroup$ Sorry. I meant, how do we get $E T_M$? Why $\frac{p^{-M+1} - 1}{1-p}$? $\endgroup$ – 3x89g2 Jul 19 '18 at 3:15
  • $\begingroup$ @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}. $$ $\endgroup$ – d.k.o. Jul 19 '18 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.