MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If I'm not in error, the number of walks on a 2-dimensional integer lattice of length 2n steps from the origin to a point (x,y) has a nice closed form:

${2n \choose n + (x + y)/2}{2n \choose n + (x - y)/2}$

Question: Is there a similar closed form for the number of walks from the origin to (x,y), where a chosen "forbidden" point ($x_f$, $y_f$) is disallowed from ever appearing anywhere in a walk?

More generally, note that without the forbidden point, for a fixed length, a uniformly randomly chosen walk of that length is asymptotically Gaussian distributed. This sort of gives us a way of seeing how the $\ell_2$ norm on the euclidean plane arises as we "zoom out" while looking at the lattice and let the lattice size go to zero; that is, since the Gaussian distribution gives equal probabilities for equal $\ell_2$ distances from the origin.

A further, vaguer question is: how does forbidding a point --- removing it from the lattice --- affect the "effective" notion of distance that arises in the analogous way from the combinatorics of paths?

share|cite|improve this question
Depending on your interpretation of "similar," my guess is "no." The reason is that there is a natural way to write down a generating function that answers your first question, but to do something similar for the second question one must throw away certain terms when expanding a product, which is "unnatural" from the generating function point of view. In other words, the generating function approach ignores the order in which a walk is taken. Since you have to take order into account, a generating function-based approach is unlikely to work, and these are the ones giving "similar" answers. – Qiaochu Yuan Mar 15 '10 at 5:25
In the scaling limit, are you talking about the Gaussian free field? Can you elaborate a little? GFF only works for paths with no self intersection. If so then there is a generalization to annuli, punctured planes or any surface for that matter. – Gjergji Zaimi Mar 15 '10 at 7:43
Gjergji: I don't see how nonselfintersection is required. I'm just relying on the binomial coefficients converging to the Gaussian distribution in the limit, aren't I? – Jason Reed Mar 15 '10 at 21:05

First, let me confirm your formula for walks $(0,0) \xrightarrow{m}(x,y)$ with $x+y\equiv m ~\mod 2$, $p_m(x,y)$, which you stated for $m=2n$.

Choose $(m+x+y)/2$ out of $m$ steps $s_i$ to be $(+1/2,+1/2)$ versus $(-1/2,-1/2)$.

Choose $(m+x-y)/2$ out of $m$ steps $t_i$ to be $(+1/2,-1/2)$ versus $(-1/2,+1/2)$.

Then letting $w_i = s_i + t_i$, $(w_i)$ are the steps of a walk $(0,0) \xrightarrow{m}(x,y)$ with steps of $(\pm 1,0)$ or $(0,\pm 1)$.

Second, let me fill in some details for the generating function approach.

Any walk $(0,0) \xrightarrow m (x,y)$ either avoids $(x_f,y_f)$, or it can be broken into $3$ pieces:

$(0,0) \xrightarrow t (x_f,y_f)$ which first visits $(x_f,y_f)$ at the end,

$(x_f,y_f) \xrightarrow {2u} (x_f,y_f)$ of size ${2u \choose u}^2$.

$(x_f,y_f) \xrightarrow {m-t-2u} (x,y)$ which last visits $(x_f,y_f)$ at the start.

The first and third pieces have the same form reversed in time. Let $q_n(a,b)$ be the number of paths $(0,0)\xrightarrow n (a,b)$ which only visit (a,b) at the end.

$$\sum_n p_n(a,b)x^n = \bigg(\sum_n q_n(a,b)x^n\bigg)\bigg(\sum_n \sideset{}{^{^{^2}}}{2n \choose n} x^{2n}\bigg)$$

$$\sum_n q_n(a,b)x^n = \sum_{n} p_n(a,b)x^n \bigg/\sum_n \sideset{}{^{^{^2}}}{2n \choose n} x^{2n}$$

So, a generating function for walks $(0,0) \to (x,y)$ which visit $(x_f,y_f)$ is

$$\bigg(\sum_n q_n(x_f,y_f)x^n\bigg)\bigg( \sum_nq_n(x-x_f,y-y_f)x^n\bigg)\bigg(\sum_n \sideset{}{^{^{^2}}}{2n \choose n} x^{2n}\bigg)$$

$$=\bigg(\sum_n p_n(x_f,y_f)x^n\bigg)\bigg( \sum_nq_n(x-x_f,y-y_f)x^n\bigg)$$

$$=\bigg(\sum_n p_n(x_f,y_f)x^n\bigg)\bigg( \sum_np_n(x-x_f,y-y_f)x^n\bigg)\bigg/\sum_n \sideset{}{^{^{^2}}}{2n \choose n} x^{2n}$$

You want to subtract this from $\sum_n p_n(x,y)x^n$.

I don't see a closed form expression for the coefficients.

share|cite|improve this answer
Can't you get this slightly quicker by splitting into two pieces: from $(0,0)$ to the first visit to $(x_f,y_f)$, and a general path from $(x_f,y_f)$ to $(x,y)$ ? – Robin Chapman Mar 15 '10 at 7:41
Yes, that's close to the second-to-last displayed equation, but I'd still need to relate $p_n$ and $q_n$. – Douglas Zare Mar 15 '10 at 8:04
By the way, it seems like it should be known how likely it is that a random walk will visit $(x,y)$ before it visits $(x_f,y_f)$. – Douglas Zare Mar 15 '10 at 18:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.