I have been trying to get an expression for a simple 2D symmetric lattice random walk. All moves have equal probabilities (moving up, down, left and right all have probabilities of 1/4). I tried to find an expression for the probability function, but I could not come up with a distribution that matches the walk. Would the 2D random walk just be a probability distribution of a solid, which occurs when you revolve the 1D binomial distribution around the y-axis?

Thanks for the help in advance.

  • $\begingroup$ As far as I know, there is no closed form for this probability function. $\endgroup$ – nicomezi Feb 23 '17 at 6:21
  • $\begingroup$ See also this question here. $\endgroup$ – Hypergeometricx Oct 25 '18 at 17:32

All we can say is that all paths are equally likely, so $\mathbb{P}[X(n)=x]=\frac{\text{# walks of length }n\text{ that terminate at }x}{4^n}$. As far as calculating the numerator, if $x=(a,b)$ and $s\geq |a|$, $n-s\geq |b|$, then the number of walks of length $n$ that terminate at $x$ and have $s$ horizontal movements are $\left(\begin{array}{c} s \\ \frac{s+|a|}{2}\end{array}\right)\left(\begin{array}{c} n-s \\ \frac{n-s+|b|}{2}\end{array}\right)$ (the first term is the number of ways you can space your movements in the $(a,0)$ direction with $s$ opportunities, the second is similar for vertical). So $\text{# walks of length }n\text{ that terminate at }x=\sum_{s=|a|}^{n-|b|}\left(\begin{array}{c} s \\ \frac{s+|a|}{2}\end{array}\right)\left(\begin{array}{c} n-s \\ \frac{n-s+|b|}{2}\end{array}\right)$, where we understand that the terms with fractional arguments are equal to 0. It's hard to get further than this without going round in circles, but this is usually enough to motivate a computer algorithm.


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.