Introduction to Random Walks on Groups

Yves Guivarc'h

Irmar, Université Rennes 1 (France)

Algorithms Seminar

March 5, 2001

[summary by Philippe Robert]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).
Abstract
In this talk simple examples are presented to illustrate some aspects of random walks on groups from the point of view of probability theory, statistical physics, ergodic theory, harmonic analysis, and group theory.



1  Shuffling Cards

A deck of cards is described by J=(a1,...,ar), where ai indicates the position of the ith card in the deck. The cards are shuffled so that the state of the deck of cards is (s(a1),...,s(ar)), where sÎS is some permutation on J. Another shuffle would give the deck (t(s(a1)),...,t(s(ar))), and so on. Of course, the permutation is likely to be different from one shuffle to another, but the habits of a given player will be such that he will choose at random among a given set A of permutations. For aÎ A, the permutation a is chosen with probability p(a)>0. After a shuffle, the next permutation is chosen independently of the past. The position of the ith card is j after the first shuffle with probability
 
å
aÎ A: a(ai)=j
p(a),
after two shuffles the probability will be
 
å
(a,b)Î A: b(a(ai))=j
p(a)p(b).
If pn denotes the nth convolution of p,
pn(s)=
 
å
aiÎ Aan°an-1°···°a1=s
p(an)p(an-1)··· p(a1),
the distribution of the position of the ith card after the nth shuffle is given by
µni=
 
å
sÎS
pn(s)ds(ai),
where dx is the Kronecker symbol at x: dx(x)=1 and dx(y)=0 when y¹x. A natural question in this setting is: provided that the set A is rich enough, is the position of the card aj uniformly distributed on {1,...,r} when n gets large?

The distribution µn on S of the configuration of the deck of cards after n shuffles is given by
µn=
 
å
sÎS
pn(s)ds,
with this notation µni(j)=µn(s:s(i)=j). Does the distribution µn on S converges to the uniform distribution on the group of permutations as n gets large? The answer to both questions is positive if the probability p satisfies some assumptions. It can then be shown that the convergence to the uniform distribution is exponentially fast with n (see Diaconis [2]).

This simple problem gives an illustration of the ergodic principle introduced in statistical physics after the work of Boltzmann and Gibbs:

2  Random Walks in Zd

This random walk is defined as follows: starting from xÎZd, it jumps to x± ei with probability 1/2d, where ei is the ith unit vector. If Sn denotes the position after n steps it is well known that when d£ 2, the sequence (Sn) almost surely visits the origin infinitely often; the random walk is then said to be recurrent. When d³ 3 the random walks visits 0 only a finite number of times; the random walk is transient. These results can be expressed in terms of electrical networks: each edge of Zd is assumed to have resistance 1, Rd is the effective resistance of Zd when the potential at 0 is 1 and 0 at infinity. It turns out that for d£ 2, Rd is infinite and Rd is finite when d³ 3.

The Laplacian D of the random walk is given by
D(f)(x)=
1
2d
æ
ç
ç
è
d
å
i=1
( f(x+ei)+f(x-ei) ) ö
÷
÷
ø
-f(x),
where f is some function on Zd. The potential function v(x) for the electrical network should satisfy D(v)=0 with v(0)=1 and limx®+¥v(x)=0.

3  Polymer Dynamics in the Plane

A simplified model of a polymer in the plane is given by a broken line A0A1... An where each segment AiAi+1 has length 1 and the angle between Ai-1Ai and AiAi+1 is ± aÎ[ 0,2p) with probability 1/2. If A0=(0,0) and A1=(1,0), the vector Zn=A0An can be represented in the complex plane as
Zn=1+
n
å
k=1
eia Sk,
where Sk=e1+···+ek and the ei are independent Bernoulli random variables with P(ei=1)=P(ei=-1)=1/2; (Sn) is the simple random walk on Z. The average quadratic length of the polymer with N segments is given by
ln=( E ( Zn2 ) )1/2.
It has been shown by Eyring that ln/(n)1/2 converges to a constant as n tends to infinity. The average length is conjectured to grow like nx with x>1/2.

