INVERTED ORBITS OF EXCLUSION PROCESSES,
DIFFUSE-EXTENSIVE-AMENABILITY AND
(NON-?)AMENABILITY OF THE INTERVAL EXCHANGES

arXiv:1804.01981v1 [math.GR] 5 Apr 2018

CHRISTOPHE GARBAN

Abstract. The recent breakthrough works [6, 8, 9] which established the
amenability for new classes of groups, lead to the following question: is the
action W (Zd ) y Zd extensive-amenable? (Where W (Zd ) is the wobbling group
of permutations σ : Zd → Zd with bounded range). This is equivalent to asking
d
d
whether the action (Z/2Z)(Z ) o W (Zd ) y (Z/2Z)(Z ) is amenable. The d = 1
and d = 2 and have been settled respectively in [6, 8]. By [9], a positive answer
to this question would imply the amenability of the IET group. In this work, we
give a partial answer to this question by introducing a natural strengthening of
the notion of extensive-amenability which we call diffuse-extensive-amenability.
Our main result is that for any bounded degree graph X, the action W (X) y
X is diffuse-extensive-amenable if and only if X is recurrent. Our proof is based
on the construction of suitable stochastic processes (τt )t≥0 on W (X) < S(Zd )
whose inverted orbits
[
Ōt (x0 ) = {x ∈ X, ∃s ≤ t, τs (x) = x0 } =
τs−1 ({x0 })
0≤s≤t

are exponentially unlikely to be sub-linear when X is transient. This result
leads us to conjecture that the action W (Zd ) y Zd is not extensive-amenable
when d ≥ 3 and that a different route towards the (non-?)amenability of the
IET group may be needed.

1. Introduction
1.1. IET group, wobbling group W (Zd ) and criteria of amenability. The
IET group (=group of Interval Exchanges Transformations) is the group of càdlàg
piecewise-translation bijections g from T = R/Z → R/Z s.t. the set
t(g) := {g(x) − x mod 1, x ∈ T} ⊆ T
is finite. Interval Exchanges Transformations have been used extensively in the
realm of dynamical systems, for example in the analysis of polygonal billards
with rational angles. See the survey by Viana [16].
Katok asked long ago whether the free group F2 can be embedded as a subgroup in IET. Even though the answer to this question remains elusive, some
progress has been done over the last decade: for example it has been proved in
[4] that for generic pairs g1 , g2 ∈ IET, the sub-group hg1 , g2 i < IET is not free.
Another natural open problem in this area is to ask the following question (see
[3]):
Question 1.1. Is the IET group amenable ?
1

2

CHRISTOPHE GARBAN

Note that one does not endow the IET group with any topology here. Therefore
amenability is equivalent to the fact that all sub-groups H = hg1 , . . . , gk i < IET
of finite type are amenable.
We will use throughout the following key fact: for any {g1 , . . . , gk } ⊆ IET, the
sub-group H = hg1 , . . . , gk i can be embedded in the group of permutations of an
¯
¯ m} are uniquely determined by
Euclidean lattice Zd × Z/mZ. The parameters {d,
g1 , . . . , gk and rkQ (g1 , . . . , gk ) := d¯ is called the rational rank of the sub-group
H. Let us briefly outline how it works.
¯ m} are obtained as follows: consider the sub• First, the parameters {d,
group Λ < T = R/Z defined by
Λ = Λ(H) := ht(g1 ) ∪ t(g2 ) ∪ . . . ∪ t(gk )i ⊆ T .
S
Note that Λ is defined equivalently as g∈H t(g) and thus does not depend
on the choice of generators of H. Abelian sub-groups of the circle are
¯
¯
of the form Λ ' Zd × Z/mZ with m ≥ 1 (if m = 1, it is just Zd ).
Equivalently, one can find α1 , . . . , αd¯ ∈ R which
P are linearly
P 1independent
over Q such that the map Φ(n1 , . . . , nd¯, b) :=
ni αi + b m (mod 1) is
d¯
an isomorphism from Z × Z/mZ to Λ ⊆ T.
• One may now associate explicit permutations (σi )1≤i≤k to each interval
exchanges g1 , . . . , gk as follows: for each 1 ≤ i ≤ k, define
 d¯
¯
Z × Z/mZ → Zd × Z/mZ
σi :
(~n, b) 7→ Φ−1 ◦ gi ◦ Φ(~n, b)

See for example [9]. In order to avoid carrying the finite group Z/mZ throughout,
note that these permutations can always be viewed as permutations on a (possibly
¯ and if
larger) Euclidean lattice Zd . This is clear if m = 1 (by taking d = d)
m ≥ 2, by identifying Z/mZ with {0, . . . , m − 1} ⊆ Z, we may view {σi }1≤i≤k as
¯
¯
permutations on a “slab graph” Zd × {0, . . . , m − 1} ⊆ Zd=d+1 .
It is easy to check that not only σ1 , . . . , σk belong to the symmetric group
S(Zd )1 but they also belong to the so-called wobbling group W (Zd ) of Zd defined
for general graphs as follows:
Definition 1.2 (See [7]). Let G = (X, E) be a locally-finite connected graph. The
wobbling group W (X) is defined as:
n
o
W (X) := σ ∈ S(X), s.t. range(σ) := sup{dG (x, σ(x))} < ∞ ,
(1.1)
x∈X

where S(X) is the set of all permutations σ : X → X.
We will equip W (X) (resp. S(X)) with the topology T of pointwise convergence
T
where σn −→ σ ∈ W (X) (resp. S(X)) if and only if for any x ∈ X, σn (x) →
σ(x). This topology is metrizable, for example using the following distance dx0
defined on W (X) (resp. S(X)) for any root-vertex x0 ∈ X: let dx0 (σ, σ̃) = 2−n if
−1
−1
σ|B(x0 ,n) = σ̃|B(x0 ,n) and σ|B(x
= σ̃|B(x
and at least one of these two equalities
0 ,n)
0 ,n)
fails for the ball B(x0 , n + 1). It is easy to check that equipped with this distance,
the metric space (S(X), dx0 ) is a Polish space.
1Throughout

this paper, S(Zd ) is the space of all permutations σ : Zd → Zd , in particular
they typically do not have a finite support.

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

3

Let us introduce a family of compact subsets Wr (X) of W (X) indexed by r ∈ N+
which will be used throughout. For any r ≥ 1, let
Wr (X) := {σ ∈ W (X), s.t. range(σ) ≤ r} .

(1.2)

(Note that Wr (X) is not a subgroup of W (X)).

Remark 1.3.
¯
(1) If one prefers to stick to permutations on the abelian group Λ ' Zd ×Z/mZ,
¯
the permutations σi would leave in the wobbling group W (X = Zd ×Z/mZ)
for the natural graph structure on X.
(2) The wobbling groups W (Zd ) have been studied recently for example in
[7].
(3) There exist finitely generated sub-groups of W (Zd ) that cannot be obtained
from the group IET through the above procedure. See Remark 1.6 below.
The above discussion provides us with an explicit embedding of H = hg1 , . . . , gk i <
IET into hσ1 , . . . , σk i < W (Zd ). As such the amenability of IET is equivalent to
the amenability of ANY of these finite-type subgroups of {W (Zd ), d ≥ 1}.
In what follows, we shall fix some {g1 , . . . , gk } in IET and we will investigate
criteria of amenability for its associated group of permutations G := hσ1 , . . . , σk i <
W (Zd ). In order to list some criteria for the amenability of G < W (Zd ), it is
useful to introduce the Cayley graph Γ on G for the symmetric generating set
S = {σ1±1 , . . . , σk±1 }.
List of equivalent criteria of amenability. We list below some criteria of
amenability in our special case of G = hσ1 , . . . , σk i < W (Zd ) but the equivalence
of these criteria holds much more generally for any finite-type groups. (See for
example [14] for a complete list of criteria).
(1) G-invariant mean. There exists a finite and finitely additive measure
m on G which is G-invariant.
(2) Fölner sequence. There exists a sequence of finite subsets Fn % G, s.t.
|∂Fn |/|Fn | → 0 (where the boundary of a set J is, say, the edge boundary
of J in the Cayley graph Γ).
(3) Kesten (version 1). There exists a symmetric probability measure µ
supported on a finite generating set of G which is such that if {si }i≥1
are i.i.d random variables in W (Zd ) with si ∼ µ, then for any  > 0,
the random walk τn := sn ◦ sn−1 ◦ . . . s1 returns to the identity (i.e.
Id : Zd → Zd ) at even times 2n with probability p2n larger than e−n when
n is large enough.
(4) Kesten (version 2). The above estimate on the return probability of
(symmetric) random walks holds for any symmetric probability measure
µ on a finite subset of G.
In particular, the amenability of IET is equivalent to proving that for any
fixed {g1 , . . . , gk } ⊆ IET, the random walk on permutations in W (Zd ) < S(Zd )
induced by the uniform measure µ on S = {σi±1 }1≤i≤k returns to IdZd →Zd with
probability larger than e−n for any  > 0 and n large enough.
1.2. A new criterion for amenability. The works [6, 8, 9] obtained a striking
new criterion to establish the amenability a large class of groups. In order to

4

CHRISTOPHE GARBAN

introduce their criterion in the case of IET, we need the following notion of
inverted orbit.
Definition 1.4. Let (τn )n≥0 be a sequence of elements in S(Zd ) (for example a
random walk with values in S(Zd )). For each n ≥ 0, the inverted orbit of the
origin is the subset On ⊆ Zd defined as
[
On := {x ∈ Zd , ∃j ∈ {0, 1, . . . , n}, τj (x) = 0} =
τj−1 ({0}) .
0≤j≤n

This new criterion from [6, 8, 9] can be stated as follows for IET (we refer to
[9] for other equivalent formulations):
Theorem 1.5 (“Inverted orbit criterion” [9]).
Fix any {g1 , . . . , gk } ⊆ IET. Let {σ1 , . . . , σk } be their associated permutations in
W (Zd ), with d ≥ rk(g1 , . . . , gk ).
The subgroup H = hg1 , . . . , gk i < IET is amenable if and only if the inverted
orbits {On }n≥0 of the random walk on W (Zd ) defined as
τn := sn ◦ sn−1 ◦ . . . s1 ,

k
X
1
(δσi + δσi−1 )
where si are i.i.d and ∼ µ =
2k
i=1

satisfy any of the following equivalent conditions:


−n
i) For any  > 0,
P
|O
for n large enough.
n | ≤ n ≥ e
 1 |O | 
n
ii) limn→∞ log E ( 2 )
/ log n = 0.
Note that this new criterion is both very surprising and powerful. Indeed, it is
very easy to check that the classical amenability criteria listed above imply this
one, but the converse is significantly harder ([8, 9]). To highlight this, assume that
the criterion Kesten (version 2) holds and let us show that it easily implies
the above criterion. Fix  > 0, if k is large enough then the above symmetric
random walk τn = sn ◦ sn−1 ◦ . . . s1 returns to the identity map with probability
larger than e−k . Now, let us use the fact that each of the σi belong to W (Zd ).
If h := max1≤i≤k range(σi ), in k steps, sites travel at distance at most h · k.
This implies that there exists C = C(d, h) < ∞ s.t. in k steps they are at
most C k d sites that may go through the origin along the process τ0 , τ1 , . . . , τk .
This means that on the event {τk = IdZd →Zd }, one has |Ok | ≤ C k d . Now for
any N = m · k, the probability that τN returns to the identity at every times
k, 2k, . . . , N =
e(−k )m = e−N . This implies that for any such
 mk is larger
 than−N
