7
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Mar 15, 2010 at 5:25
  • $\begingroup$ 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. $\endgroup$
    – Gjergji Zaimi
    Commented Mar 15, 2010 at 7:43
  • $\begingroup$ 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? $\endgroup$
    – Jason Reed
    Commented Mar 15, 2010 at 21:05

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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)$ ? $\endgroup$
    – Robin Chapman
    Commented Mar 15, 2010 at 7:41
  • $\begingroup$ Yes, that's close to the second-to-last displayed equation, but I'd still need to relate $p_n$ and $q_n$. $\endgroup$
    – Douglas Zare
    Commented Mar 15, 2010 at 8:04
  • $\begingroup$ 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)$. $\endgroup$
    – Douglas Zare
    Commented Mar 15, 2010 at 18:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .