## 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}$.