d
N , one has P |ON | ≤ C k ≥ e
. It is not hard to conclude that item i) holds.
We let the reader appreciate the fact that the reverse direction “Inverted orbit
criterion” ⇒ Kesten (version 2) is much less clear. See [8, 9].
Remark 1.6.
(1) One may wonder whether this amenability criterion holds for any arbitrary
subgroup hσ1 , . . . , σk i < W (Zd ), but this is known not to be the case.
Indeed it is shown in [5] that F2 < W (Zd ) for any d ≥ 1. If d = 2, and
σ1 , σ2 ∈ W (Z2 ) are s.t. hσ1 , σ2 i ' F2 , it follows from [8] that the random
walk induced by the uniform measure on {σ1± , σ2± } does satisfy items i)
and ii). Yet hσ1 , σ2 i is not amenable. This shows that it is important

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

5

somehow for this inverted orbit criterion to hold that the set {σ1 , . . . , σk }
is produced through the above procedure out of some {g1 , . . . , gk } ⊆ IET.
(2) It is not hard to check that items i) and ii) in Theorem 1.5 are equivalent.
See [9]. The reason why we stated this equivalence is that i) is somewhat
reminiscent of Kesten’s criterion while ii) has a nice interpretation in terms
of a certain lamplighter random walk on Zd . The usual lamplighter
RW on {0, 1} o Zd corresponds to a random walker on Zd which switches
on or off lamps along his way on Zd . It corresponds to the semi-direct
d
product (Z/2Z)(Z ) o Zd and this group is well known to be amenable.
The present situation corresponds to another kind of lamplighter random
walk on Zd : at each step, either all lamps switched on in Zd simultaneously
move to a new site according to a random permutation uniformly chosen
among S = {σi±1 }1≤i≤k , or a lamp is added/removed at the origin 0Zd .
See [9] for details. For an appropriate choice of finite generating set of
d
(Z/2Z)(Z ) o hσ1 , . . . ,σk i, the probability of return to the identity (0̄) ×
IdZd →Zd is exactly E (1/2)|On | . As opposed to the classical lamplighter
groups whose amenability is easy to show, the amenability of IET is
equivalent to the amenability of these different types of lamplighter groups
d
(Z/2Z)(Z ) o hσ1 , . . . , σk i. Such permutation wreath products are studied
for example in [10, 15].
1.3. Random walks in conductances. Before going further, let us briefly
introduce in this subsection a classical type of random walk on Zd which will be
used throughout this work.
Definition 1.7 (Random walk among conductances). Let C : Zd × Zd → R+ be
a symmetric kernel satisfying for any x ∈ Zd ,
X
C(x) :=
C(x, y) ∈ (0, ∞)
y

Such an operator induces a random walk {Xn }n≥0 on Zd defined as the Markov
chain on Zd satisfying for any x, y and n ≥ 0,


C(x, y)
P Xn+1 = y Xn = x :=
C(x)
The process {Xn }n≥0 is called the random walk in conductances {C(x, y)}x,y .
(Notice we may well have C(x, x) > 0 in which case the process has a positive
probability to stay at x).
The main reason why this particular type of RW will be relevant to us is
because of the following fact. For any fixed choice of {σ1 , . . . , σk } ⊆ S(Zd ), if
(τn )n≥0 is the random walk on S(Zd ) defined as τn = sn ◦ . . . s1 where si are
uniform in S = {σi±1 }1≤i≤k , then for any initial site x ∈ Zd , the stochastic process
n 7→ τn ({x}) is a random walk in conductances given by
C(x, y) := |{1 ≤ i ≤ k : σi (x) = y}| + |{1 ≤ i ≤ k : σi−1 (x) = y}| ,

(1.3)

for any x, y ∈ Zd . Clearly C(x, y) = C(y, x) and if all {σi }1≤i≤k are in the wobbling
group W (Zd ) then C has bounded-range i.e. C(x, y) = 0 if kx − yk2 > h for
some finite range h.

6

CHRISTOPHE GARBAN

For later use, we collect below some classical properties of random walks in
conductances.
Proposition 1.8 (Classical facts, see for example [13] or [11]).
Let (Xn )n≥0 be a RW among the conductances {C(x, y)}x,y∈Zd .
a) (Xn )n≥0 is reversible for the measure µ on Zd given by µ(x) := C(x) for
any x ∈ Zd . 2
b) If C has bounded-range and if d ∈ {1, 2}, then (Xn ) is recurrent.
¯
c) Same conclusion if C has bounded-range on a slab-graph Zd ×{0, . . . , m−1}
with d¯ ∈ {1, 2}.
d) If C has bounded range onZd , then there exists c > 0 s.t. for all x ∈ Zd
and all k ≥ 1, P x X2k = x ≥ ck −d/2 .
e) If there exists δ > 0 s.t. for any neighbouring sites x, y ∈ Zd (i.e. such
that kx − yk2 = 1) C(x, y) ≥ δ, then if d ≥ 3, (Xn ) is transient.

1.4. Main question addressed in this work. Recall the above “Inverted orbit
criterion” from [8, 9] is much sharper (at least in the case of IET) than classical
amenability criteria. One may then argue/hope that all specificities of the IET
group have already been used in the proof in [8, 9] that
“Inverted orbit criterion” ⇒ amenability of IET

