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... $$
-
0since 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
-
0I did. Please check the link. – 2012-02-26
-
0not 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
-
0Some 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
-
0by 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
-
0ooopsy forgot, and then take its complimentary. – 2012-02-26
-
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