Let $p(n,t)$ be the probability that a simple random walk starting at state $n$ hits $0$ within $t$ steps.

How big can $p(n,t(n))$ get for large $n$ when $t(n) = o(n^2)$? It seems like maybe it could be $e^{-o(n^2/t)}$, since you also get to count paths that hit $0$ but end positive.


1 Answer 1


For a symmetric random walk with standard derivation $1$, start at $x_0$ at $t = 0$. The probability distribution of it landing at $x_1$ for large time $t$ is approximately given by:

$$P[\,x(t) = x_1|x(0) = x_0] = \frac{1}{\sqrt{2\pi t}}e^{ -\frac{(x_1-x_0)^2}{2t} }$$

For large $t$, $p(n,t)$ is known to be about twice the probability for $x(t) \le 0$ at time $t$ and can be expressed in terms of the complementary error function. i.e.

$$\begin{align}p(n,t) &\sim 2 P[\,x(t) \le 0| x(0) = n]\\ &\sim 2\int_{-\infty}^0 \frac{dx}{\sqrt{2\pi t}} e^{ -\frac{(x-n)^2}{2t} } = 2\int_{-\infty}^{-n} \frac{dx}{\sqrt{2\pi t}} e^{-\frac{x^2}{2t}}\\ &= \textrm{erfc}(\frac{n}{\sqrt{2t}})\end{align}$$ The relation $p(n,t) \sim 2P[\,x(t) \le 0|x(0) = n]$ can be proved using the reflection principle for Bronwian motion. Unluckily, I can't find any good explanation how this is done on the web. I hope this is a start.

EDIT about the factor of two.

In the expression of $p(n,t)$, the factor of two in front of $P[\,x(t) \le 0|x(0) = n]$ isn't that surprising. If one enumerate all possible history of a random walk between time $\tau = 0$ to $\tau = t$. Those walks which have hitted state $0$ at a time $\tau \le t$ falls into 3 classes. Namely, those with $x(t) < 0, = 0 \textrm{ and } > 0$. For large $t$, the case for $x(t) = 0$ is much less probable than the other two. Because the walk is symmetric, the case for $x(t) > 0$ and for $x(t) < 0$ has exactly the same probability!

  • $\begingroup$ Thanks! It's good to know that you can only get an extra factor of two. $\endgroup$
    – abc
    Mar 1, 2013 at 10:28
  • $\begingroup$ @abc, there is a reason for the factor of two. see update of the answer. $\endgroup$ Mar 1, 2013 at 11:46

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.