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 .
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 2 The speed is at least linear iff there are non constant harmonic functions on the Cayley graph.
Theorem 3 Let be an amenable group. Assume that Banach space has Markov type . Then
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 4 A 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.
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 .