# Random (drunkard) walk distance after $n$ steps

I am tying to analyze a random walk on an integer lattice $\mathbb{Z}^k$. For $k=1$, what is the probability that after $n$ steps the drunkard's distance from the origin is lower than $\sqrt{n}$?

The exact values $$2^{-n}\sum_{k=\frac12(n-\sqrt{n})}^{k=\frac12(n+\sqrt{n})}{n\choose k}$$ are not easily computed except for small values of $n$ but their limit when $n\to\infty$ is known and given by the gaussian approximation $$\sqrt{2/\pi}\int_0^1\mathrm e^{-x^2/2}\mathrm dx=\mathrm{erf}(1/\sqrt2)=0.682689...$$
• not talking about the approximation. about the first formula. doesn't the formula refer to the probability of a distance greater than $\sqrt{n}$ – MrRoth Feb 26 '12 at 11:19
• Some halves were missing, sorry about that. The argument is that, if $k$ steps are to the right and $n-k$ to the left, the position is $2k-n$, and one wants this to be between $-\sqrt{n}$ and $+\sqrt{n}$. – Did Feb 26 '12 at 11:29
• You asked for the probability to be at distance at most $\sqrt{n}$ after $n$ steps. The formula in my post provides that. – Did Feb 27 '12 at 17:31