Notes of Antoine Gournay’s lecture nr 1

Compression and random walks

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

\displaystyle  \begin{array}{rcl}  \alpha_Y(X)=\sup\{\alpha\in(0,1)\,;\,\exists f:X\rightarrow Y\textrm{ such that }\omega_f(t)\leq At+B,\,\rho_f(t)\geq\frac{t^\alpha}{A}-B\}. \end{array}

1. Main results

1.1. Random walks

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

Example. On {Cay({\mathbb Z},\{\pm1\})}, the distribution at time {n} is binomial centered at 0.

In general, for a Cayley graph {Cay(G,S)}, the distribution at times {n} is the push-forward of the uniform measure on {S^n} under the walk map

\displaystyle  \begin{array}{rcl}  (s_1,\ldots,s_n)\mapsto s_1\cdots s_n. \end{array}

It can be viewed a the distribution of the product {\prod_{i=1}^{n}\sigma_i} where {\sigma_i} are independant uniformly distributed random varibles with values in {S}. Thus it is an iterated convolution of probability measures {\mu^{\star n}}.

1.2. Walking on {{\mathbb Z}^d}

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 {G} be a finitely generated group. The probability of returning to the origin decays exponentially fast if and only if {G} is non amenable.

{G} is non amenable if there is a constant {c>0} such that every finite set {A} satisfies

\displaystyle  \begin{array}{rcl}  |A|\leq c|\partial A|. \end{array}

Here, {g\in\partial A} if {g\in A} and some neighbour {gs\notin A}.

1.4. Speed

The speed of a random walk {(W_n)} on a group is the function

\displaystyle  \begin{array}{rcl}  n\mapsto \mathop{\mathbb E}(d(W_n,e)). \end{array}

This is always at most {n}. The lower speed exponent is

\displaystyle  \begin{array}{rcl}  \beta_{G,S}=\sup\{c\in[0,1]\,;\,\exists K>0,\,\mathop{\mathbb E}(d(W_n,e))\geq K?,n^c\}. \end{array}

Unknown wether this depends on generating system {S} or not.

Example. {G={\mathbb Z}^d} with usual generating system. The distribution at times {n} is approximated by a Gaussian distribution with mean 0 and whose variance is linear in {n}. With probability close to 1, {W_n} is at distance {\Theta(\sqrt{n})}, therefore the speed exponent is {\frac{1}{2}}.

Example. {G=F_2}, free group on 2 generators. View the tree as a rooted tree. Let {W_n} denote the random walk, {Z_n} its distance from the origin. Then {Z_n} is the random walk where probability of going to the right is {3/4}, and probability of going to the left is {1/4}. Again, the distribution of {Z_n} is binomial {\mathcal{B}(n,3/4)}, with mean {n/2}, it is approximated by a Gaussian of mean {n/2} and variance {3n/16}. With probability close to 1,

\displaystyle  \begin{array}{rcl}  |W_n-\frac{n}{2}|=\Theta(\sqrt{\frac{3n}{4}}). \end{array}

Therefore speed is linear in {n}, {\beta=1}.

These are the only easy examples I know.

Fact. {\beta=\frac{1}{2}} for nilpotent, polycyclic… groups.

Fact. {\beta=\frac{3}{4}} for the lamplighter group {{\mathbb Z}\wr{\mathbb Z}} with infinitely many lamps.

Fact. {\beta=1} for the lamplighter group on {{\mathbb Z}^3}, {{\mathbb Z}_2\wr{\mathbb Z}^3}.

Fact. {\beta=1} 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 {G} be an amenable group. Assume that Banach space {B} has Markov type {p}. Then

\displaystyle  \begin{array}{rcl}  p\alpha_{B}(G)\hat{\beta}\leq 1, \end{array}

where {\hat{\beta}=\sup_S \beta_{G,S}}.

Markov type will be discussed at length this week. For instance {L^q} has Markov type {\min\{2,q\}}.

The theorem gives an easy way to estimate {\beta}. 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 {Y} is a stochastic process {(Z_n)} such that

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(Z_{n+1}=y|Z_n=y_n,\ldots,Z_0=y_0)=\mathop{\mathbb P}(Z_{n+1}=y|Z_n=y_n), \end{array}

i.e. The future depends on the past only via the present position. It is stationary if the distribution {\pi_n} of {Z_n} does not depend on {n}. It is reversible if furthermore

\displaystyle  \begin{array}{rcl}  \pi(y)K(y,x)=\pi(x)K(x,y). \end{array}

Example. If {Y} is a finite graph, the random walk with initial distribution

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(Z_0=y)=\frac{deg(y)}{|edges|} \end{array}

is a reversible stationary Markov chain.

Definition 4 A Banach space {B} has Markov type {p} if for every reversible and stationary Markov chain on {Y} and for every map {f:Y\rightarrow B},

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(d(f(Z_n),f(Z_0))^p)\leq Kt\mathop{\mathbb E}(d(f(Z_1),f(Z_0))^p). \end{array}

If {p=2}, this says that walks diverge as if some kind of Central Limit Theorem would hold.

2.2. Questions

Which values can {\beta} take ? A theorem of Virag states that {\beta\geq 1/2} always. The observed values are 1 and {1-2^{-k}}, {k\geq 1}. 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 {\alpha}.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s