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

  • $\begingroup$ since this is a "base" question, can you please elaborate or provide a reference for your solution? (i am interested in this simple case, and for k>1) $\endgroup$ – MrRoth Feb 26 '12 at 11:13
  • $\begingroup$ I did. Please check the link. $\endgroup$ – Did Feb 26 '12 at 11:17
  • $\begingroup$ not talking about the approximation. about the first formula. doesn't the formula refer to the probability of a distance greater than $\sqrt{n}$ $\endgroup$ – MrRoth Feb 26 '12 at 11:19
  • $\begingroup$ 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}$. $\endgroup$ – Did Feb 26 '12 at 11:29
  • 1
    $\begingroup$ You asked for the probability to be at distance at most $\sqrt{n}$ after $n$ steps. The formula in my post provides that. $\endgroup$ – Did Feb 27 '12 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.