From: greg@math.ucdavis.edu (Greg Kuperberg)
Subject: Re: Random Walk on a 2D square lattice
Date: 26 Jul 1999 10:55:09 -0700
Newsgroups: sci.math.research

In article <3798C80D.11965C9@wolfram.com>,
Michael Trott  <mtrott@wolfram.com> wrote:
>Are closed form expressions for the probability (of a random walker on a
>2D square lattice) of being at lattice point {i, j} after t time steps
>known?

If you mean the random walk in which the walker moves up, right, left,
or down, then the way to solve the problem is to rotate by 45 degrees.
Then the walker is going NE, NW, SE, or SW, which means that each
coordinate is independently executing a random walk in 1D, for which
the answer is a binomial coefficient.  Thus the answer for yours is a
product of binomial coefficients.

More explicitly, the probability is

    (t choose (i+j+t)/2) (t choose (i-j+t)/2) / 4^t

or 0 if i+j+t is odd.

If you mean a more general random walk in which the walker chooses from
some finite set of steps, then there is no simple formula even in one
dimension, although in any dimension there is a somewhat tautological
formula for the generating function.
-- 
  /\  Greg Kuperberg (UC Davis)
 /  \
 \  / Visit the Math Archive Front at http://front.math.ucdavis.edu/
  \/  * From Andrews to Zeilberger, Abramovich to Zaidenberg *