arXiv:1107.5499v2 [math.GR] 25 May 2016

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF
GROUPS
LAURENT BARTHOLDI AND ANNA ERSCHLER
Abstract. We study the Poisson-Furstenberg boundary of random walks on
permutational wreath products. We give a sufficient condition for a group to
admit a symmetric measure of finite first moment with non-trivial boundary,
and show that this criterion is useful to establish exponential word growth
of groups. We construct groups of exponential growth such that all finitely
supported (not necessarily symmetric, possibly degenerate) random walks on
these groups have trivial boundary. This gives a negative answer to a question
of Kaimanovich and Vershik.

1. Introduction
Consider a set X with a basepoint ρ and a right action of a group G. A random
walk on X is defined by a probability measure µ on G; the random walker starts
at ρ and, at each step, moves from x to xg with probability µpgq. An important
particular case is X “ G, seen as a G-space under right-multiplication. A measure
µ is symmetric if µpgq “ µpg ´1 q for all g P G, and is non-degenerate if its support
generates the group G.
The Poisson-Furstenberg boundary is the space of ergodic components of the
time shift in the space of infinite trajectories of the walk. In the case of random
walks on groups, there are several equivalent definitions of the Poisson-Furstenberg
boundary, and we recall some of them in Section 2. For more information, see e.g.
[26].
There is a strong relation between triviality/non-triviality of the boundary and
other asymptotic properties of groups (see [26], and [17] for a more recent overview).
For example, a result of Kaimanovich-Vershik and Rosenblatt [26, 32] states that
a group is amenable if and only if it admits a non-degenerate measure with trivial
boundary.
A natural question to ask is: “Can exponential word growth be characterized by
non-triviality of the boundary for appropriate measures?” Indeed, there are several
manifestations of the analogy between non-triviality of the boundary and exponential growth, such as the “Entropy Criterion” of Derriennic [11] and KaimanovichVershik [26] and the “Choquet-Deny” theorem for nilpotent groups, proven by
Dynkin and Maliutov [12]. There are partial results towards the characterisation
questions explained below, such as [15, Theorem 4.1] stating that a solvable group
G admits a symmetric measure with non-trivial Poisson boundary if and only if G
has exponential growth.
Date: 12 January 2015.
The work is supported by the ERC starting grant GA 257110 “RaWG”, the Courant Research
Centre “Higher Order Structures” of the University of Göttingen, and the ANR grant ANR-14ACHN-0018-01.
1

2

LAURENT BARTHOLDI AND ANNA ERSCHLER

The “Entropy Criterion” implies in particular that if a group admits a finitely
supported measure with non-trivial boundary, then its word growth is exponential.
Kaimanovich and Vershik conjecture in [26, page 466] that every group of exponential growth admits a symmetric (possibly infinitely supported) measure with
non-trivial boundary, and add: “It is plausible that such a measure can be chosen
finitary (but non-symmetric)”.
Their conjecture remains open; but we show in Section 5 that their addendum
does not hold:
Theorem A. There exists a finitely generated group G of exponential word growth,
such that the boundary of pG, µq is trivial for all finitely supported (possibly degenerate and non-symmetric) measures µ.
There are many examples of groups of exponential growth such that every symmetric finitely supported measure has trivial boundary, yet some finitely supported
measure has non-trivial boundary; e.g., wreath products of a non-trivial finite group
with Z or Z2 , see [26, §6.4], and solvable Baumslag-Solitar groups, see [26, §6.6].
Likewise, on some groups (e.g. wreath products of a finite group with the infinite
dihedral group, see Gilch [19]), every non-degenerate measure has trivial boundary,
but these groups admit degenerate measures with non-trivial boundary.
The groups we construct to prove Theorem A are permutational
wreath products,
ř
as defined in the next section: groups W “ A ≀X G “ X A ⋊ G. More precisely,
we consider a family of groups W “ A ≀X1 ˆ¨¨¨ˆXd pG1 ˆ ¨ ¨ ¨ ˆ Gd q, in which each Gi
is a copy of the first Grigorchuk group, each Xi is an orbital Schreier graph of the
first Grigorchuk group, and A is a finite group. See Sections 2 and 4 for details of
this construction. See also Section 6 for a larger family of examples.
Ordinary wreath products (X “ G) have exponential growth as soon as A is
non-trivial and G is infinite, but the situation is more subtle for permutational
wreath products, which may have intermediate growth. Indeed, it is shown in [7]
that the W above has intermediate growth if d “ 1. In this paper we consider the
groups W with d ě 2, and are in particular interested in the case d “ 2. For d ě 3
one can show that a simple random walk on such groups has non-trivial PoissonFurstenberg boundary, see Example 4.9. For the proof of Theorem A we consider
the case d “ 2, which lies in some sense on a borderline between exponential and
intermediate growth: on one hand, as we explain below, the growth is exponential.
On the other hand, these groups are “close to groups of subexponential growth”,
in the sense that any finitely supported measure on them has trivial boundary.
In many known examples of groups, their exponential growth can be checked
either by exhibiting a free semigroup (they exist in solvable groups of exponential
growth, and more generally in elementarily amenable groups of exponential growth,
see Chou [10]); or by proving the existence of an imbedded regular tree in the
group’s Cayley graph (as is the case for any non-amenable group [8]). Ordinary
(non-permutational) wreath products of a non-trivial group by an infinite group
also contain regular trees in their Cayley graph, and this class of groups contains
interesting examples of torsion groups of exponential growth, see Grigorchuk [23].
Our understanding is that, for the groups we consider in this paper, it is not
straightforward to check that their growth is exponential. To show that our examples have exponential growth we prove (in Section 4) the following criterion based
on random walks:

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

3

