Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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

share|cite|improve this answer
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) – MrRoth Feb 26 '12 at 11:13
I did. Please check the link. – Did Feb 26 '12 at 11:17
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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