What is the number of N step random walks starting from a point (x0,y0) to a point (x1,y1) assuming each direction (right,left,up,down) has equal probability. I know the expression for the one dimension case is:
$$ \binom{N}{\frac{N+(y1-y0)}{2}} $$
is there a similar expression for two dimensions?
I saw this post (Probability Distribution of a 2D lattice random walk) but the answer given is clearly wrong.
Best Answer
The linked answer has a formula, but I wanted to provide a different perspective. I am generalizing the method used by Brian M. Scott in this answer.
Suppose the vertices your walk visits are $(x_0,y_0),(x_1,y_1),\dots,(x_N,y_N)$. (I am using different notation for the final vertex). Note that
The sums $x_0+y_0, x_1+y_1,\dots,x_N+y_N$ are a one-dimensional random walk from $x_0+y_0$ to $x_N+y_N$. This is because the values change by $\pm1$ each time.
The differences $x_0-y_0,x_1-y_1,\dots,x_N-y_N$ are also a $1$D random walk from $x_0-y_0$ to $x_N-y_N$.
Any pair of $1$D random walks can be generated in this fashion. You just need to check that the four possible choices of north, south, east and west for the $2$D walk generate all possible pairs of $\pm1$ for the two $1$D walks described above.
It follows that the number of $2$D random walks is the product of the number of ways to complete these two $1$D random walks, which is $$ \binom{N}{\frac12({N+x_0+y_0-x_N-y_N})}\times \binom{N}{\frac12({N+x_0-y_0-x_N+y_N})}. $$