Theorem B. Let G be a finitely generated group acting on a set X, and let µ be a
finitely supported, symmetric, non-degenerate measure on G. Suppose that the drift
function of µ is at most Dnα for some constants α ă 1 and D, and that, for every
ρ P X, the probability of return to ρ of the n-step random walk induced on X is at
most Cn´δ , for some constants δ ą α and C. Let A be a non-trivial group.
Then W :“ A ≀X G admits a symmetric measure with finite first moment and
non-trivial Poisson-Furstenberg boundary. In particular, the word growth of W is
exponential.
In our situation, we consider δ “ 1 and some α ă 1. The assumption of Theorem B on the probability to return to the origin on X is a consequence of the
fact that X is a product of two copies of infinite transitive Schreier graphs. For
our main examples used for the proof of Theorem A, the condition on the drift in
Theorem B follows from an upper bound on the growth of Grigorchuk groups. To
get more examples of this kind, we consider groups for which the condition on the
drift on G is ensured by a version of a self-similar-random-walk argument due to
Bartholdi-Virag and Kaimanovich; see Example 6.5. We also give a torsion-free
group with this property, see Example 6.6.
On the other hand, to prove that the random walks we consider have trivial
Poisson-Furstenberg boundary, we use a criterion due to Kalpazidou and Mathieu
ensuring recurrence of “centered” random walks, and a criterion for triviality of the
boundary of random walks on permutational wreath products (Proposition 5.1).
This criterion is more complicated than in the case of ordinary wreath products,
see the discussion at the beginning of Section 5.
The groups we construct in this paper admit a (symmetric, non-degenerate)
finite first moment measure with non-trivial boundary. This leads us to ask the
following question:
Question 1.1. Does there exist a group G of exponential word growth, such that
all (not necessarily symmetric, not necessarily non-degenerate) measures with finite
first moment have trivial Poisson-Furstenberg boundary?
2. Definitions and preliminaries
2.1. Poisson-Furstenberg boundary, entropy and drift. Consider two infinite
trajectories x and y. We say they are equivalent if they coincide after some instant,
possibly up to the time shift: there exists N P N, k P Z such that xn “ y n`k for all
n ě N . Consider the measurable hull of this equivalence relation in the space of
infinite trajectories. The quotient by this equivalence relation is called the PoissonFurstenberg boundary.
ř A function F : G Ñ R is called µ-harmonic if for all g P G we have F pgq “
hPG F pghqµphq. The Poisson-Furstenberg boundary is non-trivial if and only if G
admits a bounded µ-harmonic function which is non-constant on the group generated by the support of µ.
ř
The entropy of a probability measure µ is computed as Hpµq “ ´ g µpgq logpµpgqq.
The entropy of the random walk, also called its asymptotic entropy, is the limit hpµq
of Hpµ˚n q{n, as n tends to infinity. This limit is well-defined, since the function
Hpnq :“ Hpµ˚n q is subadditive. If Hpµq “ 8, then Hpµ˚n q “ 8 for all n and in
this case we put hpµq “ 8.

4

LAURENT BARTHOLDI AND ANNA ERSCHLER

Fix a finite generating set S and consider on G the word metric } ¨ }S associated
with S. Given a probability measure µ on G and β ą 0, the β-moment of µ with
ř
respect to S is Lβ pµq :“ gPG µpgq}g}βS . Clearly, if the β-moment is finite with
respect to some finite generating set S, then it is finite with respect to any other
generating set. The first moment of µ is simply written Lpµq.
The function Lpnq :“ Lpµ˚n q is also subadditive, by the triangular inequality for
} ¨ }S . It expresses the mean distance to the origin in the word metric } ¨ }S , after n
steps of the random walk. The drift, also called rate of escape, of the random walk
pG, µq is the limit ℓpµq of Lpnq{n as n tends to infinity; this limit is well-defined
because Lpnq is subadditive. If the first moment of µ is finite, that is, if Lp1q ă 8,
then ℓpµq ď Lp1q ă 8.
The entropy criterion (Derriennic, Kaimanovich-Vershik [11, 26]) states that if µ
is a measure of finite entropy, then the boundary of pG, µq is trivial if and only if the
entropy of the random walk hpµq is zero. If ℓpµq “ 0 then hpµq “ 0. For symmetric
measures, the converse is true: a symmetric measure µ of finite first moment has
zero drift (ℓpµq “ 0) if and only if the entropy of the random walk pG, µq is zero
(hpµq “ 0), see Karlsson-Ledrappier [29].
We say that a measure µ is non-degenerate if its support generates G. If the
boundary of µ is trivial, then the group generated by the support of µ is amenable.
Every amenable group admits a non-degenerate measure with trivial boundary
(Kaimanovich-Vershik, Rosenblatt [26, 32]); this measure can be chosen symmetric
and with support equal to G.
2.2. Random walks on permutational wreath products. We consider groups
A, G, such that G acts on a set X from the right. řThe (permutational) wreath
product W “ A ≀X G is the semidirect product of X A with G. The support
supppf q of a function
ř f : X Ñ A consists in those x P X such that f pxq ‰ 1. The
restricted product řX A is the group of finitely supported functions X Ñ A. The
left action of G on X A is then defined by pg ¨ f qpxq “ f pxgq; observe that for g1 ,
g2 in G
pg1 g2 ¨ f qpyq “ f pypg1 g2 qq “ f ppyg1 qg2 q “ pg2 ¨ f qpyg1 q “ pg1 ¨ g2 ¨ f qpyq.

We have in particular supppg ´1 ¨ f q “ supppf qg.
If A and G are finitely generated and if the action of G on X is transitive, then
the permutational wreath product is a finitely generated group. Indeed, fix finite
generating sets SA and SG of A and G respectively, and fix a basepoint ρ P X. The
wreath product is generated by S “ SA Y SG . Here and in the sequel we identify G
with its image in W under the imbedding g Ñ p1, gq and identify A with its image
in W under the imbedding a Ñ pfa , 1q, where fa : X Ñ A is defined by fa pρq “ a
and f pxq “ 1 for all x ‰ ρ. We call S the standard generating set of W defined by
SA , SG . Analogously, if the action of G on X has finitely many orbits, then W is
finitely generated by SG Y pSA ˆ X{Gq. If the action has infinitely many orbits,
then the permutational wreath product is not finitely generated.
The Cayley graph of the permutational wreath product with respect
ř to the
standard generating set S
can
be
described
as
follows.
Elements
of
W
“
X A⋊G
ř
are written f g with f P X A and g P G; multiplication is given by pf1 g1 qpf2 g2 q “
f1 pg1 ¨ f2 qg1 g2 .
Consider a word v “ s1 s2 . . . sℓ , with all si P S, and write its value in W as
řfv gv .
Set u “ fu gu “ s1 s2 . . . sℓ´1 . Here gu , gv belong to G, and fu , fv belong to X A.

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

5

We consider two cases, depending on whether sℓ P SA or Sℓ P SG . If sℓ P SA , we
have an edge of “A” type from u to v. The multiplication formula gives gv “ gu
and fv pxq “ fu pxq for all x ‰ ρgu´1 , while fv pρgu´1 q “ fu pρgu´1 qsℓ .
If sℓ P SG , we have an edge of “G” type from u to v. In that case, fv “ fu , and
g v “ g u sℓ .
We have begun to study asymptotic properties of permutational wreath products
in [7]. The asymptotic geometry of these groups turns out to be much richer than
in the particular case of ordinary wreath products (namely, for which X “ G). It
is easy to see that the word growth of A ≀ G is exponential whenever X “ G is
infinite and A is non-trivial. However, among permutational wreath products there
are groups of intermediate growth, see [7].
Given a probability measure µ on W “ A ≀X G, we say that the random walk is
translate-or-switch if the support of µ belongs to the union of G and A; in other
words, µ “ pµA ` qµG , where p, q ě 0, p ` q “ 1, the support of µA belongs to A,
and the support of µG belongs to G.
We say that the random walk is switch-translate-switch if µ “ µA ˚ µG ˚ µA ,
for measures µA , µG supported on A and G respectively. If X “ G, the “switchtranslate-switch” random walks are called “switch-walk-switch”. In this case, we
can view each step of the random walk as follows: we “switch” the value of the
configuration at the point where the random walker stands, then make one step
of the random walk on G and then switch the configuration at the point of the
arrival. Note however that no such interpretation is valid for a general permutational wreath product, because translation and movement are in general genuinely
different operations.
Let w “ g1 . . . gn be a word over G of length n “ |w|, and let ρ P X be a
base point. The inverted orbit of w is the set tρ, ρgn , ρgn´1 gn , . . . , ρg1 ¨ ¨ ¨ gn u; the
inverted orbit growth is the cardinality
δρ pwq “ #tρ, ρgn , ρgn´1 gn , . . . , ρg1 ¨ ¨ ¨ gn u
of that set. In the sequel, ρ will be fixed, and we will usually omit it from the
notation.
If w is a word corresponding to a length-n trajectory of a random walk, then we
can consider δρ pwq as a random variable with values in t1, . . . , n ` 1u.
3. Criteria for non-triviality of the boundary
We characterize in this section groups with non-trivial Poisson-Furstenberg boundary, with the goal of applying it to permutational wreath products. For ordinary
wreath products, a well-known criterion by Kaimanovich and Vershik [26, Proposition 6.4] states that, for A ‰ 1 finite and finitely supported measures, A ≀ G has
trivial boundary if and only if the projection of the random walk to G is recurrent.
We extend this criterion to permutational wreath products.
Lemma 3.1. Let the group G act on X and let µ be a probability measure on
G. Let ρ P X be a basepoint. Then the induced random walk on X starting at ρ
is recurrent if and only if the expectancy of the inverted orbit growth Erδρ pwqs is
sublinear in |w|.
Proof. Consider the random variable Ai,n which equals 1 if the i-th point on the
inverted orbit of the trajectory of the random walk is distinct from any points from

6

LAURENT BARTHOLDI AND ANNA ERSCHLER

1 to i ´ 1, and equals 0 otherwise. Consider a word w “ g1 . . . gn . Since G acts by
permutations on X, we have
w P Ai,n ô ρgi ¨ ¨ ¨ gn R tρgi´1 ¨ ¨ ¨ gn , ρgi´2 ¨ ¨ ¨ gn , . . . , ρg1 ¨ ¨ ¨ gn u
ô ρ R tρgi´1 , ρgi´2 gi´1 , . . . , ρg1 ¨ ¨ ¨ gi´1 u

´1
´1 ´1
´1 ´1
ô ρ R tρgi´1
, ρgi´1
gi´2 , . . . , ρgi´1
gi´2 ¨ ¨ ¨ g1´1 u.

Therefore,
´1
´1 ´1
´1 ´1
ErAi,n s “ Prρ ‰ ρgi´1
and ρ ‰ ρgi´1
gi´2 and . . . and ρ ‰ ρgi´1
gi´2 ¨ ¨ ¨ g1´1 s;

observe that this is the probability pi that the random walk on X induced by pG, µ̌q
with µ̌pgq “ µpg ´1 q, starting from ρ, never returns to this base point ρ during time
moments between 1 and i ´ 1. Note that for each i we have pi ě pi`1 . If the
random walk on X induced by pG, µ̌q is recurrent, then pi Ñ 0, while if the random
walk on X induced bypG, µ̌q is transient, then there exists p ą 0 such that pi ě p
for all i.
Next, observe that the expectation of δρ pwq is
(1)

Erδρ pwqs “ Er1 ` A1,n ` A2,n ` ¨ ¨ ¨ ` An,n s

“ 1 ` ErA1,n s ` ErA2,n s ` ¨ ¨ ¨ ` ErAn,n s.

Therefore, the expectation of δρ pwq grows linearly (at least pn) if the random walk
is transient, while δρ pwq{|w| tends to zero if the random walk is recurrent.
Finally, observe that pG, µ̌q induces a transient random walk on X if and only
if the stabilizer Gρ of ρ P X is a transient set for the random walk pG, µ̌q; because
Gρ “ G´1
ρ , this happens if and only if pG, µq induces a transient random walk on
X.

We continue now with two propositions, each giving a sufficient condition for
non-triviality of the boundary. One uses finiteness of the entropy of µ, and the
other a weak restriction on the support of µ. The proof of Lemma 3.2 appears
further below.
Lemma 3.2. Let µ be a non-degenerate measure on W with finite entropy Hpµq,
and suppose that the expected size of the inverted orbits of the random walk defined
by the projection of µ to G grows linearly. Then the entropy hpµq of the random
walk pW, µq is positive; so the Poisson-Furstenberg boundary of pW, µq is non-trivial.
Combining Lemma 3.1 and Lemma 3.2, we get the following
Proposition 3.3. Let µ be a non-degenerate random walk on W with finite entropy and transient projection to X. Then the Poisson-Furstenberg boundary of the
random walk pW, µq is non-trivial.
Proof of Lemma 3.2. The argument is similar to that of [15, Theorem 3.1]. ř
Let ρ P X be any basepoint. First, there exists N P N and f ‰ f 1 P X A
both supported on tρu such that f, f 1 P supppµ˚N q, ř
because µ is non-degenerate.
Recall that we identify A with those functions f P X A that are supported on
tρu. Since hpµ˚N q “ N hpµq, it suffices to prove hpµ˚N q ą 0; up to replacing µ by
µ˚N , we suppose, from now on, that there are at least two elements in A X supppµq;
in particular, µpAq ą 0. If at time instant n the increment of the random walk
belongs to A, we say that at this instant there is an ‘A’ step of the random walk.

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

7

Define the normalized measure ν : A Ñ R by νpaq “ µpaq{µpAq; by assumption,
Hpνq ą 0.
Let w “ w1 . . . wn P W n be a trajectory, and let W act on X via the quotient
map W Ñ G. Consider, in analogy with the proof of Lemma 3.1, the event Zi,n
that the inverted random walk of G on X visits a new point at time i, namely
Zi,n ô ρwi ¨ ¨ ¨ wn R tρwj ¨ ¨ ¨ wn | j ą iu.
As in (1) we have
Erδρ pwqs “ PrZ1,n s ` ¨ ¨ ¨ ` PrZn,n s ` 1.