and that only “generic” arguments are needed to conclude for the amenability of
IET. For example if the answer to the question below turns out to be positive, it
would immediately imply that IET is amenable.
Question 1.9 (See question 1.2 from [7]).
For any d ≥ 1, the following questions are equivalent:
(1) Is the action W (Zd ) y Zd extensive-amenable ?
d
d
(2) Is the action (Z/2Z)(Z ) o W (Zd ) y (Z/2Z)(Z ) amenable ?
(3) Is is true that for any finite {σ1 , . . . , σk } ⊆ W (Zd ), the inverted orbits
{On }n≥0 of the random walk (τn )n≥0 on W (Zd ) generated by the uniform
measure on S = {σi±1 }1≤i≤k satisfy items i) or ii) in Theorem 1.5 ?

To our knowledge, up to now, all natural examples of stochastic processes
(τn )n≥0 in W (Zd ) whose inverted orbits have been successfully analyzed give
support to a positive answer to the above question. Let us list the situations that
have been analyzed so far.
(1) The main technical tool in the work [6] is precisely to answer this question
when d = 1: it is proved that the action W (Z) y Z is extensive-amenable.
This property is then used in [6] to prove the amenability of the topological
full group of a Cantor system. (This gave the first example of a finitely
generated simple group which is amenable).
(2) This analysis is extended in [8] where it is shown that W (Z2 ) y Z2 is
extensive-amenable as well. More generally, it is shown that W (X) y X
is extensive-amenable if X is locally-finite and recurrent. Using this
property, the amenability of a large class of groups has is established in
[8].
2N.B.

Reciprocally, any Markov chain on Zd which is reversible for a non-degenerate measure
µ is a random walk in conductances.

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

7

(3) One particular instance of this situation (analyzed in [9]) is the case of
random walks on permutations induced by interval exchanges {g1 , . . . , gk }
whose rational rank statisfies rkQ (g1 , . . . , gk ) ∈ {1, 2}. These lead to
¯
random walks (τn )n≥0 in W (Zd × {0, . . . , m − 1}) with d¯ ∈ {1, 2}. For
any initial state x, the processes n 7→ τn ({x}) are random walks among
¯
bounded-range conductances on W (Zd × {0, . . . , m − 1}) and are therefore
recurrent by item c) above. Using this recurrence property,

 it is shown in
[9] that the inverted orbits of such processes satisfy E |On | = o(n) which
in particular implies i) in Theorem 1.5. Consequently by Theorem 1.5,
these subgroups H = hg1 , . . . , gk i of low rational rank are amenable!
(4) Another relevant example is given by the class of rigid permutations
on Zd , given by σirigid (x) := x + ei where (ei )1≤i≤d is the canonical basis of
Zd . It is not hard to show3 that items i) and ii) also hold for this specific
choice of rigid permutations {σ1rigid , . . . , σdrigid }.
(5) Our last example deals with asking the analogous question for forward
orbits rather than inverted orbits. If (τn )n≥0 is, say, the random walk on
W (Zd ) defined as τn = sn ◦ . . . s1 where si are uniform in S = {σi±1 }1≤i≤k
for some fixed choice of {σ1 , . . . , σk } ⊆ W (Zd ), then as we noticed above
the forward orbit of the origin:
[
O~n :=
τj ({0}) ,
0≤j≤n

is the nothing but the range of a random walk on Zd with bounded-range
conductances given by (1.3). In particular we see here that the geometry
of forward orbits is much easier to apprehend than the geometry of
inverted orbits4. (See also the discussion in [10]). Using classical heatkernel bounds for such conductance-random walks (item d) above), we
obtain that the probability of the event {τ2k (0) = 0} is greater than c k −d/2 ,
where c = c({σ1 , . . . , σk }) > 0. This plus the fact that maxi range(σi ) < ∞
easily implies that for any dimension d ≥ 1, one has for any  > 0,


P |O~n | ≤ n ≥ e−n , for n large enough.
Remark 1.10. Note at this stage that the last two items do not suggest that
the dichotomy recurrence/transience should play any particular role in deciding
whether the action W (Zd ) y Zd will be extensive-amenable or not.
Our goal in this paper is to go beyond these examples and to analyze what
happens for more “generic” examples of diffusions with values in W (Zd ). Indeed,
as the answer to Question 1.9 remains open when d ≥ 3, we will consider the exact
same question but for a broader class of random walks than the random walks
defined in Question 1.9, item (3). To start with we will not even restrict ourselves
to diffusions in the wobbling group W (Zd ) but we will start by investigating
Question 1.9 for random walks on the larger symmetric group S(Zd ). Without
3by

an argument very similar to Kesten, version 2 ⇒ “Inverted orbit criterion”
fact, inverted orbits naturally show up for the study of the lamplighter RW governed
d
by (Z/2Z)(Z ) o hσ1 , . . . , σk i, while the easier forward orbits (=range of RW) naturally show
d
up for the study of the classical lamplighter RW corresponding to (Z/2Z)(Z ) o Zd
4In

8

CHRISTOPHE GARBAN

requiring some natural axioms (see the classes A),B),C),D) in Definition 1.11
below), it is not hard to come up with examples of random walks on S(Zd ) with
i.i.d increments which do not satisfy items i) or ii) from Theorem 1.5. Let us
give two such examples to motivate our later axioms.
• A straighforward example of random walk on permutations which has
large inverted orbits is given by the following asymmetric process driven
by rigid permutations:
Pd τn := sn ◦ . . . ◦ s1 , with si i.i.d. and sampled
1
according to µ = d i=1 δσrigid . In this case, one clearly has |On | = n + 1
i
for all n ≥ 0. This suggests that some kind of isotropy is required to
make the question interesting. The natural axiom suggested by Question
1.9 is to look at random walks on S(Zd ) with i.i.d increments sampled
according to a symmetric probability measure µ on S(Zd ) (equipped
with the metrizable topology T from Definition 1.2). By symmetric we
mean here that for any Borel set A ⊆ S(Zd ), we require µ(A) = µ(A−1 :=
{σ, σ −1 ∈ A}). This symmetry condition is the same as the symmetry
condition required in Kesten’s criterion.
• Also, if one allows i.i.d increments with long-range behavior (i.e. permutations σ such that αR (σ) = supkxk2 ≤R {kσ(x) − xk2 } grows fast with
R), then it is not hard to come up with symmetric counter-examples.
Here is one possible way to build a long-range random walks on S(Zd ):
consider any arbitrary injective map from a 3-regular tree T3 into Z (d = 1
is enough here). Now let µ be the pushforward measure on S(Z) of the
uniform measure µ0 on matchings of T3 (see for example [13]). Let
On ⊆ T3 be the inverted orbit of the RW on S(T3 ) induced by µ0 . It is a
rather interesting warming-up problem to check that the inverted orbits
{On }n≥0 do not satisfy item i) nor ii). In particular, the pushforward
process on S(Z) driven by µ does not satisfy these items either.
1.5. Classes of diffusion on S(Zd ) considered. Given the above discussion,
we identify four classes of diffusions on S(Zd ) from the most general ones (A) to
the most restritive ones (D). Our main results will deal with (A) and (B) only.
Definition 1.11 (Four classes of diffusions on S(Zd )). We shall consider random
processes τn := sn ◦ . . . ◦ s1 , where {si }i≥1 are i.i.d and sampled according to
a symmetric and possibly diffuse Borel probability mesure µ on the space
(S(Zd ), T ). (See definition 1.2).
In particular, the family of processes {(n 7→ τn ({x}))n≥0 }x∈Zd are coupled
random walks in common conductances given by
Cµ (x, y) := µ({σ, σ(x) = y}) + µ({σ, σ(y) = x})

(1.4)

We will consider the following classes of diffusions on S(Zd ).
(A) L1 -diffusions on S(Zd ).
There exists k ∈ L1 (Zd ), s.t. for all x, y ∈ Zd , CCµµ(x,y)
≤ k(x − y). This
(x)
hypothesis prevents long-range behaviour as in the second example above.
(B) Bounded-range diffusions on W (Zd ).
We require k to be of finite support, or equivalently that the probability
measure µ is supported on some Wr (Zd ) ⊆ W (Z d ) (r ∈ N+ ). This class

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

9

