Notes of Yuval Peres’ 2014 lecture

The Poisson boundary of lamplighter groups

Joint with R. Lyons.

1. Entropy

The whole subject started with Kesten in 1949 and Furstenberg in early 50’s. Entropy on the boundary. In 1970, Avez proposed to define entropy directly on the group. Kaimanovich and Vershik (1979, 1983, Derriennic 1980.

Let {G} be generated by finite symmetric set {S}. Consider simple random walk on Cayley graph : jump to a neighbour picked uniformly at random. When the walk is transient,

– what are the bounded harmonic functions on the group ? Harmonic means {Ph=h}.

– what is the tail {\sigma}-field {\bigcap_n \sigma(X_n,X_{n+1},\ldots)} ?

In particular, when are all bounded harmonic functions constant ? When is the tail trivial ? This should be related to entropy.

1.1. Entropy


\displaystyle  \begin{array}{rcl}  H(X_n)=\sum_x p^n(e,x)\log(1/p(e,x)). \end{array}

Group invariance implies sub-additivity, so asymptotic entropy can be defined as

\displaystyle  \begin{array}{rcl}  h=\lim_{n\rightarrow\infty}\frac{1}{n}H(X_n). \end{array}

The main criterion, found in special cases by Avez and generalized by Kaimanovich-Vershik and Deriennic, is

Theorem 1 The following are equivalent.

  1. All bounded harmonic functions are constant.
  2. Tail is trivial (tail events have probability 0 or 1).
  3. {h=0}.

Also equivalent to speed being zero.

2. Lampligter groups

Lamplighter groups are special cases of wreath products. I will focus on

\displaystyle  \begin{array}{rcl}  G_d ={\mathbb Z}_2 \wr {\mathbb Z}^d. \end{array}

Group elements can be thought of as states, i.e. 0 or 1 for each element of {{\mathbb Z}^d}, together witht a position in {{\mathbb Z}^d} of the lamplighter. Neighbours of a given state differ by the state of the lamp or moving lamplighter one step aside. The identity is lamplighter at 0 and all lamps at 0.

When {d=1}, the volume growth equals Fibonacci numbers, so the growth rate equals the golden mean. On the other hand, the simple random walk moves slowly: after {n} steps, the lamplighter has moved to distance {\sqrt{n}}.

When {d=2}, the range of the walk grows sublinearly ({n/\log n}). Therefore the rate of escape is 0.

When {d\geq 3}, a positive fraction of the lamps will be left unchanged. The range of the wolk grows linearly. To turn them off will take linear time, the distance reached is linear. So the rate of escape is linear.

In general, if the base group is transient, the boundary is non trivial.

2.1. KV conjecture

Question (Kaimanovitch-Vershik). What are the bounded harmonic functions on {G_d} ? More specifically,

\displaystyle  \begin{array}{rcl}  h(x)=\mathop{\mathbb P}_x(\textrm{Lamp at origin eventually is on}) \end{array}

is a bounded harmonic function. Let {\mathcal{T}_0=\{}eventual lamps{\}}. This is a sub-{\sigma}-field of the tail. All bounded observables {f:\mathcal{T}_0 \rightarrow{\mathbb R}} define harmonic function

\displaystyle  \begin{array}{rcl}  h(x)=\mathop{\mathbb E}_x(f(\textrm{eventual lamps})). \end{array}

Kaimanovitch-Vershik conjectured in 1983 that all bounded harmonic functions are like that.

2.2. Results

In 1994, with James, I studied the tail of {{\mathbb Z}_+\wr {\mathbb Z}^d}, which is easier. We use the fact that walks have cut-points: if one point is removed, the past and future of the trajectory do not intersect. We showed that this happens if {d\geq 3}. The question boils down to the tail of a sequence of independant variables, solved by Kolmogorov’s 0-1 law.

Erschler in 2008 showed that the tail equals {\mathcal{T}_0} if {d\geq 5}.

With Lyons, we finally proved that the tail equals {\mathcal{T}_0} provided that the base group is transient (hardest case is {d=3,4}).

2.3. Proof

We need a criterion that has been used since the 1980’s.

Theorem 2 (Kaimanovitch 1985) Let {\mathcal{T}_0} be an invariant sub-{\sigma}-field of the tail. Then {\mathcal{T}_0} is the full tail if and only if the conditional entrodpy

\displaystyle  \begin{array}{rcl}  H(X_n|\mathcal{T}_0)=o(n). \end{array}

Combining this with a Shannon type theorem, one gets a more versatile variant.

Theorem 3 If there exists finite set {A_n\in G}, {\mathcal{T}_0}-measurable, such that

  1. {\log|A_n|=o(n)}.
  2. {\mathop{\mathbb P}_e(X_n\in A_n|\mathcal{T}_0)>\delta>0}.

Then {\mathcal{T}_0} is the full tail.

Construction of sets {A_n}. AT time {n}, the lampligter is somewhere is the ball of radius {n}, of size {n^d}. Go {n^\epsilon} further steps. Lamp status chages by at most {2^{2n^\epsilon}}. In dimension {d\geq 5}, past and future do not intersect. Indeed

\displaystyle  \begin{array}{rcl}  \sum_{k,\ell>n^\epsilon}p^{k+\ell}(0)\leq C\sum_{t>2n^\epsilon} t.t^{-d/2}\rightarrow 0. \end{array}

If {d=3,4}, we show that few points of the past also appear on the future of the path. The number (a binomial coefficient {\choose{n^d}{n^{-\epsilon/2}(\log n)^2}}) is sub-exponential.

2.4. Questions

Kaimanovitch: you seem to be using jumps in the walk.


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s