4  Random Rotations on the Sphere

This problem has been considered by Arnold and Krylov [1]. The action of two rotations a and b of R3 on the unit sphere S2 centered at 0 is analyzed. If l(a,b) is a product of n such rotations, one writes |l|=n. For pÎ S2, the distribution µn of l(a,b)(p) is given by
µn=
1
2n
 
å
|l|=n
dl(a,b)(p).
The problem is to determine when µn converges to the uniform distribution on S2 and, if it occurs, the rate of convergence. The answer to the first point is positive under mild assumptions. The question concerning the speed is, for the moment, unsolved. This example is in some sense, a continuous analogue of the example of card shuffling.

5  Random Walks on the Free Group

The free group with two generators a and b is denoted by G. An element g is a string of letters a, a-1, b and b-1 where a letter cannot be the inverse of the previous letter or the next letter in the string (otherwise the two letters cancel). The distance d(g,g') is given by the length of the string g-1g'. The group G can be compactified by adding the set G of infinite strings. If x is such a string and gÎG, it is easily seen that, if (xn) is a sequence of G and e is the empty string (the neutral element of the group), the quantity
b(g,x)=
 
lim
xn®x
( d(g,xn)-d(e,xn) )
is well defined.

The random walk considered here just adds a, a-1, b or b-1 at the end of the string, with the convention that the inverse of the last letter suppresses this letter. This random walk is equivalent to a random walk on a homogeneous tree with degree 4. In particular it is transient and the length of the string almost surely converges to infinity. The Laplacian D of this random walk is given by
D(f)(g)=
1
4
( f(g a)+f(g a-1)+f(g b)+f(g b-1) ) -f(g),
for gÎG and f a function on G. For xÎG, hx(g)=(1/3)b(g,x) is harmonic with respect to this Laplacian, i.e., D(hx)=0. Dynkin and Malyutov [4] have shown that every positive harmonic function f can be expressed as an integral of the elementary functions hx, xÎG, i.e.,
f(g)= ó
õ
 


G
hx(gn(dx),
where n is a positive measure on G.

This situation has to be compared with the case of the random walks on Zd with d³ 3 which are also transient but without non-constant positive harmonic functions. Similarly, in a continuous setting, there does not exist any non-constant positive harmonic function f on Rd, i.e., such that
d
å
i=1
2f
xi2
=0.
But restricted to the unit disc of R2, such functions exist and can be represented as
1
2p
ó
õ
2p


0
P(z,qn(dq),
where n is some finite measure on [ 0,2p) and P is the Poisson kernel
P(z,q)=
1-|z|2
|eiq-z|2
.
One can check that z|® P(z,q) is harmonic: it is the equivalent of the function hx for the unit disc.

References

[1]
Arnol'd (V. I.), Kozlov (V. V.), and Neishtadt (A. I.). -- Dynamical systems. III. -- Springer-Verlag, Berlin, 1988, xiv+291p. Mathematical Aspects of Classical and Celestial Mechanics. Translated from the Russian.

[2]
Diaconis (Persi). -- Group representations in probability and statistics. -- Institute of Mathematical Statistics, Hayward, CA, 1988, vi+198p.

[3]
Doyle (Peter G.) and Snell (J. Laurie). -- Random walks and electric networks. -- Mathematical Association of America, Washington, DC, 1984, xiv+159p.

[4]
Dynkin (E. B.) and Maljutov (M. B.). -- Random walk on groups with a finite number of generators. Doklady Akademii Nauk SSSR, vol. 137, 1961, pp. 1042--1045.

[5]
Guivarc'h (Yves). -- Marches aléatoires sur les groupes. In Development of mathematics 1950--2000, pp. 577--608. -- Birkhäuser, Basel, 2000.

[6]
Woess (Wolfgang). -- Random walks on infinite graphs and groups. -- Cambridge University Press, Cambridge, 2000, xii+334p.

This document was translated from LATEX by HEVEA.