Introduction to Random Walks on Groups

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=(a₁,...,a_r), where a_i 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(a₁),...,s(a_r)), where sÎS is some permutation on J. Another shuffle would give the deck (t(s(a₁)),...,t(s(a_r))), 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(a_i)=j

p(a),

after two shuffles the probability will be

(a,b)Î A: b(a(a_i))=j

p(a)p(b).

If pⁿ denotes the nth convolution of p,

pⁿ(s)=

a_iÎ A: a_n°a_n-1°···°a₁=s

p(a_n)p(a_n-1)··· p(a₁),

the distribution of the position of the ith card after the nth shuffle is given by

µ_nⁱ=

sÎS

pⁿ(s)d_{s(a_i)},

where d_x is the Kronecker symbol at x: d_x(x)=1 and d_x(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 a_j 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

pⁿ(s)d_s,

with this notation µ_nⁱ(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:

the limit is independent of the initial state;
the limit is independent of the particular choice of the probability p;
the limit is the most disordered distribution m on S, i.e., the distribution with the maximal entropy H(m), with

H(m)=

å

sÎS
-m(s)log(m(s)).

2 Random Walks in Z^d

This random walk is defined as follows: starting from xÎZ^d, it jumps to x± e_i with probability 1/2d, where e_i is the ith unit vector. If S_n denotes the position after n steps it is well known that when d£ 2, the sequence (S_n) 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 Z^d is assumed to have resistance 1, R_d is the effective resistance of Z^d when the potential at 0 is 1 and 0 at infinity. It turns out that for d£ 2, R_d is infinite and R_d is finite when d³ 3.

The Laplacian D of the random walk is given by

D(f)(x)=

æ
ç
ç
è

i=1

(

f(x+e_i)+f(x-e_i)

)

ö
÷
÷
ø

-f(x),

where f is some function on Z^d. The potential function v(x) for the electrical network should satisfy D(v)=0 with v(0)=1 and lim_x®+¥v(x)=0.

3 Polymer Dynamics in the Plane

A simplified model of a polymer in the plane is given by a broken line A₀A₁... A_n where each segment A_iA_i+1 has length 1 and the angle between A_i-1A_i and A_iA_i+1 is ± aÎ[ 0,2p) with probability 1/2. If A₀=(0,0) and A₁=(1,0), the vector Z_n=A₀A_n can be represented in the complex plane as

Z_n=1+

k=1

e^{ia S_k},

where S_k=e₁+···+e_k and the e_i are independent Bernoulli random variables with P(e_i=1)=P(e_i=-1)=1/2; (S_n) is the simple random walk on Z. The average quadratic length of the polymer with N segments is given by

l_n=( E

(

Z_n²

)

)^1/2.

It has been shown by Eyring that l_n/(n)^1/2 converges to a constant as n tends to infinity. The average length is conjectured to grow like n^x 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 R³ on the unit sphere S² centered at 0 is analyzed. If l(a,b) is a product of n such rotations, one writes |l|=n. For pÎ S², the distribution µ_n of l(a,b)(p) is given by

µ_n=

2ⁿ

|l|=n

d_l(a,b)(p).

The problem is to determine when µ_n converges to the uniform distribution on S² 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 (x_n) is a sequence of G and e is the empty string (the neutral element of the group), the quantity

b(g,x)=

lim

x_n®x

(

d(g,x_n)-d(e,x_n)

)

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)=

(

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, h_x(g)=(1/3)^b(g,x) is harmonic with respect to this Laplacian, i.e., D(h_x)=0. Dynkin and Malyutov [4] have shown that every positive harmonic function f can be expressed as an integral of the elementary functions h_x, xÎ¶G, i.e.,

f(g)=

ó
õ

¶G

h_x(g) n(dx),

where n is a positive measure on ¶ G.

This situation has to be compared with the case of the random walks on Z^d 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 R^d, i.e., such that

i=1

¶²f

¶ x_i²

=0.

But restricted to the unit disc of R², such functions exist and can be represented as

ó
õ

P(z,q) n(dq),

where n is some finite measure on [ 0,2p) and P is the Poisson kernel

P(z,q)=

1-|z|²

|e^iq-z|²

One can check that z|® P(z,q) is harmonic: it is the equivalent of the function h_x 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 L^AT_EX by H^EV^EA.