3
$\begingroup$

I am stuck on this question,

"In a symmetric random walk of a particle on integer number line, starting from origin, what is the probability that it hits $-9$ before $+6$"

Here symmetric implies: P(going left at each step) = 1/2 and ditto for going right.

I could not think of a method for this, I just know that the expected number of steps to reach an integer $k$ can be defined recursively as:

Let $f(k)$ denote the expected number of steps starting from $k$,

$f(0)$ = $\frac{1}{2}$$(1+f(-1))$ + $\frac{1}{2}$$(1+f(1))$

In general, $f(k)$ = $\frac{1}{2}$$(1+f(k-1))$ + $\frac{1}{2}$$(1+f(k+1))$

But how do I relate this or without relating this to the required probability. Please help me with this. Thanks in advance!

PS: Please excuse me for the poor LaTeX syntax, I'm new to it.

$\endgroup$
2
$\begingroup$

You are asking yourself "how many steps?" when the question is "is position $-9$ reached before $+6$?".

Instead, consider $g(k)$ as this probability starting at $k$. You now have $$g(k) = \tfrac12 g(k-1)+\tfrac12 g(k+1)$$ and the boundary values $$g(-9)=1,g(+6)=0$$ which you should be able to solve

If you were really interested in the number of steps until you stop, the boundary values are $f(-9)=0,f(+6)=0$ and the solution is a little more complicated (you get a quadratic function of $k$, with $f(0)=54$ and it not a coincidence that $54=6\times 9$)

$\endgroup$
  • $\begingroup$ Sure I can solve the above set of equations, but it will give me the probability that I reach -9 starting from 0, and not P(I've reached -9 given I've not reached +6) or the probability of reaching -9 before reaching +6. Can you please elaborate over this? $\endgroup$ – Mohit Aneja Aug 8 '18 at 17:23
  • $\begingroup$ I defined $g(k)$ as the probability of reaching $-9$ before reaching $+6$ if you start from $k$. So $g(0)$ is precisely the result you want $\endgroup$ – Henry Aug 8 '18 at 17:27
  • $\begingroup$ Solving this I get $f(0)$ as $\frac{6}{15}$. Just one more question, is there a way to intuitively solve this? since the final results indicate the the probability is ratio of distance from the other end mod$(-6)$ / total distance $(15)$. Many thanks for clarifying this much already! $\endgroup$ – Mohit Aneja Aug 8 '18 at 17:36
  • $\begingroup$ Let's call $K$ the position at some stage, whether or not you have stopped. Since the steps are equally likely to be left or right, starting from $0$ you have $E[K]=0$ at all times. So if you eventually (with probability $1$) end up at $-9$ or $+6$ then the respective probabilities must be in the ratio $6:9$ to keep the expected position zero, making the probabilities $\frac{6}{6+9}$ and $\frac{9}{6+9}$. See Wikipedia for similar ideas $\endgroup$ – Henry Aug 8 '18 at 17:58
  • $\begingroup$ Thanks a lot @Henry. You explained it really well. $\endgroup$ – Mohit Aneja Aug 8 '18 at 18:06

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.