1
For i ě 2, let Zi,n
“ Zi,n ^ pwi´1 P Aq denote the event that Zi,n holds and
that an ‘A’ step is performed at the moment the new point is visited. Since Zi,n
1
and pwi´1 P Aq are independent events, PrZi,n
s “ µpAqPrZi,n s. Therefore, the
expected number t of distinct points x1 , . . . , xt P X that belong to the inverted
orbit of w and at which an ‘A’ step occurs is at least

µpAqPrZ2,n s ` ¨ ¨ ¨ ` µpAqPrZn,n s ` µpAq ě µpAqErδρ pwqs ´ 1.
Since the expectation of δρ pwq is linear in n, the expectation of t is also linear
in n, say Erts ě dn for all n large enough and a constant d ą 0.
Now given a random trajectory w “ w1 w2 . . . wn P W n , with steps wi , let
1
i1 , . . . , it P t1, . . . , n ´ 1u denote those times i at which Zi`1,n
holds. Let τ denote
n
1
1
the partition of W in which w “ w1 . . . wn and w “ w1 . . . wn1 belong to the
same part if they have the same t, same indices i1 , . . . , it and if wi “ wi1 for all
i R ti1 , . . . , it u. In particular all wi1 , . . . , wit belong to A, and if for s “ 1, . . . , t
we let xs “ ρwis ¨ ¨ ¨ wn denote the corresponding points in the inverted orbit, then
they are the same for all elements of a part.
We compute the conditional entropy Hpµ˚n | τ q. All elements w in a part of
the partition are obtained by selecting independently t elements wi1 , . . . , wit P A
according to the normalized measure ν. All these words w evaluate to distinct
elements w of W : each wi1 , . . . , wit may be recovered from w P W by writing
w “ pf, gq with f : X Ñ A, g P G and considering f px1 q, . . . , f pxt q. Therefore,
Hpµ˚n | τ q ě ErtsHpνq ě µpAqdnHpνq;

we have Hpµ˚n q ě Hpµ˚n | τ q, because entropy is not less than the mean conditional entropy, see e.g. [31, §5], so
hpµq “ lim

1
1
Hpµ˚n q ě lim Hpµ˚n | τ q ě µpAqdHpνq ą 0.
n
n



We consider now a different sufficient condition for non-triviality of the boundary,
requiring only a very weak form of non-degeneracy of the random walk:
Proposition 3.4. Let µ be “switch-translate-switch” random walk on W , and assume that there exist n P N and two elements in the support of µ˚n with equal
projection to G. Assume also that the projected random walk pX, µq is transient.
Then the Poisson-Furstenberg boundary of the random walk pW, µq is non-trivial.
Note, in particular, that the first condition holds as soon as µ is non-degenerate
and A ‰ 1. Note also that the ‘translation’ part of µ is allowed to be infinitely
supported on X. Indeed, we will later apply Proposition 3.4 to infinitely supported
measures.

8

LAURENT BARTHOLDI AND ANNA ERSCHLER

Proof. Consider
a trajectory Θ “ p1, f1 g1 , f2 g2 , . . . q of the random walk on W ,
ř
with fi P X A and gi P G, and pfi gi q´1 fi`1 gi`1
ř „ µ.
By assumption, there exists n P N and u, v P X A, g P G such that two elements
ug ‰ vg P W are reached with positive probability at time n of the walk. Choose
a coördinate σ P X in which u and v differ, say vpσq “ aupσq for some a ‰ 1 in A.
Consider fi pσq. Since the random walk we consider is “switch-translate-switch”,
for all i the elements fi and fi`1 differ in at most two places. More precisely,
´1
fi pσq ‰ fi`1 pσq only when σ P tρgi´1 , ρgi`1
u.
Since µ is transient, there is a bound R P N such that, almost surely, we have
´1
σ P tρgi´1 , ρgi`1
u in at most R instants i. It follows that
φσ pΘq :“ lim fi pσq
iÑ8

almost surely exists, and defines a measurable function on the space of trajectories.
For any ǫ ą 0, at least 1 ´ ǫ of the mass of µ is concentrated
ř on a finite set
Wǫ Ă W ; there exists a finite subset Aǫ Ď A such that f P X Aǫ whenever
f g P Wǫ ; so, with probability 1 ´ Rǫ, the limit φσ belongs to the finite set AR
ǫ .
Take now ǫ small enough so that Rǫ ă µ˚n pugq. Then there exists b P AR
such
ǫ
that with positive probability the trajectory Θ visits ug at time n and satisfies
φσ pΘq “ b.
For each such trajectory, replace the initial n steps (reaching ug) with an n-step
random walk reaching vg. This produces a positive-measure set of trajectories that
visit vg at time n and satisfy φσ pΘq “ vpσqupσq´1 b “ ab ‰ b. Therefore, φσ is not
constant.
We have exhibited a non-constant measurable function on the space of exits of
the random walk, so its boundary is not trivial.