will correspond to the later notion of diffuse-extensive-amenability.
See Definition 1.14.
(C) Finitely-generated diffusions on W (Zd )
One assumes that µ is finitely supported on W (Zd ). This is the same as
the notion of extensive-amenability from [8, 9] (see also question 1.9).
(D) “IET” diffusions on W (Zd ), d ≥ 1
The measure µ is supported on a finite set {σi±1 }1≤i≤k ⊆ W (Zd ) where
the permutations σi are produced through the above recipe from some
{g1 , . . . , gk } ⊆ IET.
Clearly, one has
(A) ) (B) ) (C) ) (D) ,
and a positive answer to Question 1.9 for any of these classes would imply the
amenability of IET.
1.6. Diffuse-extensive-amenability and main results. Our first main result
is to introduce a broad family of random walks (τn )n≥0 on S(Zd ) which belong to
the class (A) from Definition 1.11 and which do not satisfy items i) or ii) from
Theorem 1.5.
Theorem 1.12 (See Theorem 2.5). For any d ≥ 3, there are symmetric probability measures µ on the space (S(Zd ), T ) whose associated conductances Cµ (x, y)
defined in Definition 1.11 induce transient ransom walks on Zd and satisfy for
any x, y ∈ Zd ,
Cµ (x, y)
≤ B e−bkx−yk2 for some b, B > 0.
Cµ (x)

Furthermore, if (τn )n≥0 is the random walk on S(Zd ) induced by µ, then its
inverted orbits {On }n≥0 satisfy the following quantitative bound
 




 1 |On | 
−n log(2)P T =∞ +o(n)
P T =∞
− n+1
2
e
≤E
,
(1.5)
≤e
2


where P T = ∞ is the probability that the random walk in the conductances Cµ ,
n 7→ τn ({0}), never returns to the origin.
When d = 2, one can also find symmetric probability measures µ on (S(Z2 ), T )
which belong to the class (A) of L1 -diffusions from Definition 1.11 and which
do not satisfy items i) or ii) from Theorem 1.5. See Corollary 2.8.
These random walks on S(Zd ) will be constructed using a well-known continuous time Markov process t ∈ R+ 7→ τt ∈ S(Zd ) called the random stirring
process. This càdlàg process in S(Zd ) is a process used to analyze/build the
so-called symmetric exclusion process on Zd , which is one of the most studied
random particle systems. We will introduce the random stirring process in Section
2 below. See also [12].
Our second main result is to modify the above processes in order to obtain
random walks in class (B), that is to say with i.i.d and bounded-range increments
(i.e. µ is supported on some Wr (Zd )). These will be obtained from the above
processes by using an appropriate spatial cut-off.

10

CHRISTOPHE GARBAN

√
Theorem 1.13. For any d ≥ 3 and any r ≥ d3 de there are symmetric probability measures µ on Wr (Zd ) whose associated conductance Cµ is transient and
which induce random walks (τn )n≥0 on W (Zd ) satisfying the same exponential
decay as in (1.5).
Finally we generalize the above analysis for euclidean lattices Zd to the case of
general bounded degree connected graphs G = (X, E). We already defined the
wobbling groups W (X) and Wr (X) earlier in Definition 1.2. As suggested to
us by M. de la Salle, we introduce the following notion which strengthens in the
present setting the notion of extensive-amenability from [6, 8, 9].
Definition 1.14. Let G = (X, E) be a connected bounded-degree graph. We will
say that the action W (X) y X is diffuse-extensive-amenable if and only if
for any r ∈ N+ , any x ∈ X and any (possibly diffuse) Borel symmetric probability
measure µ supported on the compact Wr (Zd ), the induced random walk (τn )n≥0 on
W (X) has inverted orbits {OnS
(x)}n≥0 which satisfy item i) or ii) from Theorem
1.5. (In this setting On (x) := 0≤j≤n τj−1 ({x})).
Remark 1.15.
(1) Clearly, if a bounded-degree graph is diffuse-extensive-amenable, then it
must be extensive-amenable (according to the equivalent definitions in
Question 1.9 above). We do not know any examples for which the reverse
direction does not hold. See Question 5.2.
(2) More generally, if G is a topological group acting faithfully on a countable
set X, we may wish to define the action G y X to be diffuse-extensiveamenable iff for any symmetric, possibly diffuse, and compactly supported Borel probability measure µ on G, the induced random walk on
S(X) has inverted orbits satisfying items i) or ii) from Theorem 1.5. Note
that our above definition in the case where G = W (Zd ) looks slightly more
restrictive as we require µ to be supported on one of the specific compact
sets Wr (Zd ). The reason for this choice is the dichotomy recurrence v.s.
transience in the Theorem below.
We will prove the following characterisation of diffuse-extensive-amenability:
Theorem 1.16. Let G = (X, E) be a bounded degree connected graph. The action
W (X) y X is diffuse-extensive-amenable if and only if X is recurrent.
(In particular the Euclidean lattices Zd , d ≥ 3 are not diffuse-extensive-amenable).

Remark 1.17. We will not show the implication “X recurrent” implies “W (X) y X
is diffuse-extensive-amenable” as the proof is exactly the same as the proof in [9]
that “X recurrent” implies “W (X) y X is extensive-amenable”.

Organization. The paper is organized as follows. In Section 2 we give some
relevant background on the random stirring process. In Section 3, we prove a
large deviation bound (estimate (1.5)) on its inverted orbits of sublinear size.
The main tool there will be a kind of FKG inequality due to Liggett. In Section
4, we add suitable cut-offs on Zd to the classical random stirring process in order
to obtain processes with i.i.d. increments in Wr (Zd ). We then axiomatize this
procedure for general bounded degree graphs X. Finally we end with a conjecture
and some open questions suggested by this work.

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

11

Acknowledgments:
I wish to warmly thank Mikael de la Salle for introducing me to this problem,
for numerous enlightening discussions around the concept of extensive-amenability
and also for his careful reading of the manuscript. I also thank Fabio Toninelli
and Guillaume Aubrun for useful discussions. This research is supported by the
ANR grant Liouville ANR-15-CE40-0013 and the ERC grant LiKo 676999.
2. The random stirring process and its inverted orbit
2.1. The random stirring process on Zd . We start by defining briefly this
process (see for example [12] for background on this process as well as its celebrated
companion, the symmetric exclusion process).
Let {p(x, y)}x,y be a symmetric transition kernel on Zd , i.e.
i) p(x, y) = p(y, x) for all x, y ∈ Zd ,
ii) p(x,
P y) ≥ 0,
iii) y p(x, y) = 1 for all x ∈ Zd .

Definition 2.1. Given a symmetric transition kernel p and a real number λ > 0,
the random stirring process on Zd with kernel λp(·, ·) is the Markov process
t 7→ τt with values in S(Zd ) which is defined informally as follows:

