** Compression and random walks **

Recall the definition of compression (see Baudier’s lecture).

**1. Main results **

** 1.1. Random walks **

Let be a graph with possibily (multiple) loops. The simple random walk on consists in jumping from a vertex to one of its neighbours picked uniformly at random. So the probability to jump from to is 0 if is not a neighbour, where is the number of edges joining to , the number of edges emanating from .

**Example**. On , the distribution at time is binomial centered at 0.

In general, for a Cayley graph , the distribution at times is the push-forward of the uniform measure on under the walk map

It can be viewed a the distribution of the product where are independant uniformly distributed random varibles with values in . Thus it is an iterated convolution of probability measures .

** 1.2. Walking on **

Polya, when walking in a park in Vienna, happened to meet a colleague several times. Puzzled, he computed the probability that two random walkers on a square grid will meet infinitesimally often is 1 in 2 dimensions, 0 in higher dimensions.

** 1.3. Walking on amenable groups **

Theorem 1 (Kesten 1949)Let be a finitely generated group. The probability of returning to the origin decays exponentially fast if and only if is non amenable.

is non amenable if there is a constant such that every finite set satisfies

Here, if and some neighbour .

** 1.4. Speed **

The *speed* of a random walk on a group is the function

This is always at most . The *lower speed exponent* is

Unknown wether this depends on generating system or not.

**Example**. with usual generating system. The distribution at times is approximated by a Gaussian distribution with mean 0 and whose variance is linear in . With probability close to 1, is at distance , therefore the speed exponent is .

**Example**. , free group on 2 generators. View the tree as a rooted tree. Let denote the random walk, its distance from the origin. Then is the random walk where probability of going to the right is , and probability of going to the left is . Again, the distribution of is binomial , with mean , it is approximated by a Gaussian of mean and variance . With probability close to 1,

Therefore speed is linear in , .

These are the only easy examples I know.

**Fact**. for nilpotent, polycyclic… groups.

**Fact**. for the lamplighter group with infinitely many lamps.

**Fact**. for the lamplighter group on , .

**Fact**. for all non amenable groups.

Theorem 2The speed is at least linear iff there are non constant harmonic functions on the Cayley graph.

Theorem 3Let be an amenable group. Assume that Banach space has Markov type . Then

where .

Markov type will be discussed at length this week. For instance has Markov type .

The theorem gives an easy way to estimate . For instance, the result about polycyclic groups is obtained in this way.

**2. Proof of the connection with Markov type **

** 2.1. Markov type **

A (time-independent) Markov chain on a set is a stochastic process such that

i.e. The future depends on the past only via the present position. It is *stationary* if the distribution of does not depend on . It is *reversible* if furthermore

**Example**. If is a finite graph, the random walk with initial distribution

is a reversible stationary Markov chain.

Definition 4A Banach space has Markov type if for every reversible and stationary Markov chain on and for every map ,

If , this says that walks diverge as if some kind of Central Limit Theorem would hold.

** 2.2. Questions **

Which values can take ? A theorem of Virag states that always. The observed values are 1 and , . However, if one looks into the finer behaviours of the speed functions, one sees a large variety.

Not much more is known about values of .