From: David Bernier Subject: asymptotics of random walks on finitely generated groups Date: 7 May 1999 09:30:08 -0500 Newsgroups: sci.math.research Suppose G is an infinite group generated by {g_1, ... g_n}. The canonical random walk on G for this set of generators is a type of Markov process where a walk can be thought of as an infinite sequence X_0, X_1, .... of random variables taking values in G, with Prob [X_0 = e]=1 (e is the identity element of G), and with transition probabilities: Prob[ X_{t+1} = {[(g_i)^((\epsilon)_j)]*h} | X_t=h ] = 1/(2*n) for t=0,1,2,... , i=1 to n, j=1 to 2 and where (\epsilon)_j = (-1)^j. The case about which the most is known is, I believe, the family of groups Z^n with n generators and n=>1. For n=1 or 2, it is well-known (Polya) that the walk is recurrent , i.e. the probability of eventually returning to e is 1. For n=>3, the walk is non-recurrent. One can define, for n=>3, a potential function U:(Z^n)->R by U(x) = the expected number of visits at x from t= 0 to oo. U is in some sense "harmonic" in that the average of the 2n values U(g_1*x), U((g_1)^{-1}*x), .... U(g_n*x), U((g_n)^{-1}*x) is U(x) if x is not e (I am using '*' as the group operation where '+' would be more customary for commutative groups). If by |x| we mean the euclidean norm of x in Z^n, then I am almost sure that U(x) is O( |x|^(2-n) ) [x non-zero], by analogy with the the harmonic function U(y) = |y|^(2-n) in R^n (which has a singularity at the origin). We can also look at the n "discrete partial derivatives" defined by DU_i(x) = U(g_i * x)-U(x) (i=1,n). Again by analogy with the R^n case, I am almost sure that |DU_i(x)| is O(|x|^(1-n)) for non-zero x. For non-commutative finitely generated groups, I believe much less is known. For example, the discrete Heisenberg group of order 3 consisting of 3x3 upper-triangular matrices with 1's on the main diagonal and any three integers above the main diagonal has a polynomial growth rate of order four (cf. [1] below where a book by M. Gromov is cited about the "growth rate" concept). N. Th. Varopoulos has done work which implies interesting results about the asymptotics of the potential function U for groups including the order 3 discrete Heisenberg group (U(x) is defined, as for the case of the groups Z^n, as the expected number of visits at e for any x in G, G being an infinite finitely generated group; for some groups, U(x) may take on values of "oo".) As far as the asymptotics of the n discrete derivative functions of U are concerned, I would be interested in knowing what results are known for the non-commutative case. For the discrete Heisenberg group of order 3, some Monte Carlo computations I did around 1989 suggest that the asymptotics of the DU_i's are O(|x|^{-3}) for non-zero x. I never was able to prove this conjecture. Thanks in advance for any comments. David Bernier [1] Bernier, D.; ``Quasicentral approximate units for the discrete Heisenberg group", J. Operator Theory, 29, (1993), pp. 225-236. -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ============================================================================== From: "David Fischer" Subject: Re: asymptotics of random walks on finitely generated groups Date: 8 May 1999 16:30:05 -0500 Newsgroups: sci.math.research For the case of the continuous Heisenberg group and the Gaussian probability distribution you might want to take a look at "The Gaussian random walk on the Heisenberg group", Illinois Journal of Mathematics, Volume 24 Number 2, Summer 1980. You might also want to look at earlier work by Keane and Guivarc'h and later work by Andre Hulanicki.