• τ0 := Id
• Independently for each pair {x, y}, one associates iid exponential clocks
of rate λp(x, y) (in other words, independently for each pair {x, y}, one
associates a Poisson Point Process of rate λp(x, y) on R+ ). At each
time t where an exponential clock rings for a given pair {x, y}, we define
τt := Txy ◦τt− where Txy denotes the transposition of {x, y} and τt− denotes
the left limit of the permutation at the time of the ring.
P
As for any y ∈ Zd , we have x∈Zd p(x, y) = 1 < ∞, it is a classical fact that one
can rigorously make sense of the above construction (see [12]).
This construction can be defined more generally for any conductance
profile
P
{c(x, y)}x,y∈Zd (recall Definition 1.7) satisfying supx c(x) = supx y c(x, y) < ∞
5
. See figure 1 for an illustration of the random stirring process on Z.
2.2. Inverted orbits.
Definition 2.2. Let {p(x, y)}x,y be a symmetric transition kernel on Zd and
λ > 0 be some fixed positive rate. Let (τt )t≥0 be the random stirring process
induced by λp(·, ·). For each t ≥ 0, the inverted orbit of the origin 0 is the
random subset Ōt ⊆ Zd defined as
[
Ōt = Ōtλ := {x ∈ Zd , ∃s ≤ t, τs (x) = 0} =
τs−1 ({0}) .
0≤s≤t

5We

distinguish the conductances c(·, ·) for the continuous time-Markov processes from
the conductances C(·, ·) in Definition 1.7 for discrete time random walks. The relationship
Lc
between the two reads
P as follows: C = e , where Lc is the symmetric operator defined by
Lc (x, y) := −c(x)(= y c(x, y)) if x = y and Lc (x, y) := c(x, y) otherwise.

12

CHRISTOPHE GARBAN

τt = . . . 2

τ0 = . . . 1

4

2

1

3

3

4

6

5

5

6

7

7

Z

Figure 1. (Nearest-neighbour) random stirring process on Z: as
time t increases, neighbouring sites are exchanged at rate λ (blue
arrows). This defines a càdlàg Markov process t 7→ τt ∈ S(Z).
We also define for any n ∈ N+ , the inverted orbit along integer times,
[
On = Onλ := {x ∈ Zd , ∃k ∈ {0, 1, . . . , n}, τk (x) = 0} =
τk−1 ({0}) .
0≤k≤n

These definitions readily extend to the more general case of a conductance profile
{c(x, y)}.
Remark 2.3. Clearly one always has On ⊆ Ōn . In particular it is easier for On to
be of small size than for Ōn .
The motion of one particle, say the origin, under the above random stirring
process is simple to describe: it is a continuous time random walk (X̄tλ )t≥0 on Zd
which jumps at rate λ according to the kernel p(·, ·). (N.B. in the general case
of a conductance profile {c(x, y)}, it jumps at rate c(x) according to the kernel
c(x,y)
). Let (Xnλ )n∈N be the trace of that continuous time RW discrete time on
c(x)
integer times. In other words, (Xnλ )n∈N is the discrete time random walk on Zd
with transition kernel
X λk
[eλ(p−Id) ](x, y) = e−λ
pk (x, y) .
k!
k≥0
L := p − Id is called the generator of this continuous-time random walk. Let us
assume that Xnλ starts at the origin and consider the stopping time T := inf{n ≥
1, Xnλ = 0} which
is the

 first return time to the origin. We shall use throughout the
0
quantity Pλp
T = ∞ , which is the probability that (Xnλ )n≥0 escapes to infinity
before returning to the origin.
 For a general conductance profile c(·, ·), we shall
0
use the notation Pc T = ∞ .
bn is the discrete time random walk on Zd induced by the
Remark 2.4. If X
bn = 0}, then it is easy to check
transition kernel p(·, ·), and if Tb := inf{n ≥ 1, X
that




1
0
Pλp
T = ∞ ≥ (1 − e−λ )P 0 Tb = ∞ = (1 − e−λ )
,
Ref f (Zd , p(·, ·))

where Ref f (Zd , p(·, ·)) is the effective resistance from 0 to infinity of the graph Zd
with conductances given by {p(x, y)}x,y . The above inequality follows from the
fact that the continuous-time random walk (Xnλ ) will jump during the first unit
interval [0, 1) with probability 1 − e−λ and will never get back to the origin with

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

13



probability P 0 Tb = ∞ . This lower bound is sub-optimal when λ is large:
 for
3
0
example in the case of the simple random walk on Z , one has Pλp T = ∞ → 1
as λ → ∞ while it is not the case of the R.H.S above.
2.3. Quantitative exponential decay.
Theorem 2.5. Let {p(x, y)}x,y be a symmetric transition kernel on Zd and λ > 0
be some fixed positive rate. Then for any n ≥ 0,
 


 1 |On | 
0 T =∞
− n+1
Pλp
2
E
≤e
.
(2.1)
2
More generally, for any p ∈ [0, 1] and any conductance profile {c(x, y)}x,y , we
have for all n ≥ 0,



|On | 
−p(n+1)Pc0 T =∞
E (1 − p)
≤e
.
(2.2)
Remark 2.6. As it was pointed out to us by M. de la Salle, this statement

 is
not very far
 from
 being optimal: indeed it is not hard to check that E|On | =
Pn
0
P
T
>
k
(see Lemma 4.3 in [9]), which readily implies that E |On | =
k=0
 λp

0
nPλp T = ∞ + o(n). By Jensen, this implies the following lower bound,
 


 1 |On | 
0 T =∞ +o(n)
−n log(2)Pλp
e
≤E
.
(2.3)
2
In terms of exponent, we are thus very close as log(2) ≈ 0.693 is not far from 1/2.
In fact it is not hard to check that our second estimate (2.2)is optimal as p → 1.

0
Finally, note that the above observation which relates E |On | with nPλp
T =∞
also shows that in the setting of Theorem 2.5, the orbits are exponentially unlikely
bn )n≥0 induced by
to be sublinear if and only if the symmetric random walk (X
p(·, ·) is transient.
The above Theorem has the following straightforward Corollaries.
Corollary 2.7. The following properties on the inverted orbits are satisfied:
(1) The continuous-time inverted orbit satisfies for any t > 0,
 


 1 |Ōt | 
dte 0
− 2 Pλp
T =∞
E
≤e
2


(2) ∃a ∈ (0, 1), P |On | < an ≤ e−an for all n ≥ 1.
Corollary 2.8. The inverted orbits are exponentially unlikely to be sublinear for
the following examples.
1
(1) If d ≥ 3 and p(x, y) := 2d
1x∼y on Zd , exponential decay holds for any
λ > 0.
1
(2) If d ∈ {1, 2} and p(x, y) ∝ kx−yk
d+α , then the exponential decay holds for
2

any λ > 0 if and only if α ∈ (0, d) . See for example Appendix B.1 in [2].

Remark 2.9. We highlighted in the above statements the particular case of
transition kernels p(·, ·) rather than the more general situation of conductance
profiles c(·, ·) to make these statements more readable for readers unused to
continuous-time Markov processes. Still, one may wonder why we added an

14

CHRISTOPHE GARBAN

additional parameter λ > 0. Indeed by construction, our continuous orbits satisfy
(law)

the obvious scaling identity |Ōtλ | = |Ōλt | which makes the parameter λ useless
from that point of view. There are two reasons.
(1) First, the question related to the IET-group is about discrete random
walks in W (Zd ) and in that setting, playing with both p(·, ·) and λ provides
a larger class of examples. (This is reminiscent of the fact that C ≡ λC for
discrete-time walks while c 6≡ λc for continuous-time RW as it corresponds
to a time-change).
(2) Second, even though it is in principle harder to obtain large deviation
bounds on On ⊆ Ōt=n , our proof in Section 3 will require to focus extensively on the discrete orbits.
3. Proof of the large deviation bound on the inverted orbits of
exclusion process
3.1. Liggett’s inequality in inhomogeneous time. The main tool in our
proof will be the following result due to Liggett which we state in a slightly
generalised form (i.e. in inhomogeneous-time).
Proposition 3.1 (Proposition 1.7, chapter VIII in [12]). Let L1 , L2 , . . . , Lk be
the generators (see [12]) of the random stirring processes on a graph G = (V, E)
with respective symmetric transition kernels pi : V × V → [0, 1]. Let λ1 , λ2 , . . . , λk
be positive rates and let t0 = 0 < t1 < . . . < tk = t. We consider the random
stirring process which evolves at rate λ1 according to L1 on the time interval [0, t1 )
and then at rate λ2 according to L2 on [t1 , t2 ) and so on. For any n ≥ 1, we
consider the following diffusion operator on functions f : V n → R,

Vn (t)f := et1 λ1 L1 e(t2 −t1 )λ2 L2 . . . e(t−tk−1 )λk Lk f .


I.e. Vn (t)f (x1 , . . . , xn ) := E ~x f (τt (x1 ), τt (x2 ), . . . , τt (xn )) , where (τt )t≥0 is the
(inhomogeneous in time) random stirring process on G = (V, E) induced by
λ1 L1 , . . . λk Lk and where
~x = (x1 , . . . , xn ) ∈ Tn := V n \ {~y , ∃i 6= j, yi = yj } .

Then, we have for any n ≥ 1 and any bounded positive-definite6 symmetric
function f : V n → R,
Vn (t)f (~x) ≤ Un (t)f (~x) for all ~x ∈ Tn ,

where Un (t) is the (inhomogeneous-time) heat semi-group on G = (V, E) induced
by independent random walks with same marginal law, i.e.
⊗n
Un (t)f = [ et1 λ1 (p1 −Id) e(t2 −t1 )λ2 (p2 −Id) . . . e(t−tk−1 )λk (pk −Id)
]f .
Proof. We refer to [12] for the proof in the time-homogeneous setting. We
just point out that in this time-homogeneous case, the hypothesis that the
transition kernel p is symmetric is fundamental in the proof. Note here that
the random walk corresponding to et1 λ1 (p1 −Id) e(t2 −t1 )λ2 (p2 −Id) . . . e(t−tk−1 )λk (pk −Id) is
no longer symmetric. As such this statement does extend Liggett’s result to a
6In

this paper, following [12], a symmetric function f : V n → R will be called positivedefinite if it is a positive definite function of each pair of variables.

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

15

considerably larger class of random processes on permutations. Yet, the proof
of this extension is immediate: let us argue in the case of two generators, L1 on
[0, t1 ) and L2 on [t1 , t2 ]. Then for any bounded positive definite f : V n → R, one
has Vn (t)f = Vn1 (Vn2 f ) ≤ Vn1 (Un2 f ) since Vn1 preserves the positivity as well as
Tn . Now (see [12]), it is easy to check that if f is positive definite, so is Un2 f . In
particular, by the homogeneous case, Vn1 (Un2 f ) ≤ Un1 (Un2 f ) = Un (t)f on Tn . 
This very useful inequality has been used extensively to study properties of
the symmetric exclusion process. See for example the use of this inequality in [1]
which shares similarities with our present proof (it already relies in fact on the
above inhomogeneous version). We will use this inequality as follows:
Q
Corollary 3.2. Let A ⊆ V and f (x1 , . . . , xn ) := ni=1 1xi ∈A . This function is
clearly positive-definite in each pair of variables. Applying the above Proposition
immediately leads to the following inequality: for all ~x = (x1 , . . . , xn ) ∈ V n \
{~y , ∃i 6= j, yi = yj },
n

 Y


P τt (xi ) ∈ A, for all 1 ≤ i ≤ n ≤
P Ztxi ∈ A ,
i=1

where {Ztzi } are independent time-inhomegenous walks starting from xi and driven
by the above transition kernels p1 , . . . , pk at rates λ1 , . . . , λk .
3.2. Bernoulli marking. The first idea here, which goes back to the proof
 |On | 
of (i) in Theorem 4.1 in [9] is to interpret E 12
as the probability that a
random subset An ⊆ τn (On ) is empty where each point in τn (On ) belongs to An
independently with probability 1/2 (indeed |τn (On )| = |On |). There is a very
convenient and dynamical way to sample the random subset An ⊆ τn (On ) which
goes as follows (once again suggested by [9]): let s1 , s2 , . . . , sn the permutations
on Zd induced by the (independent) random stirring processes along the intervals
(0, 1), (1, 2), . . . (n − 1, n), let also t0 , t1 , . . . , tn be (n + 1) independent standard
Bernoulli variables in {0, 1}.
(1) At time 0, let A0 = ∅ if t0 = 0 and A0 := {0} otherwise.
(2) At time 1, let A1 := s1 (A0 ) \ {0} if t1 = 0 and A1 := s1 (A0 ) ∪ {0}
otherwise.
(3) We keep going inductively for i ≥ 2, let Ai := si (Ai−1 ) \ {0} if ti = 0, and
Ai := s1 (Ai−1 ) ∪ {0} otherwise.

As such, clearly An is a uniform subset of τn (On ) and thus An = ∅ with probability
exactly (1/2)|On | .
3.3. Nearly Bernoulli marking via large N -reservoirs. We will not achieve
such a perfect Bernoulli marking, but we shall instead get as close as we want
by relying on the following approximation procedure (see Figure 2). The very
important feature of our approximation will be that not only it will serve as a nearly
perfect Bernoulli(1/2)-marking but it will also evolve as a time-inhomogeneous
exclusion process on a larger graph than Zd , where one connects a large “reservoir”,
namely a complete graph KN with N  1, to the origin 0 ∈ Zd . See Figure
2. This second property will allow us to reduce the analysis to independent

16

CHRISTOPHE GARBAN

N
2

− 1 initial particles at
time 0 inside KN

KN

Zd

0

rate N on
[k(1 + N1 ), k(1 + N1 ) + N1 )
Figure 2.

time-inhomogeneous random walks running on Zd ∪ KN thanks to Proposition
3.1.
We will work for each even N ∈ 2N+ on the graph GN with vertex set Zd ∪ KN
(where KN is the complete graph on N vertices) and where we connect Zd with
KN by adding one edge between each N vertex of KN and the origin 0 of the
lattice Zd . Let us now set up the inhomogeneous rates we shall use on this lattice:
• For each k ≥ 1, let Ik be the unit interval [k − 1 + Nk , k + Nk ). On
each such interval Ik , the random stirring process is driven by λp(·, ·)
where p is our initial symmetric kernel on Zd . In other words, each edge
e = (x, y), x, y ∈ Zd switch at rate λp(x, y) on Ik . Furthermore, the rates
inducing the switches between KN and {0} are frozen, i.e. equal to 0, on
these intervals.
• For each k ≥ 0, let Jk be the interval [k + Nk , k + k+1
). On each such
N
interval Jk , assume each edge from KN to {0} switch at rate N , while the
rest of the process (on Zd ) is frozen on these intervals.
• By symmetry, there is no need to describe the rates between vertices in
KN , we may assume these rates to be zero if we wish to.
This construction induces as in Definition 2.1 two natural processes:
(N )

a) First a Markov process t 7→ τt on the permutations of Zd ∪ KN which
only permutes sites in Zd on intervals Ik , k ≥ 1 while it only permutes
sites between KN and the origin 0 on intervals Jk , k ≥ 0.
b) It also induces a random walk on the permutations of Zd which has exactly
the law of the original random stirring process. For each k ≥ 1, let sk be
the permutation of Zd induced by the stirring process restricted to the
interval Ik . As such {sk }k≥1 are i.i.d and τn := sn ◦ . . . ◦ s1 has the same
law as in Theorem 2.5.
(N )

