1
$\begingroup$

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}$?

1 Answers 1

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... $

  • 1
    You 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