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$.

  • 2
    $\begingroup$ 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. $\endgroup$ – 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, \begin{equation} P(Q)=P_1+P_2, \end{equation} 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 \begin{equation} P(Q)=\frac{1}{2N}. \end{equation}

Here we used the Markov property of the walk and the formula \begin{equation} P(\tau_{x,b}<\tau_{x,a})=\frac{x-a}{b-a} \end{equation} for any distinct integers $a,b$ and any integer $x$ between $a$ and $b$; cf. e.g. Theorem 4 for $p=1/2$.

  • $\begingroup$ How come you don't get the same result as @AnthonyQuas? I can't immediately tell why myself. $\endgroup$ – Vilhelm Agdur Dec 21 '18 at 15:46
  • $\begingroup$ @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. $\endgroup$ – Iosif Pinelis Dec 21 '18 at 19:29
  • $\begingroup$ It was my mistake. I read $c_N^-$ as the hitting time of $-N-1$. $\endgroup$ – Anthony Quas Dec 22 '18 at 17:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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