# Simple random walk hitting time asymptotic behavior

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.

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!

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