Alternatively, as a replacement for the last three paragraphs of the proof, let the
element a “ vpσqupσq´1 P A have order m P N Y t8u. Let T be a right
Ů transversal
of xay Ů
in A; that is, A “ T \ aT \ ¨ ¨ ¨ . If m “ 8, set A0 “ nPZ a2n T and
A1 “ nPZ a2n`1 T , while if m ă 8, set An “ an T for all n P t0, . . . , m ´ 1u.
Then the function χ : Θ ÞÑ pn if φσ pΘq P An q is measurable, takes finitely many
values, and takes value n with positive probability if and only if it takes value n ´ 1
pmod mq or pmod 2q with positive probability, so is not constant.
4. Groups admitting finite first moment measures with non-trivial
Poisson-Furstenberg boundary
Our aim, in this section, is to prove that most wreath products of the form
W “ A ≀X1 ˆX2 pG1 ˆ G2 q have a non-trivial boundary for an appropriate measure.
This measure will be an infinite convex combination of the convolutions powers of
some symmetric finitely supported measure on W . Our main task is to chose the
coëfficients in the convex combinations in such a way that they decay not to fast;
on the other hand, they must decay fast enough that the measure we construct has
finite first moment.
To show that the measure has non-trivial boundary, we use the results of the
previous section (Propositions 3.3 and 3.4). At the end of this section, we give
applications of Theorem B, and construct groups of exponential growth that we
will later use to prove Theorem A.

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

9

Theorem 4.1 (= Theorem B). Let G be a group acting on a set X, and let µ be a
finitely supported, symmetric, non-degenerate measure on G. Suppose that its drift
satisfies Lµi pnq ď Dnα for all n P N, for some constants D and α ă 1. Suppose also
that, for every ρ P X, the probability of return to ρ satisfies µ˚n pstabG pρqq ď C{nδ
for all n P N, for some constants C and δ ą α. Let A be a non-trivial group.
Then W :“ A ≀X G admits a symmetric measure with finite first moment and
non-trivial Poisson-Furstenberg boundary. In particular, the word growth of W is
exponential.
The idea of the proof is to construct a measure µ, with finite first moment, such
that the induced random walk on X is transient; and then to use Proposition 3.3
or Proposition 3.4 to conclude that the boundary of the random walk pW, µq is
non-trivial.
4.1. Reminder: properties of Stable Laws. We start by recalling classical
results on stable laws from [24], which we restrict to measures on R` . A measure µ
on R` is stable if for any a1 , a2 ą 0 there are a ą 0, b such that µpa1 ¨ xq ˚ µpa2 ¨ xq “
µpa ¨ x ` bq; in particular, if µ is the law of independent random variables X1 , X2 ,
then the law of X1 ` X2 is an affine transformation of µ.
Let X1 , X2 , . . . be independent random variables with law µ1 . We say µ1 is in the
domain of attraction of a non-degenerate stable law µ if there are constants An , Bn
such that the law µn of pX1 ` ¨ ¨ ¨ ` Xn ´ An q{Bn converges weakly to µ; namely,
if µn pM q Ñ µpM q for all Borel subsets M Ď R whose boundary is µ-negligible.
The distribution of a measure µ on R` is the function F pxq “ µpr0, xsq. Attraction towards a stable law can be checked by estimating the regularity of the tails
of the distribution:
Theorem 4.2 (Part of [24, Theorem 2.6.1]). A measure belongs to the domain of
attraction of a stable law if and only if its distribution F satisfies
hpxq
as x Ñ 8,
xα
for a function h that varies slowly in the sense of Karamata (meaning hptxq{hpxq Ñ
1 for all t ą 0) and a parameter α P p0, 2q. This parameter is called the exponent
of the measure.

F pxq “ 1 ´

We will also use a local limit theorem due to Gnedenko: again, we only quote
a subcaseş of the general result. Recall that a measure µ on R has density g if
µpM q “ M gpxqdx for all measurable M Ă R. All stable measures have a density,
which furthermore may be supposed to be a continuous (and therefore bounded)
function g : R Ñ R, see [24, §2.3].
Theorem 4.3 (Part of [24, Theorem 4.2.1]). Suppose that µ1 is supported on N,
but not on hN for any h ą 1, and suppose that µ1 is in the domain of attraction of
a stable law with density g. Then
ˇ
ˇ
lim sup ˇBn pµ1 q˚n pkq ´ gppk ´ An q{Bn qˇ “ 0.
nÑ8 kPN

4.2. Proof of Theorem 4.1.

Proof. Consider a parameter γ P p1, 2q, to be ř
fixed later. For
ř8i P t1, 2, . . . u, set
8
αi “ Cγ {iγ for a constant Cγ defined such that i“1 αi “ Cγ i“1 i´γ “ 1. Define

10

LAURENT BARTHOLDI AND ANNA ERSCHLER

measures νγ on N and λγ on G by
νγ piq “ αi ,

λγ “

8
ÿ

αi µ˚i .

i“1

By the definition of Cγ , both νγ and λγ are probability measures. The following
estimate on negative moments of νγ˚n will be needed later:
Lemma 4.4. For all δ ą 0 there exists a constant C such that, for all n ě 2,
#
8
ÿ
C{n1{pγ´1q logpnq if δ “ 1,
νγ˚n piq{iδ ď
C{nδ{pγ´1q
if δ ‰ 1.
i“1

Proof. We first show that νγ is in the domain of attraction of a stable law, by
checking
the hypotheses of Theorem 4.2. Its distribution satisfies 1 ´ F pxq “
ř
´γ
C
, so
xăiPN γ i
ż8
ż8
Cγ 1´γ
Cγ
x
“
px ` 1q1´γ ,
Cγ t´γ dt ď 1 ´ F pxq ď
Cγ t´γ dt “
γ´1
γ
´
1
x
x`1

so Cγ {pγ ´ 1q ď hpxq ď Cγ {pγ ´ 1qp1 ` 1{xq1´γ and h is slowly varying. Therefore,
νγ is in the domain of attraction of a stable law of exponent α “ γ ´ 1.
It then follows from [24, Theorem 2.1.1] that Bn “ n1{α hpnq for another function
h that slowly varies in the sense of Karamata.
Let g be the density of the stable law towards which νγ converges. By Theorem 4.3, supk Bn pνγ q˚n pkq ´ gppk ´ An q{Bn q converges to 0 as n Ñ 8, and g is
bounded, so supk Bn pνγ q˚n pkq is bounded. Therefore, there exists a constant C 1
such that pνγ q˚n pkq ď C 1 n´1{pγ´1q for all k P N.
We are now ready to prove the lemma. Set an “ n1{pγ´1q , and split the sum as
8
ÿ

i“1

νγ˚n piq{iδ “

In the first summand, we use
an
ÿ

i“1

an
ÿ

i“1

νγ˚n piq

νγ˚n piq{iδ ď C 1 {n1{pγ´1q
1

ď C {n

1{pγ´1q

νγ˚n piq{iδ `
1

ď C {n

an
ÿ

8
ÿ

i“an `1

1{pγ´1q

νγ˚n piq{iδ .

for all i, so

1{iδ

i“1

#
log an ď C 2 {n1{pγ´1q logpnq
an1´δ {p1 ´ δq ď C 2 {nδ{pγ´1q

if δ “ 1,
if δ ‰ 1,

for some constant C 2 . For the second summand, we use the coarse estimate
8
ÿ

i“an `1

νγ˚n piq{iδ ď 1{aδn
2

8
ÿ

i“an `1

and we are done, setting C “ C ` 1.

νγ˚n piq ď 1{aδn “ 1{nδ{pγ´1q


Let us next find out for which γ the random walk on X defined by λγ is transient.
The argument is close to that of [16, Lemma 3.1]. In that lemma, it was shown
that for any transitive action of G on an infinite set X, the measures λγ define a
transient random walk on X as soon as γ P p1, 3{2q. For the proof of Theorem 4.1,
however, it is not sufficient to work with γ between 1 and 3{2, because the theorem’s
assumptions do not imply that λγ has finite first moment for some γ ă 3{2. Indeed,

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

11

we will use in an essential manner the additional assumption on the action to weaken
the condition on γ.
Proposition 4.5. Suppose that the probability of return to the origin ρ P X for
the random walk on X induced by the measure µ satisfies µ˚n pstabG pρqq ď C{nδ
for some δ ą 0. Then, for all γ P p1, 1 ` δq, the random walk pλγ , Xq is transient.
Proof. For any H Ă G, we have

λ˚n
γ pHq “

ÿ

iě0

νγ˚n piqµ˚i pHq.

In particular, this holds with H the stabilizer of ρ P X:
ÿ
λ˚n
νγ˚n piqµ˚i pstabG pρqq.
γ pstabG pρqq “
iě1

By Lemma 4.4 we know that for any δ
8
ÿ

i“1

νγ˚n piq{iδ ď C{nδ{pγ´1q logpnq.

Therefore, for all n ě 2 we have
λ˚n
γ pstabG pρqq “
ď

8
ÿ

i“1
8
ÿ

i“1

νγ˚n piqµ˚i pstabG pρqq
νγ˚n piqC{iδ ď C{nδ{pγ´1q logpnq.

Since γ ă 1 ` δ, we have δ{pγ ´ 1q ą 1, so
8
ÿ

n“0

λ˚n
γ pstabG pρqq ă 8.

This means that stabG pρq is a transient subgroup for the measure λγ , or, in other
words, that the random walk on X induced by the measure λγ is transient.

We can now finish the proof of Theorem 4.1. It is time to use the assumption
on the first moment of µ.
Lemma 4.6. For γ ą 1 ` α, the first moment of the measure λγ is finite.
Proof. Recall that Lµ piq denotes the first moment of the measure µ˚i . By our
assumption, there exists a constant D such that Lµ piq ă Diα for all i P N. The
first moment of λγ is therefore equal to
8
ÿ

i“1

if γ ´ α ą 1.

νγ piqLµ piq ď D

8
ÿ

i“1

Cγ i´γ iα “ DCγ

8
ÿ

i“1

i´pγ´αq ă 8,


Now fix γ P p1 ` α, 1 ` δq. By Proposition 4.5, the random walk λγ is transient,
while by Lemma 4.6 the first moment of λγ is finite.
Take a measure µA on A with finite first moment, whose support contains 1 and
generates A. Set λ “ µA ˚ λγ ˚ µA . Observe that λ is a non-degenerate random
walk with finite first moment, and that the induced random walk on X is transient.

12

LAURENT BARTHOLDI AND ANNA ERSCHLER

Therefore, by Proposition 3.3, the boundary of pW, λq is non-trivial. This completes
the proof of Theorem 4.1.
Alternatively, note that λ is a “switch-translate-switch” random walk, so that
Proposition 3.4 applies.

4.3. Consequences of Theorem 4.1.
Corollary 4.7. Let α ă 1 be given; for each i “ 1, 2, let Gi act transitively on
an infinite set Xi , and let µi be a finitely supported, symmetric, non-degenerate
probability measure whose drift satisfies Lµi pnq ď Dnα for a constant D and all
n P N.
Set G “ G1 ˆ G2 and X “ X1 ˆ X2 , on which G acts coördinatewise. Let A be
a non-trivial group.
Then W :“ A ≀X G admits a symmetric measure with finite first moment and
non-trivial Poisson-Furstenberg boundary. In particular, the word growth of W is
exponential.
Proof. Set µ “ µ1 ˆ µ2 ; it is the random walk on X that walks independently
on X1 and X2 . Choose a basepoint ρ “ pρ1 , ρ2 q P X. Observe stabG pρq X G1 “
stabG1 pρ1 q and stabG pρqXG2 “ stabG2 pρ2 q. For all n ě 0 we have µ˚n pstabG pρqq “
˚n
µ˚n
1 pstabG1 pρ1 qqµ2 pstabG2 pρ2 qq.
We say that a symmetric random walk on a connected locally finite graph is a
nearest neighbour random walk if it is a symmetric random walk which walks along
the edges of the graph with probability bounded away from zero: p1 px, yq “ p1 py, xq,
p1 px, yq ą 0 implies that x and y are joined by an edge, and there exists p ą 0 such
that p1 px, yq ě p whenever x and y are joined by an edge.
For a nearest-neighbour symmetric random walk on a connected infinite
locally
?
finite graph, the n-step transition probabilities satisfy pn px, yq ď C 1 { n for some
C 1 ą 0 and all n ě 1,?and, in particular, the probability to return to the origin
satisfies pn px, xq ď C 1 { n for all x and?all n ě 1; see Woess [33, Corollary
? 14.6].
˚n
pρ
qq
ď
C
{
n
and
µ
pstab
n for some
pρ
qq
ď
C
{
This implies µ˚n
pstab
2
2
G
1
1
G
2
1
2
1
constants C1 , C2 depending on X1 , X2 and all n ě 1. Therefore, µ˚n pstabG pρqq ď
C{n, for C “ C1 C2 and all n ě 1.
Consider S “ S1 Y S2 . Clearly, S is a generating set of G “ G1 ˆ G2 whenever
S1 and S2 are generating sets of G1 and G2 respectively, and }pg1 , g2 q}S “ }g1 }S1 `
}g2 }S2 for all g1 P G1 , g2 P G2 . For all n ě 0, we have Lµ,G,S pnq “ Lµ1 ,G1 ,S1 pnq `
Lµ2 ,G2 ,S2 pnq; so, by the assumptions of the corollary, Lµ pnq “ Lµ,G,S pnq ď Cnα .
We may therefore apply Theorem 4.1 with δ “ 1.

Groups satisfying the assumption of the theorem admit a symmetric measure of
finite first moment whose boundary is non-trivial. However, there are groups of
exponential growth, such as for example wreath products of a finite group with Z,
on which any symmetric finite first moment measure has trivial boundary.
Remark 4.8. The assumption that X is a direct product is important, and is used
to bound from above the return probabilities to the origin. There are examples of
wreath products with infinite X, such as the group A ≀X1 G012 studied in [7], that
have intermediate word growth and therefore trivial boundary for all measures of
finite first moment.
Example 4.9. Consider G “ G1 ˆ G2 ˆ G3 and X “ X1 ˆ X2 ˆ X3 with all
Xi infinite, transitive Gi -spaces. Then all permutational wreath products A ≀X G

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

13

have exponential word growth, without any assumption on the µi . Indeed, all
simple random walks on these groups have a non-trivial boundary, as follows from
Proposition 3.3.
Remark 4.10. Let G be a group with word growth vpnq at most exppnβ q for some
β ă 1, and let µ be a finitely supported measure on G. Then LG,µ pnq ď Cnp1`βq{2 .
Proof. For any symmetric finitely
supported random walk on a group G, there exists
a
K ą 0 such that Lpnq ď K n log vpnq ` logpnq for all n, see [14, Lemma 7.(ii)]. 

Example 4.11. Consider G1 and G2 both equal to the first Grigorchuk group
G012 , and X1 and X2 some orbits for the action on the boundary of the rooted
tree. Recall that G012 has subexponential word growth, and more precisely by [20]
has growth at most exppnβ q for some β ă 1. The best known upper bound is
β “ logp2q{ logp2{ηq – 0.7674 with η 3 ` η 2 ` η “ 2, see [3]. In view of Remark 4.10,
the assumptions of Corollary 4.7 are satisfied for α “ p1`βq{2, so A≀X1 ˆX2 pG1 ˆG2 q
has exponential growth as soon as A is not trivial.

Among the Grigorchuk groups, there are groups with growth arbitrarily close to
exponential along a subsequence [21], and in particular not bounded from above by
any function of the form exppnα q. We cannot use Remark 4.10 to estimate the drift
of simple random walks on such groups. However, every Grigorchuk group admits
a finitely supported random walk whose drift function is bounded from above by
Cnα for α “ 3{4, see Corollary 6.3.
5. A sufficient condition for triviality of the Poisson-Furstenberg
boundary
It is well known that the triviality of the boundary of an ordinary wreath product
of A ≀ G is related to the recurrence of G, see Kaimanovich and Vershik [26, Proposition 6.4]. However, their argument does not seem to provide information about
the triviality of the boundary in the case of a permutational wreath product A≀X G,
in which the action of G on X is recurrent. Indeed, let W “ A ≀X G be a permutational wreath product, let ρ be a point of X and let W 1 be the subgroup of W
that projects to the stabilizer of ρ in G. Starting with a random walk on W which
induces a recurrent random walk on X, we can claim (by renormalizing the random
walk at stop times in the stabilizer of ρ) that the boundary of this random walk is
equivalent to the boundary of some (in general, infinitely supported) random walk
on W 1 ; however, in contrast with the ordinary wreath product case the group W 1
may be large, even if A is small.
Another approach to criteria for triviality of the boundary in the case of ordinary
wreath products A ≀ G, in which the induced random walk on G is recurrent, is to
estimate the entropy of the random walk [13]. The proposition below is an analogue
of such a criterion, but now in the case of permutational wreath products. The
main difficulty of the proof of this proposition, which does not appear in the case
of ordinary wreath products, is in the estimation of the number of choices of the
inverted orbit, see Remark 5.3.
Proposition 5.1. Let A, G be groups of subexponential word growth, and set W :“
A ≀X G. Let µ be finitely supported probability measure on W .

14

LAURENT BARTHOLDI AND ANNA ERSCHLER

If the expected inverted orbit growth of the projected random walk pX, µq grows
sublinearly, then hpµq “ 0; so the random walk on pW, µq has trivial PoissonFurstenberg boundary.
Lemma 5.2. Let G be a group of subexponential word growth, and let δ : N Ñ N
be a sublinear function. Then the function
v ` pnq :“ #tpg1 , . . . , gk q P Gk | k ď δpnq, }g1 } ` ¨ ¨ ¨ ` }gk } ď nu

grows subexponentially.

Proof. Let vpnq denote the growth function of G; then by hypothesis, for every
ǫ ą 0, there exists C such that log vpnq ď ǫn ` C. We then estimate
ÿ
ÿ
ÿ
v ` pnq “
vpn1 q ¨ ¨ ¨ vpnk q
0ďmďn 0ďkďδpnq n1 `¨¨¨`nk “m

ˆ
˙
n ` δpnq ´ 1
ď nδpnq
max
vpn1 q ¨ ¨ ¨ vpnδpnq q.
n1 `¨¨¨`nδpnq “n
δpnq
˘
`
is subexponential when δ is
Let us show that the binomial coëfficient n`δpnq´1
δpnq
sublinear. We use the following simple approximation for binomial coëfficients,
which comes from Stirling’s formula for n!:
ˆ ˙ d
ˆ ˙´k ˆ
˙k´n
n
2πn
k
n´k
«
,
k
kpn ´ kq n
n
in the sense that the quotient tends to 1 as n, k Ñ 8. In particular, if k ď n{2
` ˘
´ logp2πq
logpk{nq Ñ 0 as k{n Ñ 0. Therefore,
then n1 log nk ď 2 ´k
n logpk{nq `
n
ˆ
˙
˘
n ` δpnq ´ 1
1
1`
1
ǫn ` Cδpnq “ ǫ.
` lim
lim log v ` pnq ď lim log
nÑ8 n
nÑ8 n
nÑ8 n
δpnq
Since this holds for all ǫ ą 0, we have limnÑ8

1
n

log v ` pnq “ 0.



Proof of Proposition 5.1. We will show, for every n, that with positive probability
a length-n random walk lands in a subset of W of subexponential size in n.
Since µ is finitely supported, there exists a finite set Y Ď X and ř
a finite set
S Ă A, which we may assume is generating, such that supppµq Ď Y S ˆ G;
namely, the random walk modifies only positions in Y , and does at most a step in
S at these positions. Let δpnq be the expectation of the inverted orbit growth of
pG, Xq, starting at all positions in Y . By assumption, δ grows sublinearly.
We restrict ourselves to length-n trajectories Ωn whose inverted orbit visits less
than 2δpnq points. These describe a subset of trajectories of measure at least 1{2:
indeed, Erδpwqs “ δpnq ď p1 ´ µpΩn qq2δpnq whence µpΩn q ě 12 .
Let w “ w1 . . . wn P Ωn be a trajectory. Considering simultaneously all y P Y ,
the inverted orbit of w visits (a subset of) O “ tywip1q ¨ ¨ ¨ wn , . . . , ywipkq ¨ ¨ ¨ wn : y P
Y u Ď X, say for definiteness at lexicographically minimal times ip1q, . . . , ipkq; and
k ď 2δpnq. This inverted orbit is determined by the sequence of group elements
pwip1q ¨ ¨ ¨ wip2q´1 , wip2q ¨ ¨ ¨ wip3q´1 , . . . , wipkq ¨ ¨ ¨ wn q P Gk .

By Lemma 5.2, there is a subexponential number v ` pnq of possibilities for O that
may occur.
Once a subset O of X is chosen,
let us consider the endpoint w “ pf, gq of the
ř
trajectory, with g P G and f P X A. The support of f is contained in O, and the

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

15

random walk did a total of at most |Y |n steps at positions in O. Let upnq denote
the growth function of A, by assumption
subexponential. Assume
ś the random walk
ř
n
ď
|Y
|n.
Then
f
P
did nx steps at
each
x
P
O,
with
x
xPO BA pnx q, which
xPO
ř
is a subset of X A of subexponential growth, again by Lemma 5.2.
Since a product of subexponential functions is again subexponential, w belongs
to a set of subexponential growth, when O ranges over all possible inverse orbits of
trajectories in Ωn .
Finally, to estimate the asymptotic entropy of µ, it suffices to compute it on
a subset of trajectories of positive measure. Indeed, consider ǫ ą 0 and subsets
˚n
Θn Ă W n with µn pΘn q ě ǫ. If hpµq “ h ą 0, then lim ´1
n log µ pwq “ h for
8
almost every trajectory w P G , by [26, Theorem 2.1]; so
ÿ
µ˚n pgq log µ˚n pgq “ hǫ ą 0.
´
gPW
g“g1 ...gn
pgi qPΘn

It therefore suffices, as we have done, to show that the asymptotic entropy of µ
vanishes on a subset of positive measure.

The proposition implies that the symmetric finitely supported random walk on
W from Example 4.11 has trivial boundary. Indeed, any nearest neighbour random
walk on Z2` or Z2 is recurrent [2]; this property depends only on the graph, not the
random walk, see the remark before Corollary 5.7. Note also that a subgraph of a
recurrent graph is also recurrent (see again [2], or [33, Corollary 2.15]), so we need
not worry whether the random walk is degenerate or intransitive.
Remark 5.3. Implicit in the application of Lemma 5.2 is the following function
vi pn, kq that deserves further study: for a group G, with generating set S, acting
on a set X with basepoint ρ, write
vi pn, kq “ #tY Ă X | #Y “ k

and Y is the inverted orbit of an S-path of length n starting at ρu.

Indeed, the lemma was used to show that, if G is a group of subexponential growth
with sublinear inverted orbit growth δpnq, then vi pn, δpnqq is subexponential.
By comparison, consider the corresponding function for direct orbits:
vd pn, kq “ #tY Ă X | #Y “ k

and Y is the direct orbit of an S-path of length n starting at ρu.

Each directed orbit Y is a connected subset of X containing ρ; and a connected
subset of cardinality k can be traversed by a path of length 2k, so we have the
simple bound vd pn, kq ď p#Sq2k , which implies that vd pn, kq is subexponential in
n as soon as k is sublinear in n.
In contrast with the direct orbit case, it is not possible in general to bound
vi pn, kq by a function of k only. For example, consider the first Grigorchuk group G
acting on a ray X. The stabilizer of ρ is infinite; let S contain the generating set of
an infinite subgroup of it. If s2 , . . . , sn fix ρ but s1 does not, then the inverted orbit
of s1 . . . sn contains only two points tρ, ρ1 u, and ρ1 is arbitrary under the condition
dpρ, ρ1 q ď n; so vi pn, 2q „ n.
More generally, we have the obvious bound vi pn, kq ď #BX pnqk . This bound is
never tight enough for our purposes.

16

LAURENT BARTHOLDI AND ANNA ERSCHLER

We now show that in this example (or, more generally, in any torsion Grigorchuk
group) the assumption that the random walk is symmetric can be dropped, see
Corollary 5.7.
5.1. Centered Markov chains. There is a class of non-symmetric (and not necessarily reversible) Markov chains that resembles in many aspects symmetric ones.
These are chains that admit a certain “decomposition into cycles”, see [27]. In particular, it is shown by Kalpazidou in [28] that under some conditions the recurrence
of such random walks does not depend on the choice of the random walk. We will
use a version of this statement which is due to Mathieu.
Definition 5.4 ([30, Definition 2.1]). Let V be an oriented graph, possibly with
loops and multiple edges. A centered Markov chain on V is defined as follows. There
is a collection of tγi u of oriented cycles on V , which we assume edge-self-avoiding
but not necessarily vertex-self-avoiding. Each cycle has a weight qi . Each edge
must belong to exactly one cycle (but remember, we allow multiple edges!). For
any vertex x in V , the sum of the weights of all cycles passing through x (counted
with multiplicity, if the cycle passes several times through x) is equal to one.
The Markov chain has the vertex set of V as set of states. The probability of
moving in one step of the Markov chain from vertex x to vertex y is given as follows:
choose a cycle containing x according to the weights qi ; then move to the successor
of x along that cycle. We write the transition kernel as follows:
ÿ
qi .
qpx, yq “
i:px,yqPγi

(The definition above is a particular case of [30, Definition 2.1], and is slightly
more general than [30, Example 2.4]. Indeed, observe that under our assumption
qi ď 1 and, in the notation of [30], we can consider mpxq “ 1 for all x P V ).
Centered Markov chains are generalizations of symmetric Markov chains: indeed,
in any non-oriented graph, replace each edge by two oriented edges that form a cycle
of length two; set the weight of that cycle to be the weight of the original edge.
In fact, the general definition of centered Markov chains in [30, Definition 2.1] is a
generalization of reversible Markov chains.

Remark 5.5. (i) If µ is a finitely supported measure on a group G and all elements
of the support of µ are torsion, then the random walk pG, µq is a centered Markov
chain on the Cayley graph of G with generating set supppµq. This is used in [30]
to prove Carne-Varopoulos estimates for random walks on torsion groups.
(ii) More generally, if µ is a finitely supported measure on a group G and all
elements of the support of µ are torsion, and G acts on a set X, then the random
walk on X is a centered random walk on the Schreier graph of pG, Xq.
Proof. For each g P supppµq there exists a minimal m ě 1 such that g m “ 1. For
each such g, consider all the cycles of the form px, xg, . . . xg m´1 q, and define the
weight of this cycle to be µpgq. The random walk on X induced by the measure µ
is the same as the centered Markov chain defined by these weighted cycles.

Lemma 5.6 (Mathieu, [30, Proposition 2.13(iii)]). Let V be a connected locally
finite graph, and let q be a centered Markov chain on V . Let q0 be the associated
symmetric Markov chain: q0 px, yq “ 21 pqpx, yq ` qpy, xqq.
Then the chain q is recurrent if and only if q0 is recurrent.

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

17

Recall that a random walk is uniformly irreducible if its one-step transition probabilities are uniformly bounded from below. It is well known (see e.g. [33, Corollary 3.5]) that if V 0 is a non-oriented graph, the recurrence/transience of uniformly
irreducible symmetric random walks on V 0 does not depend on the probability
measure, but only on the graph. Thus, by the lemma, if V is recurrent considered
as a non-oriented graph, then all centered Markov chains on X are recurrent.
The following example (statements (i) and (ii) of the corollary below) gives a
negative answer to the question of Kaimanovich and Vershik from [26]:
Corollary 5.7 (= Theorem A). Let G be any Grigorchuk torsion group, for example G012 , and let X be an orbit of G on the tree’s boundary. Let A be a non-trivial
finite group, and set W “ A ≀XˆX pG ˆ Gq. Then
(i) W has exponential word growth;
(ii) any finitely supported random walk on W has trivial Poisson-Furstenberg
boundary;
(iii) any finitely supported random walk on W has zero drift.
Proof. (i) follows from Theorem 4.1; see its application in Example 4.11.
For (ii), take a finitely supported measure µ on G ˆ G and consider the induced
random walk on X 2 . Since W is a torsion group, the random walk on X 2 is a
centered Markov chain. By [4, §5.1], the graph X is Z` or Z, so the random
walk on X 2 is a centered Markov chain on a graph which is a subgraph of Z2 . By
Lemma 5.6, this random walk is recurrent. Therefore, we can apply Proposition 5.1,
and conclude that the random walk pW, µq has trivial boundary. See Figure 1 for
a portion of the Schreier graph X ˆ X.
For (iii), take a finitely supported measure µ on W . Any finitely supported
measure has finite entropy. We have shown in (ii) that the random walk pW, µq has
trivial boundary. Therefore, by the entropy criterion, hpµq “ 0.
Mathieu has proven in [30] that Carne-Varopoulos estimates hold for centered
Markov chains. In particular, he has shown that, for centered random walks on
groups, hpµq “ 0 if and only if ℓpµq “ 0. We conclude that ℓpµq “ 0.

6. Further examples. Drift estimates for self-similar random walks
Self-similar groups are groups G endowed with a homomorphism φ : G Ñ G ≀ Sd ,
with Sd the symmetric group on t1, . . . , du. By iterating the map φ, every selfsimilar group acts on sets of cardinality dn , for all n P N; these sets form the levels
of a d-regular rooted tree. If we write φpgq “ xxg1 , . . . , gd yyπ, then the permutation
π P Sd describes the action of g on the neighbours of the root, while g1 , . . . , gd
describe recursively the action of g on the subtrees attached to the root.
A fundamental example is the first Grigorchuk group G012 . It is the self-similar
group characterized as follows: it is generated by four elements a, b, c, d; it acts
faithfully on the 2-regular rooted tree; and φ is given on the generators by
(2)

φpaq “ xx1, 1yyp1, 2q,

φpbq “ xxa, cyy,

φpcq “ xxa, dyy,

φpdq “ xx1, byy.

Self-similar random walks were introduced by the first author and Virag in [5];
see below for the definition. In that paper, they show that the so-called “Basilica
group” admits a self-similar random walk, and then this self-similar measure is used
to show that this random walk has zero drift with respect to some metric (which
is not a word metric, in contrast with usual definition of the drift).

18

LAURENT BARTHOLDI AND ANNA ERSCHLER

Kaimanovich uses a similar idea in [25], but works with the entropy of the random
walk hpµq instead. The main idea of these papers is to use the self-similarity of the
random walk to prove that its asymptotic entropy vanishes. In a similar way one
can use self-similar measures in order to estimate Hµ pnq, see [6, Proposition 4.11].
The following lemma is similar to that proposition.
Definition 6.1. A self-similar sequence of groups is a sequence pG1 , G2 , . . . q of
groups, with homomorphisms φi : Gi Ñ Gi`1 ≀ Sd .
Let µi be a measure on Gi . It defines a random walk on Gi`1 ˆ t1, . . . , du, via
φi : if φi pgq “ xxg1 , . . . , gd yyπ, then the walk moves from ph, iq to phgi , πpiqq with
probability µi pgq. The renormalization of µi is the measure µ1i on Gi`1 defined by
running µi on p1, 1q till it reaches Gi`1 ˆ 1; in formulas,
ÿ1
µ1i pgq “
µi ph1 q ¨ ¨ ¨ µi phn q,
h1 ,...,hn PGi`1

where the sum extends over all n-tuples ph1 , . . . , hn q such that φi ph1 ¨ ¨ ¨ hn q P tgu ˆ
d
Gd´1
i`1 ˆ stabSd p1q and φi ph1 ¨ ¨ ¨ hj q R Gi`1 ˆ stabSd p1q for all j ă n.
A self-similar sequence of measures on a sequence pGi q of groups is a sequence
pµ1 , µ2 , . . . q of measures, each µi a measure on Gi , and a sequence of numbers
pα1 , α2 , . . . q in r0, 1s, such that µ1i “ p1 ´ αi qδ1 ` αi µi`1 , namely µ1i is a convex
combination of µi`1 and the Dirac measure at 1 P Gi`1 . It is a lazy random walk,
with laziness αi .
The following lemma generalizes [6, Proposition 4.11]; see also [1, 9]:
Lemma 6.2. Let pGi q be a self-similar sequence of groups, and let pµi q be a selfsimilar sequence of measures on pGi q, with laziness pαi q. Assume supi Hpµi q ă 8.
Then there exists a constant K such that
log d
.
HG1 ,µ1 pnq ď Knβ for all n, with β “
log d ´ logpsup αi q
Proof. A random variable in Gi is determined by its projection to Sd and by its d
renormalizations in Gi`1 . Say an n-step walk starting at 1 visits ni times point i,
for all i P t1, . . . , du. Then
Hµi pnq ď Er

d
ÿ

j“1

Hµ1i pni q | n1 ` n2 ` ¨ ¨ ¨ ` nd ď ns ` d log d.

For ν a measure, we extend Hν pnq to real arguments n P R by interpolating linearly:
Hν pp1 ´ θqn ` θpn ` 1qq “ p1 ´ θqHµ pnq ` θHµ pn ` 1q. By [26, Proposition 1.3],
for n P N the numbers Hν pn ` 1q ´ Hν pnq decrease monotonically to hpνq; so the
affine extension Hν : R Ñ R is a concave function. Therefore,
Hµi pnq ď dHµ1i pn{dq ` d log d.
Next, for all m P N,

m ˆ ˙
ÿ
m k
Hµ1i pmq “
αi p1 ´ αi qm´k Hµi`1 pkq;
k
k“0

the binomial distribution has mean αi m, so again by concavity
Hµ1i pmq ď Hµi`1 pαi mq.

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

19

Therefore,
Hµi pnq ď dHµi`1 pnαi {dq ` d log d.
We then iterate this relation, to obtain
Hµ1 pdk {α1 ¨ ¨ ¨ αk q ď d log d ` ¨ ¨ ¨ ` dk log d ` dk Hpµk`1 q ď Kdk

for a constant K, and we are done.



For any finitely supported random walk on a finitely generated group G, there
exist constants C, D ą 0 such that
˙2
ˆ
Lpnq
Hpnq
Lpnq
ď
ďD
(3)
C
n
n
n

for all n; the first inequality follows from Varopoulos’s long range estimates, see
e.g. [14, page 1201]. These inequalities hold, more generally, for any random walk
with finite second moment, see [18, Corollary 9.(ii)].
Kaimanovich observes in [25] that the first Grigorchuk group admits a self-similar
measure µ with laziness 1{2. An example of such a measure is µ defined by µp1q “
5{12, µpaq “ 1{3, µpbq “ µpcq “ µpdq “ 1{12: for this measure one has µ1 “ 1{2δ1 `
1{2µ. We can therefore apply Lemma 6.2 with d “ 2 and α “ 1{2 and conclude
that the entropy function Hµ pnq of this random walk satisfies Hpnq ď Kn1{2 .
Now take a sequence ω “ pv1 , v2 , . . . q P t0, 1, 2u8 , and define ωi “ pvi , vi`1 , . . . q
its shift; consider the corresponding sequence of Grigorchuk groups Gi “ Gωi ,
which form a similar sequence. The standard generators of Gi are still written
a, b, c, d. On each Gi define a probability measure µi by µi p1q “ 5{12, µi paq “ 1{3,
µi pbq “ µi pcq “ µi pdq “ 1{12. These form a self-similar sequence of measures on
pGi q, and, as in [25], one has µ1i “ 1{2δ1 `1{2µi`1 . Combining this with Lemma 6.2
and (3), we get the
Corollary 6.3. On every Grigorchuk group Gω , there exists a symmetric nondegenerate finitely supported measure µ and a constant C such that Hpnq ď Cn1{2
and Lpnq ď Cn3{4 for all n P N.
Remark 6.4. Examples of Grigorchuk groups above stress the importance of the
fact that [5] works with drift with respect to a special non-word metric, and [25]
works with entropy of random walks, and not with drift: although Grigorchuk
groups admit self-similar measure sequences with laziness 1{2, it is not true that
on these groups one has Lpnq ď Cn1{2 . Indeed, it is shown in [16, Corollary 1] that
any simple random walk on the first Grigorchuk group satisfies Lpnq ě nκ for some
κ ą 1{2 and infinitely many n’s.
Example 6.5. Let G1 , G2 be two Grigorchuk groups. Let respectively X1 , X2 be
orbits for their action on the boundary of the rooted tree. By Corollary 6.3, the
assumption of Theorem 4.1 is satisfied. Therefore, for any non-trivial group A, the
wreath product W “ A ≀X1 ˆX2 G1 ˆ G2 has exponential word growth.
If G1 and G2 are torsion groups, then every finitely supported measure on W has
trivial boundary, so these are other negative answers to the Kaimanovich-Vershik
question.
Example 6.6. Let G1 “ G2 “ H be the Grigorchuk torsion-free group of subexponential growth from [22]; recall that H maps onto G012 , and therefore acts on
an orbit X of the Grigorchuk group on the boundary of the rooted tree. Consider

20

LAURENT BARTHOLDI AND ANNA ERSCHLER

the wreath product W “ Z ≀XˆX pH ˆ Hq. Then W is a torsion-free group of
exponential growth, such that every finitely supported measure on W has trivial
Poisson-Furstenberg boundary.
Proof. Clearly W is torsion-free, as an extension of torsion-free groups. Since the
action of H ˆ H on X ˆ X actually comes from the action of G012 ˆ G012 , the random walk µ on X ˆX induced by H ˆH is the same as a random walk induced by a
measure on G012 ˆG012 . Therefore, µ defines a centered random walk on a subgraph
of Z2 . Applying Lemma 5.6 as we did in the proof of Corollary 5.7(ii), we conclude
that µ induces a recurrent random walk. By Lemma 3.1, the expected inverted
orbit growth is sublinear. Since both Z and H ˆ H have subexponential growth,
Proposition 5.1 gives that every finitely supported measure on W has trivial boundary. On the other hand, W has exponential word growth since, by Theorem 4.1,
its quotient Z ≀XˆX pG012 ˆ G012 q already has exponential growth.

7. Lipschitz imbeddings of regular trees
We gave, in Theorem 4.1, a general criterion for a permutational wreath product
of a product of two groups to have exponential word growth. For most of the
examples we produce, it does not seem at all straightforward to check without
using random walks that they have exponential growth.
Below is one example in which we prove more directly that the growth of an
inverted orbit of pG, Xq is linear (and hence that the word growth of the corresponding wreath product A ≀X G is exponential). We consider G “ G012 , acting
diagonally on X “ X1 ˆ X2 , where X1 and X2 are orbits under G012 of the rays
ρ1 “ p12q8 and ρ2 “ p21q8 respectively (regarded as points of the boundary of the
rooted tree t1, 2u˚ on which G012 acts).
Proposition 7.1. Let wn be the word over ta, b, c, du of length „ p2{ηqn constructed
as follows. Write Ω1 “ tab, ac, adu˚ Ă Ω “ ta, b, c, du˚ , consider the substitution
ζ : Ω1 Ñ Ω1 given by
ζ : ab ÞÑ abadac,

ac ÞÑ abab,

ad ÞÑ acac,

and consider the word wn “ ζ n padq.
For a word w “ g1 . . . gℓ define δpwq “ #tpρ1 , ρ2 qgi ¨ ¨ ¨ gℓ | 0 ď i ď ℓu with
ρ1 “ p12q8 and ρ2 “ p21q8 . Then for all n ě 1 we have δpwn q “ |wn | ` 1; namely,
all points on the inverse orbit of wn are distinct.
The words wn in the statement of the lemma above were used in [7, Proposition 4.7] to estimate the growth of the permutational wreath product of the first
Grigorchuk group.
Proof. Write wn “ g1 . . . gℓ and ρ “ pρ1 , ρ2 q. We are to show that for all i ă j
we have ρgi ¨ ¨ ¨ gℓ ‰ ρgj ¨ ¨ ¨ gℓ ; or, equivalently, that ρgi ¨ ¨ ¨ gj´1 ‰ ρ, namely, no
subword of wn fixes ρ.
Let F denote the free product xa | a2 y ˚ xb, c, d | b2 , c2 , d2 , bcdy; its elements may
be identified with those words in Ω that alternate in ‘a’ and ‘b, c, d’ letters, and
we have a natural quotient map F Ñ G. The map φ : G Ñ G ≀ S2 lifts to a map
a
φ : F Ñ F ≀S2 by the same defining formula (2). We note φpwn q “ xxwn´1
, wn´1 yy as
an equality in F , and more generally if u is a subword of wn then φpuq “ ǫs xxu1 , u2 yy
with ´1 ď |u1 | ´ |u2 | ď 1 and u1 , u2 are subwords of wn´1 which overlap on all

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

21

d b d c b c d b d b c b d b d c b c d b d c b c d b d
a
a
a
a
a
a
a
a
ρ1 c
c
c
c
c
d
d
d
d
d
b c
da
b
c d
ba
d
b c
da
c
b d
c ρ2
a
d
b c
da
d
b c
da
d
b c
da
c
b d
c

ρ

Figure 1. The Schreier graph of G012 on G012 {stabpρ1 q ˆ
G012 {stabpρ2 q. Edges are indicated by colours: black for a,
red/green/blue for b{c{d.
except possibly one letter. Let η « 2.46 be the positive root of X 3 ´ X 2 ´ 2X ´ 4;
then |u1 | « |u|{η.
Assume now for contradiction that a non-trivial subword gi . . . gj´1 of wn fixes
pnq
pnq
pmq
pmq
ρ. Set u1 “ u2 “ gi . . . gj´1 and for all m ă n define subwords u1 , u2 of wm
pm`1q
pmq
pm`1q
pmq
pmq
by φpu1
q “ xx..., u2 yy and φpu2
q “ xxu1 , ...yy. Then ρ1 u1 “ ρ1 and
pmq
pmq
ρ2 u2 “ ρ2 for all m P t1, . . . , nu. Let m be maximal such that |u1 | ď 4 and
pmq
pmq
pmq
|u2 | ď 4; in particular u1 and u2 are non-trivial. Now the only possibilities
pmq
for a non-trivial word of length ď 4 to fix ρ1 or ρ2 are u1 P td, aca, acad, dacau
pmq
and u2 P tc, ada, adac, cadau, and none of these words have sufficient overlap. 
Let us tentatively introduce the following notion. Consider a group G acting
transitively on a set X, and fix ρ P X. Say that the growth of inverted orbits of G
on pX, ρq is strongly linear, if there exists a finite generating set S of G such that
for each n P N there exists a word wn of length n over elements of S such that the
inverted orbit of wn has exactly n ` 1 points (recall that this is the maximal value
it may assume).
Proposition 7.1 shows that pG, Xq has strongly linear growth. Observe the following consequence of strongly linear growth of inverted orbits:
Lemma 7.2. If G has strongly linear inverted orbit growth on X and A is nontrivial, then some Cayley graph of A ≀X G contains an imbedded copy of the infinite
binary rooted tree.

22

LAURENT BARTHOLDI AND ANNA ERSCHLER

Proof. Let a0 ‰ a1 be two elements of A. Let S 1 be a generating set of G for which
the inverted orbits grow strongly linearly. Let S be a generating set of W :“ A ≀X G
containing ta0 , a1 u ˆ S 1 . For n P N, let wn “ g1 ¨ ¨ ¨ gn be a word of length n
visiting n points in X, and consider all words of the form aim gm ¨ ¨ ¨ ain gn for all
m P t1, ¨ ¨ ¨ , n ` 1u and all im , . . . , in P t0, 1u. We claim that these are the vertices
of the height-n binary rooted tree in the Cayley graph of W .
First, these elements are all distinct: consider aim ¨ ¨ ¨ gn and ai1 1 ¨ ¨ ¨ gn . If m ‰
m
m1 then their projections to G are distinct; while if m “ m1 then, because the
inverted walk gm ¨ ¨ ¨ gn visits n ´ m ` 1 distinct positions, the elements are distinct
as soon as ij ‰ i1j for some j P tm, . . . , nu.
Because all aim gm belong to S, there is an edge in the Cayley graph from
aim gm ¨ ¨ ¨ ain gn to aim`1 gm`1 ¨ ¨ ¨ ain gn ; these edges form a binary tree, rooted at 1.
Since n was arbitrary, we obtain for all n a binary tree of height n and rooted
at 1. A classical diagonal argument then extracts from this sequence an infinite
binary rooted tree.

Corollary 7.3. The wreath product W “ A ≀X1 ˆX2 G012 has exponential word
growth, for X1 the orbit of ρ1 “ p12q8 and X2 is the orbit of ρ2 “ p21q8 . Moreover,
some Cayley graph of W contains an infinite binary rooted tree.
It also follows from 4.1 that W has exponential growth; indeed, G012 and G012 ˆ
G012 are commensurable, so we are, up to finite index, in the situation of a product
of groups G1 ˆ G2 acting on X1 ˆ X2 . We have elected to give a direct proof that
W has exponential growth, because we also deduce along the way that W contains
trees in its Cayley graph.
A classical question of Rosenblatt [32] asks whether every group of exponential
growth admits a Lipschitz imbedding of the infinite binary rooted tree. A result
of Benjamini and Schramm [8] implies that every non-amenable graph contains
the image a regular tree by a Lipschitz imbedding; so it is sufficient, to answer
positively Rosenblatt’s question, to exhibit a non-amenable subgraph. Rosenblatt’s
question is answered positively for virtually soluble groups (the group contains a
free subsemigroup) and non-amenable groups (since their Cayley graph is nonamenable), but is open in general. The group W we construct in this article also
contains Lipschitzly imbedded infinite binary rooted trees (by Lemma 7.2), though
for a different reason than those mentioned above.
References
[1] Gideon Amir and Bálint Virág, Speed exponents of random walks on groups (2013), available
at arXiv:math/1203.6226v2.
[2] Paolo Baldi, Noël Lohoué, and Jacques Peyrière, Sur la classification des groupes récurrents,
C. R. Acad. Sci. Paris Sér. A-B 285 (1977), no. 16, A1103–A1104 (French, with English
summary). MR0518008 (58 #24558)
[3] Laurent Bartholdi, The growth of Grigorchuk’s torsion group, Internat. Math. Res. Notices
20 (1998), 1049–1054, DOI 10.1155/S1073792898000622, available at arXiv:math/0012108.
MR1656258 (99i:20049)
[4] L. Bartholdi and R. I. Grigorchuk, On the spectrum of Hecke type operators related to some
fractal groups, Tr. Mat. Inst. Steklova 231 (2000), no. Din. Sist., Avtom. i Beskon. Gruppy,
5–45, available at arXiv:math/9910102; English transl., Proc. Steklov Inst. Math. 4 (231)
(2000), 1–41. MR1841750 (2002d:37017)
[5] Laurent Bartholdi and Bálint Virág, Amenability via random walks, Duke Math. J. 130
(2005), no. 1, 39–56, DOI 10.1215/S0012-7094-05-13012-5, available at arXiv:math/0305262.
MR2176547 (2006h:43001)

POISSON-FURSTENBERG BOUNDARY AND GROWTH OF GROUPS

23

[6] Laurent Bartholdi, Vadim A. Kaimanovich, and Volodymyr V. Nekrashevych, On amenability
of automata groups, Duke Math. J. 154 (2010), no. 3, 575–598, DOI 10.1215/00127094-2010046, available at arXiv:math/0802.2837. MR2730578 (2011k:20048)
[7] Laurent Bartholdi and Anna Erschler, Growth of permutational extensions, Invent. Math. 189
(2012), no. 2, 431–455, DOI 10.1007/s00222-011-0368-x, available at arXiv:math/1011.5266.
MR2947548
[8] Itai Benjamini and Oded Schramm, Every graph with a positive Cheeger constant contains
a tree with a positive Cheeger constant, Geom. Funct. Anal. 7 (1997), no. 3, 403–419, DOI
10.1007/PL00001625. MR1466332 (99b:05032)
[9] Jérémie Brieussel, Behaviors of entropy on finitely generated groups, Ann. Probab. 41 (2013),
no. 6, 4116–4161, DOI 10.1214/12-AOP761, available at arXiv:math/1110.5099. MR3161471
[10] Ching Chou, Elementary amenable groups, Illinois J. Math. 24 (1980), no. 3, 396–407.
MR81h:43004
[11] Yves Derriennic, Quelques applications du théorème ergodique sous-additif, Conference on
Random Walks (Kleebach, 1979), Astérisque, vol. 74, Soc. Math. France, Paris, 1980, pp. 183–
201, 4 (French, with English summary). MR588163 (82e:60013)
[12] Eugene B. Dynkin and Mikhail B. Maljutov, Random walk on groups with a finite number
of generators, Dokl. Akad. Nauk SSSR 137 (1961), 1042–1045 (Russian). MR0131904 (24
#A1751)
[13] Anna G. Dyubina, Characteristics of random walks on the wreath products of groups, Zap.
Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 256 (1999), no. Teor. Predst.
Din. Sist. Komb. i Algoritm. Metody. 3, 31–37, 264, DOI 10.1023/A:1012465406149 (Russian,
with English and Russian summaries); English transl., J. Math. Sci. (New York) 107 (2001),
no. 5, 4166–4171. MR1708557 (2000g:60012)
[14] Anna G. Erschler, On drift and entropy growth for random walks on groups, Ann. Probab.
31 (2003), no. 3, 1193–1204. MR1988468 (2004c:60018)
, Liouville property for groups and manifolds, Invent. Math. 155 (2004), no. 1, 55–80,
[15]
DOI 10.1007/s00222-003-0314-7. MR2025301 (2005i:43023)
[16]
, Critical constants for recurrence of random walks on G-spaces, Ann. Inst. Fourier
(Grenoble) 55 (2005), no. 2, 493–509. MR2147898 (2006c:20085)
[17]
, Poisson-Furstenberg Boundaries, Large-Scale Geometry and Growth of Groups,
Proc. ICM Hyderabad, India, 2010, pp. 681–704.
[18] Anna G. Erschler and Anders Karlsson, Homomorphisms to R constructed from random
walks, Ann. Inst. Fourier. 60 (2010), no. 6, 2095-2113.
[19] Lorenz A. Gilch, Acceleration of lamplighter random walks, Markov Process. Related Fields
14 (2008), no. 4, 465–486. MR2473764 (2010c:60142)
[20] Rostislav I. Grigorchuk, On the Milnor problem of group growth, Dokl. Akad. Nauk SSSR
271 (1983), no. 1, 30–33. MR85g:20042
, Degrees of growth of finitely generated groups and the theory of invariant means,
[21]
Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 5, 939–985. English translation: Math.
USSR-Izv. 25 (1985), no. 2, 259–300. MR86h:20041
, Degrees of growth of p-groups and torsion-free groups, Mat. Sb. (N.S.) 126(168)
[22]
(1985), no. 2, 194–214, 286. MR86m:20046
[23]
, Superamenability and the occurrence problem of free semigroups, Funktsional. Anal.
i Prilozhen. 21 (1987), no. 1, 74–75. MR88k:43002
[24] Ildar A. Ibragimov and Yu. V. Linnik, Independent and stationary sequences of random
variables, Wolters-Noordhoff Publishing, Groningen, 1971. With a supplementary chapter by
I. A. Ibragimov and V. V. Petrov; Translation from the Russian edited by J. F. C. Kingman.
MR0322926 (48 #1287)
[25] Vadim A. Kaimanovich, “Münchhausen trick” and amenability of self-similar groups, Internat. J. Algebra Comput. 15 (2005), no. 5-6, 907–937. MR2197814
[26] Vadim A. Kaimanovich and Anatoly M. Vershik, Random walks on discrete groups: boundary
and entropy, Ann. Probab. 11 (1983), no. 3, 457–490. MR704539 (85d:60024)
[27] Sophia L. Kalpazidou, Cycle representations of Markov processes, 2ed, Applications of Mathematics (New York), vol. 28, Springer, New York, 2006. Stochastic Modelling and Applied
Probability. MR2226353 (2007c:60003)
, On multiple circuit chains with a countable infinity of states, Stochastic Process.
[28]
Appl. 31 (1989), no. 1, 51–70, DOI 10.1016/0304-4149(89)90102-6. MR996611 (90j:60068)

24

LAURENT BARTHOLDI AND ANNA ERSCHLER

[29] Anders Karlsson and François Ledrappier, Linear drift and Poisson boundary for random
walks, Pure Appl. Math. Q. 3 (2007), no. 4, Special Issue: In honor of Grigory Margulis.,
1027–1036. MR2402595 (2009d:60133)
[30] Pierre Mathieu, Carne-Varopoulos bounds for centered random walks, Ann. Probab. 34
(2006), no. 3, 987–1011, DOI 10.1214/009117906000000052. MR2243876 (2008d:60094)
[31] Vladimir A. Rokhlin, Lectures on the entropy theory of transformations with invariant measure, Uspehi Mat. Nauk 22 (1967), no. 5 (137), 3–56 (Russian). MR0217258 (36 #349)
[32] Joseph Max Rosenblatt, Ergodic and mixing random walks on locally compact groups, Math.
Ann. 257 (1981), no. 1, 31–42, DOI 10.1007/BF01450653. MR630645 (83f:43002)
[33] Wolfgang Woess, Random walks on infinite graphs and groups, Cambridge University Press,
Cambridge, 2000. MR1743 100
E-mail address: laurent.bartholdi@gmail.com
École Normale Supérieure, Paris and Georg-August Universität zu Göttingen
E-mail address: anna.erschler@ens.fr
École Normale Supérieure, Paris

