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

  • 0
    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)2012-02-26
  • 0
    I did. Please check the link.2012-02-26
  • 0
    not talking about the approximation. about the first formula. doesn't the formula refer to the probability of a distance greater than $\sqrt{n}$2012-02-26
  • 0
    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}$.2012-02-26
  • 0
    by what you are saying, since this is symmetric then the $k$ should start $k=n-\sqrt{n}$ and end at $k=n$, then we simply multiply everything by two. correct?2012-02-26
  • 0
    ooopsy forgot, and then take its complimentary.2012-02-26
  • 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