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 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 *