6
$\begingroup$

Suppose we are on a finite 2D grid of points from $(0,0)$ to $(a,b)$. Each turn we can move up/down/left/right on this grid (we have 3 possible moves on edges and 2 on corners). In the beginning we are at the point $(x_0,y_0)$ inside the grid. How many ways are there to make $N$ steps on the grid?

I know a recursive solution when the number of ways to make $N$ steps is sum of number of ways to make $N-1$ steps from cell to the left/right/up/down. I wonder is there a combinatorial solution?

  • 0
    The answer to this question http://math.stackexchange.com/questions/17972/probability-of-never-reach-1-for-a-1d-random-walk-of-n-steps which uses reflection principle might be helpful but I can't extend it to the second bound and 2D.2011-10-14

2 Answers 2

1

I don't know of a combinatorial solution, but I do know a trick...

The number of $n$-step walks starting at $(x,y)$ that don't leave the grid is obviously the total number of $n$-step walks ($4^n$) times the probability $p_n(x,y)$ that a random $n$-step walk started at $(x,y)$ doesn't leave the grid.

What is that probability? Obviously, $p_0(x,y) = \chi(x,y)$, where $\chi(x,y)$ equals $1$ inside the grid and $0$ on the points surrounding it. For higher $n$, we have the recurrence relation $p_{n+1}(x,y) = \chi(x,y) \frac{p_n(x-1,y) + p_n(x+1,y) + p_n(x,y-1) + p_n(x,y+1)}{4}.$

Except for the $\chi(x,y)$ term, this is almost a convolution, and by making use of the fact that the grid is rectangular, we can get rid of the unwanted term by extending $p_0$ suitably beyond the edges of the grid.

Here it turns out to be much more convenient to let the grid extend from $(1,1)$ to $(a-1, b-1)$, so I'm going to adopt that convention, and then define $p_0(x,y) = f(x)g(y)$, where $f(x) = \begin{cases} \phantom{+}0 & \text{if }x = ka, k \in \mathbb Z \\ \phantom{+}1 & \text{if }(2k+0)a < x < (2k+1)a, k \in \mathbb Z \\ -1 & \text{if }(2k+1)a < x < (2k+2)a, k \in \mathbb Z \end{cases}$ $g(y) = \begin{cases} \phantom{+}0 & \text{if }y = kb, k \in \mathbb Z \\ \phantom{+}1 & \text{if }(2k+0)b < y < (2k+1)b, k \in \mathbb Z \\ -1 & \text{if }(2k+1)b < y < (2k+2)b, k \in \mathbb Z.\end{cases}$

It is then not hard to show that, even if we drop the $\chi(x,y)$ term from the recurrence, $p_n(x,y) = 0$ whenever $x$ is divisible by $a$ or $y$ is divisible by $b$. Thus, we can calculate $p_{n+1}$ for $n \ge 0$ via the convolution $p_{n+1} = p_n * K$, i.e. $p_{n+1}(x,y) = \sum_{u,v \in \mathbb Z} p_n(x-u,y-v) K(u,v),$ where the kernel $K$ is given by $K(1,0) = K(0,1) = K(-1,0) = K(0,-1) = \frac 1 4$ and $K(u,v) = 0$ for all other values of $u$ and $v$.

Why would we want to do that? Well, it just happens that convolutions of discrete periodic functions can be efficiently calculated using discrete Fourier transforms. In particular, letting $\tilde p_n$ and $\tilde K$ denote the Fourier transforms of $p_n$ and $K$, we have $\tilde p_n = \tilde p_{n-1} \tilde K = \tilde p_0 \tilde K^n,$ where the multiplication is simply done pointwise.

0

Very elegant the answer of Ilmari. However, it seems that by this proceeding we also count the "degenerate" paths in following sense: suppose, for example, that we are at the step 1 and are at the point $(x_{1},y_{1})$ such that $x_{1} = x_{0}$ and $y_{1} = y_{0}+1$. Now, for the next step we can't move backward to the previous point $(x_{0},y_{0})$, otherwise $(x_{2},y_{2}) = (x_{0},y_{0}) $ and the trace of the path would only have two points $ \left \{ (x_{0},y_{0}), (x_{1},y_{1}) \right \}$. In the same manner, if , at each step we still have 4 possible moves, we would be counting these "degenerate" paths,i.e., those paths that after having made any number of movements, the trace is the same.