1

Let $X_1,X_2,X_3,\cdots$ variables i.i.d., such that $P(X_1=2)=1/2=P(X_1=-1)$ Let $S_n=X_1+\cdot+X_n$ consider stopping time $\tau=\{n\geq 1:S_n=10, \ or\ S_n=-10\}$. If $E(\tau )=8$. Compute $P(S_\tau = 10)$.

How can I approach this problem, as start?

apa
  • 385
  • 1
    Maybe you can solve by converting problem to Gambler's ruin problem. Say that in each game you either win 2 dollars or lose 1 dollar with probability 1/2. Game ends when you win 10 dollars or lose 10 dollars.

    Next let $q_i$ represent the probability that you win 10 dollars before losing 10 dollars having won $i$ dollars ($-10 < i < 10$).

    Then, $q_{-10} = 0$, $q_{10}=1$, $q_i = \frac{q_{i-1}}{2} + \frac{q_{i+2}}{2}$.

    Final answer you need is $P(S_n = 10) = q_0$

     – Snowball May 08 '21 at 17:50
  • @Snowball but why $E(\tau)=8$ is given in the problem? Can that recursion $q_0$ be solved using the probabilities given? – apa May 08 '21 at 18:05
  • I am not exactly sure. Btw, what happens when get 11? Do we stop or continue? – Snowball May 08 '21 at 18:12
  • @Snowball Good question one stop I think we can solve it with $\leq$ rather than $=$. – apa May 08 '21 at 18:15
  • In the Mitzenmacher and Upfal's probability and computing book pg 181 (2nd edition), it solves Gambler's ruin problem first using Markov chain and then solves using the method I specified above.

    In the first one, they use expected winning after $t$ rounds where $t\to\infty$ and it is zero (in original problem winning is 1, not 2). Since eventually game should end, final expected value is $l_1q - l_2(1-q)=0$. In this problem, maybe we can say expected stop time is 8 and then after 8 rounds, expected winning is 4, so $10q - 10(1-q)=4$, so $q = 0.7$

     – Snowball May 08 '21 at 18:37
  • @Snowball Thanks I think this might help – apa May 08 '21 at 19:01

0 Answers0