# Number of walks on 2D grid

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?

• +1 The really hard problem here is that there are certain partial walks which lead to no further possible walks, such as when you walk yourself into a dead end near the grid's edge, or spiral yourself in. So it becomes less than trivial to determine the number of permutations. – Engineer Oct 14 '11 at 13:59
• Total number of walks on infinite grid is obviously (4 ^ N). The problem is to find walks that leave our grid. – man Oct 14 '11 at 14:20
• @Nick: You seem to be assuming that the path can’t intersect itself, but the statement of the problem imposes no such restriction. – Brian M. Scott Oct 14 '11 at 20:50
• Yes. No restrictions on self-intersection. – man Oct 14 '11 at 20:59
• I don’t know whether this is at all useful, but your problem is equivalent to the following problem. Let $A=\{a,b,c,d\}$. For $w\in A^*$ let $h(w)=|w|_b-|w|_a$ and $v(w)=|w|_d-|w|_c$. For $u,w\in A^*$ write $u\preceq w$ iff $u$ is an initial segment of $w$. Given integers $m_0<m_1$ and $n_0<n_1$ and a positive integer $k$, what is $$|\{w\in A^k:\forall u\preceq w[m_0\le h(u)\le m_1\land n_0\le v(u)\le n_1]\}|\;?$$ – Brian M. Scott Oct 14 '11 at 21:04

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.

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.