We will use the first process t 7→ τt
to induce a nearly Bernoulli-marking:
N
initialise the system with 2 − 1 particles in KN , say at sites {x1 , . . . , x N −1 } (and
2

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

17

no particles elsewhere). Now for each t ≥ 0, let
N
(N )
(N )
− 1} ∩ Zd
At := {τt (xi ), 1 ≤ i ≤
2
d
This set is a random subset of Z evolving in time. For each n ∈ N, let n
b :=
(N )
1
1
n(1 + N ) + N . Our approximation has been constructed so that Anb is very
close to the exact Benoulli-marked random set An ⊆ τn (On ) we considered
above. The slight technical difficulty here is that given the set τn (On ), the
(N )
(N )
events {x ∈ Anb }, x ∈ τn (On ) are no longer independent (in other words Anb
is not quite a uniform random subset of τn (On )). Yet, to overcome this lack of
independence, the following stochastic domination type of argument allows us to
conclude.
3.4. Stochastic domination. We will show the following lower bound.
Lemma 3.3. If N is large enough,
 (N )



P Anb = ∅ ≥ E (1/2)|On |

(N )

Proof. The randomness used to sample the random set Anb can be naturally
decomposed into two sources of randomness. First, recall s1 , . . . , sn are the
permutations of Zd induced by the stirring processes on each of the intervals
(Ii )1≤i≤n . Let us call F the filtration generated by these permutations. The other
(N )
source of randomness needed to run Anb is the shuffling within KN ∪ {0} which
arises on each intervals Jk , k ≥ 0. For each k ≥ 0, call Gk the filtration generated
by that shuffling on Jk (i.e. by the stirring process in KN ∪ {0} restricted to Jk ).
(N )
With these definitions, the permutation τnb of Zd ∪ KN is measurable w.r.t to
σ(F , (Gk )0≤k≤n ) while the permutation τn of Zd is measurable w.r.t F only. In
particular the sets On and τn (On ) are also measurable w.r.t F . We may thus
write,
 (N )

  (N )

P Anb = ∅ = E P Anb = ∅ F
  Y

=E E
1x∈A
F
(N )
/
n
b

x∈τn (On )

Now, let us use any prescribed ordering of the set τn (On ) so that may write
τ (On ) = {z1 , . . . , zm }, where m = |On |. For each 1 ≤ i ≤ m, let us define
ki := sup{j ≤ n, τj (zi ) = 0}, i.e the last passage in 0 of the orbit of zi before time
n. This random time ki ∈ {0, . . . , n} is also measurable w.r.t F which allows us
to go one step further:
m=|O |
 (N )

  Yn

P Anb = ∅ = E E
1zi ∈A
F
(N )
/
i=1
m
Y

  
=E E E

n
b

1zi ∈A
F , (Gk )k6=k1
(N )
/
n
b

i=1



F



m

 Y


=E E
1zi ∈A
F
,
(G
)
F
,
(N ) E 1
(N )
k
k6
=
k
1
z1 ∈A
/
/
i=2

n
b

n
b

18

CHRISTOPHE GARBAN
(N )

since it can be easily checked that the events {zi ∈
/ Anb }2≤i≤m are measurable
w.r.t σ(F , (Gk )k6=k1 ). We will prove below that

 1
E 1z1 ∈A
F
,
(G
)
≥
(N )
k
k6
=
k
1
/ n
b
2

(3.1)

which will imply
m
 (N )

 1 Y

P Anb = ∅ ≥ E E
1zi ∈A
F
,
(N )
2 i=2 / nb

and by repeating inductively the same argument from i = 2 to i = m, this gives
us the desired result, i.e.
 (N )

  1

 1

P Anb = ∅ ≥ E E ( )m F = E ( )|On | .
2
2
Let us then show the estimate (3.1). Given F , (Gk )k6=k1 , z1 will not belong to
(N )
Anb if and only if the shuffling inside Kn ∪ {0} on the interval Jk1 will not end
up with a particle at the origin. The probability that there is no particle is larger
than the probability pupdate that there is at least one update of the origin on Jk ,
times the probability p0 that the last transposition did not place a particle at {0}.
From the construction of our process, pupdate = 1 − e−N ×N/N = 1 − e−N . For the
estimate of p0 , note that at the time of the last switch, there are at most N2 − 1
particles in KN , hence p0 ≥ ( N2 + 1)/N = 12 + 1/N . All together this gives us a
lower bound of (1 − e−N )( 12 + 1/N ) which is higher than 1/2 for N large enough.
This ends our proof.

3.5. Upper bound via independent random walks. We shall now rely on
Corollary 3.2 to show the following domination.
Lemma 3.4.


 (N )

0 T =∞
− n+1
P
lim sup P Anb = ∅ ≤ e 2 λp
.
N →∞

Clearly this Lemma together with Lemma 3.3 concludes the proof of Theorem
2.5.
Proof. Let ~x := (x1 , . . . , x N −1 ) be our initial set of particles in KN (see Figure 2).
2
Corollary 3.2 implies that
 (N ) 


N
P Anb
= P τnb (x1 ) ∈ KN , for all 1 ≤ i ≤
−1
2
N
2

≤

−1
Y
i=1



P xi Zt=bn ∈ KN



N
− 1) log P x1 Zt=bn ∈ KN by symmetry
(3.2)
2


