# About a pattern of hitting times for a simple random walk

Let $$\omega_1, \omega_2, \ldots$$ be uniform iid on $$\{-1,1\}$$, and let $$X_n = \sum_{i=0}^n \omega_i$$ be the corresponding simple random walk. Fix some integer $$N$$, and let $$h^+_N$$ be the first time $$X_n$$ hits $$N$$, $$h^-_N$$ the hitting time of $$-N$$, $$c^-_N$$ the hitting time of $$-(N-1)$$, and finally let $$e^+_N$$ be the hitting time of $$N+1$$. Let $$Q$$ be the event that $$h^+_N < h^-_N$$ and $$c^-_N < e^+_N$$.

What is $$\mathbb{P}(Q)$$? I don't necessarily need an exact formula, just to know how it behaves as $$N$$ grows big.

The picture here is that if $$Q$$ occurs, then the random walk either first hits $$N$$ before bounding back to hit $$-(N-1)$$, or it very nearly hits $$-N$$ before bounding back to hit $$N$$. Either way it makes a "big swing". You could also think of the event $$Q$$ as containing (half of) the boundary between hitting $$N$$ first and hitting $$-N$$ first, inside the big set $$\{-1,1\}^\infty$$.

• It’s $1/(4N+4)$: this is $\mathbb P(h_N^+<h_N^-).\mathbb P(c_N^-<e_N^+|h_N+<h_N^-)$. The first term is $1/2$ and the second is the probability of hitting $-(N+1)$ before $N+1$ given that you started at $N$. This is exactly $1/(2N+2)$: look up hitting times for gambler’s ruin. – Anthony Quas Dec 20 '18 at 16:14

Let $$\tau_{x,y}$$ be the first hitting time of $$y$$ starting from $$x$$ at time $$0$$. Let $$\tau_y:=\tau_{0,y}$$. Then the conditions $$h^+_N < h^-_N$$ and $$c^-_N < e^+_N$$ can be rewritten as $$\tau_N<\tau_{-N}$$ and $$\tau_{1-N}<\tau_{N+1}$$. So, $$$$P(Q)=P_1+P_2,$$$$ where \begin{align} P_1&:=P(\tau_{1-N}<\tau_N<\tau_{-N}) \\ &=P(\tau_{1-N}<\tau_N)P(\tau_{1-N,N}<\tau_{1-N,-N}) \\ &=\frac{N}{2N-1}\,\frac{1}{2N}, \end{align} \begin{align} P_2&:=P(\tau_N<\tau_{1-N}<\tau_{N+1}) \\ &=P(\tau_N<\tau_{1-N})P(\tau_{N,1-N}<\tau_{N,N+1}) \\ &=\frac{N-1}{2N-1}\,\frac{1}{2N}, \end{align} so that $$$$P(Q)=\frac{1}{2N}.$$$$
Here we used the Markov property of the walk and the formula $$$$P(\tau_{x,b}<\tau_{x,a})=\frac{x-a}{b-a}$$$$ for any distinct integers $$a,b$$ and any integer $$x$$ between $$a$$ and $$b$$; cf. e.g. Theorem 4 for $$p=1/2$$.
• @VilhelmAgdur : I did re-check this answer a couple of times. On the other hand, I don't understand the comment by Anthony Quas; in particular, I am wondering why $1−N$ does not seem to play a role there. – Iosif Pinelis Dec 21 '18 at 19:29
• It was my mistake. I read $c_N^-$ as the hitting time of $-N-1$. – Anthony Quas Dec 22 '18 at 17:28