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.
 A: 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! 