We thus need an upper bound on P x1 Zt=bn ∈ KN , i.e. a lower bound on the
probability pescape that the particle initially at x1 escapes from KN at time t = n
b.
One possible way of escaping is as follows:
= exp (

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

19

(1) First, Ztx1 needs to be placed in {0} at the end of one of the shuffling on
intervals Jk . At the beginning of each of these Jk , all the N sites of KN
have the same probability pmarked to be placed at {0} at the end of Jk
(note that pmarked does not depend on what happened before as it also
takes into account the event that a site in KN without a particle is sent to
{0}). We use below the fact that the motion of one i.i.d particle t 7→ Ztx1
has the same law as t 7→ τt (x1 ). In particular, we see that N pmarked is
exactly the probability that one of the sites initially in KN is placed at
{0} at the end of Jk under the exclusion dynamics on Jk . Now it is easy
to see that this latter probability is greater than the probability that there
is at least one update along Jk (i.e. = 1 − e−N ) times the probability that
the site initially at {0} (at the beginning of Jk ) is not sent back to {0}
at the end of Jk . By looking at what happens at the last update, this is
greater than 1 − N1 . This gives us pmarked ≥ N1 (1 − e−N )(1 − N1 ) ≥ N1 − N22
for N large enough. Now, the probability that Ztx1 gets placed in {0} at
the end of one of the intervals (Jk )0≤k≤n is exactly
1
2
n+1
1 − (1 − pmarked )n+1 ≥ 1 − (1 −
+ 2 )n+1 =
+ O(N −2 )
N
N
N
(2) Now, if the particle initially at x1 is placed in {0} at the end of a Jk , one
way to get a lower bound is to ask this particle to never get back to the
origin. This probability

depends on what is 0 ≤ k ≤ n but in any case is
0
larger than Pλp
T =∞
All together, we find that

n+1 0 
Pλp T = ∞ + O(N −2 )
pescape ≥
N
Getting back to (3.2), this gives us
 (N ) 


N
n+1 0 
P Anb
≤ exp ( − 1) log(1 −
Pλp T = ∞ + O(N −2 ))
2
N


N
n+1 0 
= exp −( − 1)
Pλp T = ∞ + O(N −1 )) .
2
N
Now, sending N → ∞ concludes our proof.

Note that the exact same proof leads to the more general estimate (2.2) in
our main Theorem 2.5. Indeed, the only change is to consider bpN c − 1 initial
particles in the “reservoir” KN instead of N2 − 1. Similarly the same proof applies
if one replaces λp(·, ·) by any general conductance profile c(·, ·).
4. spatial cut-off and a characterization of
diffuse-extensive-amenability
4.1. The case of Zd . We start by explaining how one can obtain bounded range
increments on Zd (which will prove Theorem 1.13). Clearly, the classical random
1
stirring process t 7→ τt (i.e. with transition kernel p(x, y) := 2d
1x∼y ) is not of
d
finite range. In other words, for any t > 0, τt ∈
/ W (Z ) a.s. (the process t 7→ τt
1
belongs to the class (A) of L -diffusions from Definition 1.11 but not to the
class (B)). To keep the technology used in Section 3 valid (namely, Liggett’s
inequality), we will still rely on some underlying Exclusion process, but to make

20

CHRISTOPHE GARBAN

increments of bounded range, we will remove some edges in order to confine the
dynamics. On the other hand, if we confine things too much then the process
will stay in some Wr0 (Zd ) for ever and the inverted orbits will remain very small
(|On | ≤ C r0d , ∀n ≥ 1).

E2
E1
Figure 3. Spatial cut-off used on Z2 , i.e. E2 = E1 ∪ E2
We will proceed as follows. First we shall divide the (nearest-neighbour) edges
of Zd (denoted by Ed ) into two sets E1 ∪ E2 . Consider for this all the unit
cubes [0, 1]2 translated by (2Z)d , i.e. all cubes of the form (2n1 , . . . , 2nd ) + [0, 1]d .
Let E1 be the set of all edges belonging to one of these cubes. See Figure
3. And Let E2 := Ed \ E1 . (i.e. E2 is the set of edges adjacent to all (2Z)d translates of the cube [1, 2]d ). Now we set up the following transition kernels: let
p1 (x, y) := d1 1x∼E1 y and p2 (x, y) := d1 1x∼E2 y .
We introduce the following inhomogeneous-time random stirring process t ≥
0 7→ τt ∈ W (Zd ) : for any k ∈ N, on the time-interval [k, k + 1/3), we let the
process evolve according to a time-homogeneous random stirring process with
transition kernel p1 (·, ·). Then, on [k + 1/3, k + 2/3), we let the process evolve
according to a time-homogeneous stirring process with kernel p2 and finally on
[k + 2/3, k + 1), we let things evolve again according to the kernel p1 . One may
write this in terms of operators as follows: if L1 , L2 are the generators of the
random stirring processes induced by p1 , p2 , then the Markov operator describing
the law of τt=1 is
K = e1/3L1 e1/3L2 e1/3L1 .
The reason why we split each unit interval [k, k + 1) into three intervals instead
of p1 on [k, k + 1/2) and p2 on [k + 1/2, k + 1) is for the following reason: for any
x ∈ Zd , the discrete-time process
n ∈ N 7→ τn ({x}) ,
is a RW with transition kernel given by
1

1

1

P = e 3 (p1 −Id) e 3 (p2 −Id) e 3 (p1 −Id) .
In particular, with our choice of splitting, P is symmetric (P = P T ) and n 7→
τn ({x}) is thus a RW in conductances C(x, y) := P (x, y) (see Definition 1.7). It
is straighforward to check from our construction that these conductances

 satisfy
item e) from Proposition 1.8. This shows that if d ≥ 3, PP0 T = ∞ > 0 and
the exact same proof as in Section 3 implies that the inverted orbits of the

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

21

(time-inhomogeneous) dynamics t 7→ τt satisfy at any integer times n ≥ 0,
 


 1 |On | 
