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$ Dec 20, 2018 at 16:14

1 Answer 1


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$ Dec 21, 2018 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$ Dec 21, 2018 at 19:29
  • $\begingroup$ It was my mistake. I read $c_N^-$ as the hitting time of $-N-1$. $\endgroup$ Dec 22, 2018 at 17:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .