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?

$\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$ 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$ 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
    Mar 15, 2010 at 21:05

1 Answer 1

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.

$\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$ 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$ 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$ Mar 15, 2010 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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