0 T =∞
− n+1
P
P
E
≤e 2
.
2
(In the present case the above symmetrisation step is not fully necessary but it will
be in the more general case below). Finally, it is immediate from our construction
that τn = sn ◦ . . . s1 where the random permutations
are i.i.d (sampled according
√
d
to τt=1 ) and belong to Wr (Z ) with r = d3 de. This ends our proof. (N.B. the
probability measure µ on Wr (Zd ) which induces this process can be described
using the above Markov operator K by µ(A) := δId K 1A ).
4.2. The general case of connected-bounded-degree graphs. In this Section, we will prove Theorem 1.16 which provides a characterisation of our notion
of diffuse-extensive-amenability from Definition 1.14.
Proof of Theorem 1.16.
Let G = (X, E) be a connected bounded degree graph. Let h ∈ N+ be such that
deg(x) ≤ h , ∀x ∈ X. Let E := {e1 , e2 , . . . , en , . . .} by any ordering of the set of
edges. We define recursively the following subsets of E:
(1) First we defined E1 ⊆ E as follows. Let E1,0 := ∅. For any n ≥ 0, let
E1,n+1 be E1,n ∪ {en+1 } iff the edge en+1 does not share any common
vertex with the edges already in E1,n . Otherwise let E1,n+1 = E1,n . Define
E1 := lim E1,n .
(2) Assume E1 , . . . , Ek ⊆ E have been defined. Construct Ek+1 recursively as
follows. Let Ek+1,0 := ∅. For any n ≥ 0, let E1,n+1 be E1,n ∪ {en+1 } iff the
S
edge en+1 does not belong to km=1 Em and does not share any common
vertex with the edges already in Ek+1,n . Otherwise let Ek+1,n+1 = Ek+1,n .
Define Ek+1 := lim Ek+1,n .
S
(3) Iterate until one has km=1 Em = E.
Let us argue that this procedure ends in finite time (i.e. that there is k ≥ 1, such
S
that km=1 Em = E). For any j ≥ 1, let us see what happens for the j-th edge
ej ∈ E. Consider the finite set F = Fj ⊆ E of all edges which share a common
vertex with ej and whose labels are < j. In particular, we have |F | ≤ 2(h − 1).
Along the process of defining the set E1 , if F ∩ E1,j−1 = ∅, then by construction
ej will belong to E1 . Otherwise, this means at least one egde in F will belong to
E1 . If we are in the second case, we proceed to the construction of E2 . Along
that construction, either we add ej to E2 or this means at least one new edge
in F (which did not appear in E1 ) has been added in E2 . As F is finite, this
readily implies that the edge ej needs to be added to Ek at the latest when
k = 2(h − 1) + 1. (I.e. E = E1 ∪ . . . E2h−1 ).
Now, for any i ∈ {1, . . . , 2h − 1}, define the conductance profile ci on G =
(X, E) as follows: for any x, y ∈ E, if the edge e = {x, y} ∈ Ei then define
ci (x, y) := 1 and otherwise let ciP
(x, y) := 0. (With this definition, there may be
some sites x here where ci (x) = y ci (x, y) = 0 but it is harmless for continuoustime dynamics). Similarly as in the above Section, if L1 , . . . , L2h−1 denote the
generators of the random stirring processes associated to these conductance
profiles, we shall consider the inhomogeneous-time random stirring process which

22

CHRISTOPHE GARBAN

evolves on each unit time interval as follows. Let N := 2h − 1. For any k ≥ 0
i
and any 1 ≤ i ≤ N , let the process t 7→ τt evolve on [k + i−1
) according
, k + 2N
2N
to the random stirring process induced by Li . This defines our stochastic process
on all intervals of the form [k, k + 1/2). On the remaining intervals, symmetrise
exactly as in the above argument in order to induce symmetric random walks
n 7→ τn (x), ∀x ∈ X. I.e. the Markov operator describing the law of τt=1 is
1

1

1

1

K := e 2N L1 . . . e 2N LN e 2N LN . . . e 2N L1 .

It is straightforward to check that
• τt=1 ∈ W4h−2 (X)
• The conductance profile C associated to K satisfies C(x, y) ≥ δ1x∼G y for
some δ = δ(h) > 0.
As item e) from Proposition 1.8 is also valid for transient bounded-degree graphs,
this concludes our proof.

5. Conclusion and some open questions
We have shown that for rather generic examples of diffusions on W (Zd ), d ≥ 3,
inverted orbits {On }n≥0 are exponentially unlikely to be sublinear. Based on
this, it would sound very counter-intuitive (and very remarquable!) to us if
for ANY symmetric and finitely supported probability measure µ on W (Zd ),
their corresponding inverted orbits had better-than-exponential probability to be
sublinear. We do not believe this can hold and state the following conjecture.
Conjecture 5.1. When d ≥ 3, the action W (Zd ) y Zd is not extensiveamenable.
More generally, one may ask the following question.
Question 5.2. Is it the case that for any bounded-degree connected graph G =
(X, E), the action W (X) y X is extensive-amenable if and only if it is diffuseextensive-amenable ? (If so, by Theorem 1.16, W (X) y X would be extensiveamenable only when X is recurrent).
Finally, on the Euclidean lattice Zd , some explicit and simple examples of RWs
on W (Zd ) such as the one below may be worth analyzing:
Question 5.3. Consider the following permutations of W (Zd ). First, let G be the
set of all d2d−1 edges of the unit cube [0, 1]d . For each e ∈ G, let Fe be the set of all
edges of ZSd obtained by translating both e and e + (1, 1, . . . , 1) by the lattice 2 · Zd .
(As such e∈G Fe = Ed ). For any e ∈ G, let σ
be be the permutation which permutes
d−1
all edges in the set Fe . This gives us d2
explicit permutations of Zd which
−1
satisfy σ
be = σ
be . When d ≥ 3, analyse what is the probability that the inverted
orbit of the RW (τn )n≥0 on W (Zd ) generated by S := hb
σe ie∈G is sublinear? Note
that S is symmetric and that for each x ∈ Zd , n 7→ τn ({x}) is just a simple RW
in Zd starting at x. (Our guess is that it is exponentially unlikely when d ≥ 3).
References
[1] Arratia, R., Symmetric exclusion processes: a comparison inequality and a large deviation
result. The Annals of Probability, pp.53–61. 1985.

DIFFUSE-EXTENSIVE-AMENABILITY AND THE IET GROUP

23

[2] Caputo, P., Faggionato, A. and Gaudillière, A., Recurrence and transience for long-range
reversible random walks on a random point process. Electronic Journal of Probability, 14,
pp. 2580–2616. 2009.
[3] de Cornulier, Y., Groupes pleins-topologiques, d?aprs Matui, Juschenko,
Monod,...,(written exposition of the Bourbaki Seminar of January 19th, 2013,
available at http://www. normalesup. org/ cornulier/plein. pdf). 2013.
[4] Dahmani, F., Fujiwara, K. and Guirardel, V., Free groups of interval exchange transformations are rare. Groups, Geometry, and Dynamics, 7(4), pp.883–911. 2013.
[5] Van Douwen, E.K. Measures invariant under actions of F2. Topology and its Applications,
34(1), pp.53–68. 1990
[6] Juschenko, K. and Monod, N. Cantor systems, piecewise translations and simple amenable
groups. Annals of mathematics, 178(2), pp.775–787, 2013.
[7] Juschenko, K. and de la Salle, M., Invariant means for the wobbling group. Bulletin of
the Belgian Mathematical Society-Simon Stevin, 22(2), pp.281–290. 2015.
[8] Juschenko, K., Nekrashevych, V. and de la Salle, M. Extensions of amenable groups by
recurrent groupoids. Inventiones mathematicae, 206(3), pp. 837–867. 2016.
[9] Juschenko, K., Matte Bon, N., Monod, N. and de la Salle, M. Extensive amenability and
an application to interval exchanges. Ergodic Theory and Dynamical Systems, pp.1–25,
2016.
[10] Kotowski, M. and Virág, B., Non-Liouville groups with return probability exponent at
most 1/2. Electronic Communications in Probability, 20. 2015.
[11] Kumagai, T. Random walks on disordered media and their scaling limits. St-Flour lecture
notes. Springer. 2014.
[12] Liggett, T.M. Interacting particle systems (Vol. 276). Springer. 2012.
[13] Lyons, R. and Peres, Y., Probability on trees and networks (Vol. 42). Cambridge University
Press. 2016.
[14] Paterson, A.L. Amenability. American Mathematical Soc. (No. 29). 2000.
[15] Saloff-Coste, L. and Zheng, T., Isoperimetric profiles and random walks on some permutation wreath products. preprint. arXiv:1510.08830. 2015.
[16] Viana, M., Ergodic theory of interval exchange maps. Revista Matemática Complutense,
19(1), pp.7–100. 2006.
(Christophe Garban) Univ Lyon, Université Claude Bernard Lyon 1, CNRS UMR
5208, Institut Camille Jordan, 69622 Villeurbanne, France
E-mail address: garban@math.univ-lyon1.fr

