2

If I start a random walk at (a, b) in the x-y plane (say, 5, 5), how do I calculate the probability that the first time I hit the y axis, I land on a positive y value?

I am not sure how to go about calculating this -- I just read the Wikipedia article on random walks and it didn't give me enough intuitive information to start working on this problem. I realize the probability must be > 1/2 if b > 0 because of the initial bias in the positive y-direction.

My initial thought was to calculate a radius of all possible destinations within some number of time steps, and take the ratio of reachable points on the positive y axis to all reachable points on the y axis as my answer, but I don't know if this approach is correct. If anyone can give me some tips I can work on it more.

rxmnnxfpvg
  • 103

1 Answers1

1

For every $a\geqslant1$, you are asking for $$P(\text{positive landing point})=P(H_1+H_2+\cdots+H_a\geqslant-b+1)$$ where $(H_k)$ is i.i.d. and distributed as $H$ the ordinate of the hitting point of the $y$-axis by the random walk starting at $(1,0)$.

The trouble is that the distribution of $H$ has no nice closed form. However, one can describe it, through a conditioning on the first step of the random walk.

This yields that $H$ is distributed as $1$ with probability $\frac14$, $H+1$ with probability $\frac14$, $H-1$ with probability $\frac14$, and $H'+H''$ with probability $\frac14$, where $H'$ and $H''$ are independent copies of $H$. Thus, for every real number $t$, $$4E(e^{itH})=1+e^{it}E(e^{itH})+e^{-it}E(e^{itH})+E(e^{itH})^2$$ Solving the quadratics, one gets $$E(e^{itH})=2-\cos t-\sqrt{(1-\cos t)(3-\cos t)}$$ or, equivalently,

$$E(e^{itH})=1+2\sin^2(t/2)-2|\sin(t/2)|\sqrt{1+\sin^2(t/2)}$$

One can extract from this formula the full distribution of $H$, albeit not in a quite explicit form, since, for every integer $k$, $$2\pi P(H=k)=\int_{-\pi}^\pi E(e^{itH})e^{-ikt}dt$$ Likewise, $$2\pi P(H_1+H_2+\cdots+H_a=k)=\int_{-\pi}^\pi E(e^{itH})^ae^{-ikt}dt$$ Finally, using the fact that $E(e^{itH})$ is real valued, one gets $$ P(H_1+H_2+\cdots+H_a>-b)=\frac1{2\pi}\int_0^\pi E(e^{itH})^a\frac{\sin((b-1/2)t)}{\sin(t/2)}dt$$ or, equivalently,

$$ P(\text{positive landing point})=\int_0^{\pi/2} \left(1+2\sin^2(t)-2\sin(t)\sqrt{1+\sin^2(t)}\right)^a\frac{\sin((2b-1)t)}{\sin(t)}\frac{dt}\pi$$

Did
  • 279,727