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}$?
Random (drunkard) walk distance after $n$ steps
1
$\begingroup$
probability
random-walk
1 Answers
2
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... $
-
1You asked for the probability to be at distance at most $\sqrt{n}$ after $n$ steps. The formula in my post provides that. – 2012-02-27