# The Poisson boundary of lampshuffler groups

Eduardo Silva

###### Abstract.

We study random walks on the lampshuffler group $\mathrm{FSym}(H)\rtimes H$,
where $H$ is a finitely generated group and $\mathrm{FSym}(H)$ is the group of
finitary permutations of $H$. We show that for any step distribution $\mu$
with a finite first moment that induces a transient random walk on $H$, the
permutation coordinate of the random walk almost surely stabilizes pointwise.
Our main result states that for $H=\mathbb{Z}$, the above convergence
completely describes the Poisson boundary of the random walk
$(\mathrm{FSym}(\mathbb{Z})\rtimes\mathbb{Z},\mu)$.

###### Key words and phrases:

Random walks, Poisson boundary, finitary symmetric groups, locally finite
groups

##  1\. Introduction

We study random walks on the semi-direct product
${\mathsf{Shuffler}}(H)\coloneqq\mathrm{FSym}(H)\rtimes H$, where $H$ is an
infinite countable group and $\mathrm{FSym}(H)$ denotes the group of
bijections from $H$ to $H$ that coincide with the identity map outside of a
finite set. Here, the action of an element $h\in H$ on a permutation
$f\in\mathrm{FSym}(H)$ is defined as $(h\cdot f)(x)=hf(h^{-1}x)$, for $x\in
H$. These groups are referred to as _lampshuffler groups_ 111The name
“lampshuffler” seems to have first appeared in [GM22], and it is used there to
refer to the group $\mathrm{FAlt}(H)\rtimes H$, where $\mathrm{FAlt}(H)$ is
the group of finitary even permutations of $H$. In this paper we use the name
lampshuffler for the group $\mathrm{FSym}(H)\rtimes H$, following [BGTT22,
GT24]. in [GM22, BGTT22, GT24] due to their resemblance to lamplighter groups,
and random walks on them are called mixer chains in [Yad09]. In Section 2 we
describe the basic geometric and algebraic structure of the group
${\mathsf{Shuffler}}(H)$, and explain that it inherits the properties of $H$
being finitely generated, amenable, or elementary amenable (Lemma 2.1).

Let $G$ be a countable group and let $\mu$ be a probability measure on $G$.
The _(right) random walk_ $(G,\mu)$ is the Markov chain with state space $G$
and with transition probabilities $p(g,h)=\mu(g^{-1}h)$, for $g,h\in G$. We
assume that the random walk starts at the identity element $e_{G}\in G$.
Random walks on lampshuffler groups have been studied in the literature. It is
shown in [Yad09] that the drift function of the simple random walk for the
standard generating set on ${\mathsf{Shuffler}}(\mathbb{Z})$ is asymptotically
equivalent to $n^{3/4}$. In [EZ20, Corollary 1.4] it is proved that the Følner
function of ${\mathsf{Shuffler}}(\mathbb{Z}^{d})$, $d\geq 1$, is
asymptotically equivalent to $n^{n^{d}}$, and the return probability
$\mu^{2n}(e)$ of the simple random walk is shown to be asymptotically
$\mathrm{exp}\left(-n^{\frac{d}{d+2}}\log^{\frac{2}{d+2}}n\right)$. Given a
random walk $(G,\mu)$ and denoting by $h(\mu)$ its Avez asymptotic entropy
(see Subsection 3.4 for the definition), the problem of “full realization”
consists on realizing each number in the interval $[0,h(\mu)]$ as the
Furstenberg entropy of some ergodic $(G,\mu)$-space. In [HY18, Theorem 1.4] it
is proved that if $H$ is a finitely generated nilpotent group, then the
lampshuffler group ${\mathsf{Shuffler}}(H)$ has full realization. Lampshuffler
groups also appear in [FS20], where the “umpteen operator” is introduced as a
representation-theoretic analog of a random Schrödinger operator, and the
property of having Lifshitz tails is linked to the decay of the return
probability of the simple random walk on
${\mathsf{Shuffler}}(\mathbb{Z}^{d})$.

The _Poisson boundary_ of a random walk $(G,\mu)$ is a measure space that
encodes the asymptotic behavior of the process. It can be defined as the space
of ergodic components of the shift map in the space of infinite trajectories.
There are several other equivalent definitions of the Poisson boundary of a
random walk, and we recall some of them in Section 3. In the last decades,
there has been extensive research focused on the identification of Poisson
boundaries, i.e., the problem of exhibiting an explicit measure space that
coincides with the Poisson boundary up to a $G$-equivariant measurable
isomorphism. The main result of the current paper is a complete description of
the Poisson boundary of ${\mathsf{Shuffler}}(\mathbb{Z})$, for measures $\mu$
with a finite first moment that induce a transient random walk on
$\mathbb{Z}$.

Let $\mu$ be a probability measure on ${\mathsf{Shuffler}}(H)$ and consider
the trajectory of the $\mu$-random walk
$(F_{n},S_{n})\in{\mathsf{Shuffler}}(H)$, $n\geq 0$, where
$F_{n}\in\mathrm{FSym}(H)$ is a finitely supported permutation of $H$ and
$S_{n}\in H$. We refer to $\\{F_{n}\\}_{n\geq 1}$ as the _permutation
coordinate_ of the $\mu$-random walk.

Our first result is the following _stabilization lemma_.

######  Lemma 1.1.

Let $H$ be a finitely generated group, and consider a probability measure
$\mu$ on ${\mathsf{Shuffler}}(H)$. Suppose that $\mu$ has a finite first
moment and that it induces a transient random walk on $H$. Then for any $h\in
H$, the values $F_{n}(h)$, $n\geq 0$, of the permutation coordinate of the
random walk almost surely stabilize to a limit value $F_{\infty}(h)$.

We prove this result in Section 4 in a more general form, where $H$ is not
assumed to be finitely generated (Lemma 4.5). If we furthermore suppose that
$\mu$ is non-degenerate (i.e., that $\mathrm{supp}(\mu)$ generates
${\mathsf{Shuffler}}(H)$ as a semigroup), then the stabilization lemma shows
that the Poisson boundary of $({\mathsf{Shuffler}}(H),\mu)$ is non-trivial
(Corollary 4.6). In particular, the Poisson boundary of any simple random walk
on ${\mathsf{Shuffler}}(H)$, for $H$ infinite and not virtually $\mathbb{Z}$
nor virtually $\mathbb{Z}^{2}$, is non-trivial. In contrast, simple random
walks on ${\mathsf{Shuffler}}(\mathbb{Z}^{d})$ for $d=1,2$ have a trivial
Poisson boundary (see Section 6). The well-known open “stability problem” asks
whether the non-triviality of the Poisson boundary for a simple random walk on
a finitely generated group depends on the choice of generating set. Corollary
4.6 together with Propositions 6.1 and 6.2 imply that for the family of groups
${\mathsf{Shuffler}}(\mathbb{Z}^{d})$, $d\geq 1$, there is no such dependence.

It is a result of Rosenblatt [Ros81, Theorem 1.10] and Kaimanovich and Vershik
[KV83, Theorem 4.4] that every amenable group admits a probability measure
with a trivial Poisson boundary. Hence, if $H$ is infinite, amenable, and is
not virtually $\mathbb{Z}$ nor virtually $\mathbb{Z}^{2}$, the group
${\mathsf{Shuffler}}(H)$ admits symmetric non-degenerate random walks with a
transient projection to $H$, for which the permutation coordinate does not
stabilize (Remark 4.7). In Proposition 4.8, we prove that
${\mathsf{Shuffler}}(\mathbb{Z})$ also admits random walks with this property.
The stabilization lemma excludes measures where the permutation coordinate
does not stabilize via the assumption of a finite first moment. In Proposition
4.9 we show that this condition cannot be weakened to the finiteness of a
smaller moment: we construct a probability measure on
${\mathsf{Shuffler}}(\mathbb{Z})$ that induces a transient random walk on
$\mathbb{Z}$ and that has a finite $(1-\varepsilon)$-moment, for every
$0<\varepsilon<1$, for which the permutation coordinate does not stabilize.

We now state our main theorem.

######  Theorem 1.2.

Let $\mu$ be a probability measure on ${\mathsf{Shuffler}}(\mathbb{Z})$ with a
finite first moment that induces a transient random walk on $\mathbb{Z}$. Then
the Poisson boundary of $({\mathsf{Shuffler}}(\mathbb{Z}),\mu)$ coincides with
the space of limit functions $F_{\infty}:\mathbb{Z}\to\mathbb{Z}$, endowed
with the corresponding hitting measure.

We prove this result by using Kaimanovich’s Conditional Entropy Criterion
[Kai00, Theorem 4.6]. Another component of our proof is the _displacement_
associated with a permutation (Definition 2.2). We explain the idea of the
proof of Theorem 1.2 at the beginning of Section 5, and present the proof in
Subsection 5.1. We mention that the conditional entropy criterion, together
with the Ray criterion and Strip criterion that follow from it [Kai00], has
played a role in the identification of the Poisson boundary for many classes
of groups, some of which we mention below.

The Poisson boundary has been described for several families of countable
groups, many of which possess hyperbolic-like properties. One such family is
that of non-abelian free groups, whose Poisson boundary was described in
[DM61] for measures supported on a free generating set and in [Der75] for
finitary measures. More generally, the Poisson boundary of a (non-elementary)
hyperbolic group was shown to coincide with its Gromov boundary in [Anc87] for
finitary measures and in [Kai00, Theorems 7.4 and 7.7] for more general $\mu$.
Furthermore, [CFFT22] established that this description of the Poisson
boundary holds for any measure of finite entropy on a hyperbolic group, and
described the boundary for acylindrically hyperbolic groups, extending [MT21,
Theorem 1.5]. These papers cover the description of the Poisson boundary for
various classes of groups that had already been studied, with extra conditions
on the measure, such as groups with infinitely many ends [Woe89], [Kai00,
Theorem 8.4], mapping class groups [KM96], braid groups [FM98], groups acting
on $\mathbb{R}$-trees [GM12] and $\mathrm{Out}(F_{n})$ [Hor16]. Another family
of groups we mention is that of discrete subgroups of semi-simple Lie groups,
studied in [Fur71, Led85] and [Kai00, Theorems 10.3 and 10.7].

The Poisson boundary has also been described for classes of groups that do not
exhibit a hyperbolic nature. A notable family is that of amenable groups,
which always admit a non-degenerate measure with a trivial Poisson boundary
[Ros81, KV83]. A natural question is whether _every_ non-degenerate measure on
a given amenable group $G$ has a trivial Poisson boundary. In such a case, $G$
is called a _Choquet-Deny group_ and this family of groups includes abelian
groups [Bla55, CD60, DSW60], nilpotent groups [DM61, Mar66], and groups that
have no ICC 222A countable group is said to be _ICC_ if it is non-trivial and
every non-trivial element has an infinite conjugacy class. quotient [Jaw04,
LZ98]. It is proven in [FHTVF19] that the latter property is also necessary
and thus provides an algebraic characterization of countable Choquet-Deny
groups. This result is further developed in [EK23], where the authors prove
the following: any countable group $G$ with an ICC quotient admits a non-
degenerate symmetric measure of finite entropy, for which the Poisson boundary
can be completely described in terms of the convergence of sample paths to the
boundary of a locally finite forest, whose vertex set is $G$.

Kaimanovich and Vershik [KV83, Proposition 6.4] provided the first examples of
amenable groups that admit measures with a non-trivial Poisson boundary.
Namely, they proved that for the wreath product
$\mathbb{Z}/2\mathbb{Z}\wr\mathbb{Z}^{d}$, $d\geq 1$, and for any non-
degenerate finitely supported measure $\mu$ whose projection to
$\mathbb{Z}^{d}$ induces a transient random walk, the lamp configurations
stabilize almost surely. This implies the non-triviality of the associated
Poisson boundary, and it was conjectured that this space is completely
described by the space of limit configurations. This was initially proven for
measures with a projection to $\mathbb{Z}^{d}$ with non-zero drift [Kai01,
Theorem 3.6.6], whereas the case of zero drift was proved first for $d\geq 5$
[Ers11], and later for $d\geq 3$ by Lyons and Peres [LP21]. Their proofs can
be adapted to provide an analogous description of the Poisson boundary of
random walks on free metabelian groups [Ers11, LP21] and, in both cases,
generalize to infinitely supported measures with appropriate moment
conditions. Additional results about the description of the Poisson boundary
on wreath products have been obtained in [KW07, Sav10] and we recall them in
Subsection 3.3. Another class of amenable groups for which the Poisson
boundary has been completely described (for finitely supported measures) is
the family of discrete affine groups of a regular tree, studied in [BTZ21].

Theorem 1.2 provides a new class of groups for which we have a complete
description of the Poisson boundary. Since our result does not ask for non-
degeneracy of $\mu$, and the group ${\mathsf{Shuffler}}(\mathbb{Z})$ contains
subgroups isomorphic to $F\wr\mathbb{Z}$ for every finite group $F$
(Proposition 2.4), Theorem 1.2 includes the description of the Poisson
boundary for the wreath product of a finite group with an infinite cyclic base
group.

In Subsection 2.3 we comment on the similarities and differences between the
group ${\mathsf{Shuffler}}(\mathbb{Z})$ and wreath products of the form
$F\wr\mathbb{Z}$, where $F$ is finite or $F=\mathbb{Z}$. One distinction we
remark is that ${\mathsf{Shuffler}}(\mathbb{Z})$ admits (degenerate) measures
with non-trivial Poisson boundary that induce a recurrent random walk on
$\mathbb{Z}$, whereas this is not possible for wreath products
$F\wr\mathbb{Z}$ as above. Nonetheless, in Section 6 we show that such
examples cannot be found among finitely supported measures: we prove that any
finitary measure on ${\mathsf{Shuffler}}(\mathbb{Z})$ or on
${\mathsf{Shuffler}}(\mathbb{Z}^{2})$ which induces a recurrent random walk on
the base group has a trivial Poisson boundary (Propositions 6.1 and 6.2).

There is also a difference between ${\mathsf{Shuffler}}(\mathbb{Z})$ and
wreath products in terms of the relation between the stabilization of
configurations and the non-triviality of the Poisson boundary. In the case of
$F\wr\mathbb{Z}$, for $F$ finite or $F=\mathbb{Z}$, and supposing that lamp
configurations stabilize, the Poisson boundary will be non-trivial as soon as
$\mathrm{supp}(\mu)$ contains two distinct elements with the same projection
to $\mathbb{Z}$. Indeed, in such a case one can prove that there will be
distinct limit configurations that occur with positive probability, which in
turn provide non-trivial shift-invariant events in the space of infinite
trajectories. In contrast, the analogous statement for
${\mathsf{Shuffler}}(\mathbb{Z})$ does not hold. In Example 4.4 we exhibit a
family of virtually cyclic subgroups of ${\mathsf{Shuffler}}(\mathbb{Z})$,
generated by elements with the same projection to $\mathbb{Z}$, which has the
following property: for every finitary measure with transient projection to
$\mathbb{Z}$, the permutation coordinate of every trajectory stabilizes to the
same limit function $F:\mathbb{Z}\to\mathbb{Z}$. Note that, since such
subgroups are virtually cyclic, the Poisson boundary is trivial for any
probability measure.

###  1.1. Organization

In Section 2 we define the groups ${\mathsf{Shuffler}}(H)$, show that they
contain wreath products as subgroups whenever $H$ is co-Hopfian, and comment
on the similarities and differences between both families of groups.
Afterward, in Section 3 we recall preliminary facts about random walks and
Poisson boundaries. In Section 4 we prove the Stabilization Lemma in a more
general form (Lemma 4.5). We prove Theorem 1.2 in Section 5. Finally, in
Section 6 we show that finitary measures on ${\mathsf{Shuffler}}(H)$, for
$H=\mathbb{Z}$ or $H=\mathbb{Z}^{2}$, whose projection to $H$ induces a
recurrent random walk, have a trivial Poisson boundary.

###  1.2. Acknowledgments

I would like to thank my advisor Anna Erschler for her guidance and help with
this project, as well as Joshua Frisch for many stimulating discussions, and
Bogdan Stankov for helpful stylistic revisions. I would like to thank the
anonymous referee for their careful reading of the first version of this
paper, and for their comments that improved the exposition. This project has
received funding from the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement No
945322, and from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation program (grant agreement No
725773).

##  2\. Extensions of finitary symmetric groups

Let $H$ be a countable group, and consider the group $\mathrm{FSym}(H)$ of
bijective functions $f:H\to H$ such that only finitely many values $h\in H$
satisfy $f(h)\neq h$. We call the set of such elements the _support_ of $f$
and denote it by $\mathrm{supp}(f)$. Note that the group operation of
$\mathrm{FSym}(H)$ is the composition of functions, in contrast to the direct
sum $\bigoplus_{H}H$, where the group operation is pointwise multiplication.
We will denote the identity element of $\mathrm{FSym}(H)$ by $\mathsf{id}$.

Since $H$ has its own group structure, there is a natural left action of $H$
on functions $f:H\to H$. More precisely, for every $h\in H$ and $f:H\to H$ we
define $h\cdot f$ by

$(h\cdot f)(x)=hf(h^{-1}x),\text{ for }x\in H.$

Whenever $f$ has finite support, so does $h\cdot f$ and one has
$\mathrm{supp}(h\cdot f)=h\cdot\mathrm{supp}(f)$. Similarly, if $f$ is a
bijection, then so is $h\cdot f$. With this, $H$ has a well-defined action on
$\mathrm{FSym}(H)$, and we can consider the semi-direct product
${\mathsf{Shuffler}}(H)\coloneqq\mathrm{FSym}(H)\rtimes H$.

We now mention some of the geometric properties of these groups that have been
studied in the past decades, in addition to the ones related to random walks
that were already discussed in the introduction. The lampshuffler group
${\mathsf{Shuffler}}(\mathbb{Z})$ is considered in [VG97, Section 2.3] as an
example of a finitely generated group that is locally embeddable in the class
of finite groups (LEF) that is not residually finite (in the same paper it is
mentioned that this example goes back to Vershik’s Doctor of Sciences thesis
[Ver73]). Additionally, the group ${\mathsf{Shuffler}}(\mathbb{Z})$ was used
in [Stë83] as an example of a finitely generated non-residually finite group
which admits a freely approximable action. This is in contrast with [Stë83,
Theorem 1], which states that any finitely presented group that admits such an
action must be residually finite. The subgroup
$\mathrm{FAlt}(\mathbb{Z})\rtimes\mathbb{Z}$ of the lampshuffler group
${\mathsf{Shuffler}}(\mathbb{Z})$, where $\mathrm{FAlt}(\mathbb{Z})$ stands
for the group of finitary even permutations of $\mathbb{Z}$, is used in
[Cho80, Example 2] as an example of the existence of free subsemigroups in
elementary amenable groups that are not virtually solvable. In [ES06, Theorem
3] it is shown that if $H$ is an infinite, hyperbolic, residually finite group
with Kazhdan’s property (T), then the group ${\mathsf{Shuffler}}(H)$ is sofic
but not residually amenable. The group ${\mathsf{Shuffler}}(\mathbb{Z})$ is
used in [BZ19, Proposition 4.4] to provide an example of a locally-finite-
by-$\mathbb{Z}$ group that does not possess Shalom’s property
$H_{\mathrm{FD}}$.

###  2.1. Basic properties

Note that the group $\mathrm{FSym}(H)$ is locally finite, meaning that every
finitely generated subgroup is finite, and hence it is elementary amenable.
Since (elementary) amenability is preserved by group extensions, the group
${\mathsf{Shuffler}}(H)$ is (elementary) amenable whenever $H$ is.

We now show that whenever $H$ is finitely generated then so is the group
${\mathsf{Shuffler}}(H)$, and exhibit an explicit standard choice of
generators.

Define for any $x,y\in H$ the transposition
$\delta^{y}_{x}\in\mathrm{FSym}(H)$ by

$\delta^{y}_{x}(h)=\begin{cases}y,&\text{ if }h=x,\\\ x,&\text{ if }h=y,\text{
and}\\\ h&\text{ otherwise.}\end{cases}$

That is, $\delta_{x}^{y}$ corresponds to the bijection of $H$ that swaps $x$
and $y$, while leaving the rest of $H$ unchanged. We denote
$\delta_{x}\coloneqq\delta^{e_{H}}_{x}$, for $x\in H$.

Suppose now that $H$ is finitely generated, and fix a finite generating set
$S_{H}$ of $H$. Then a standard generating set for ${\mathsf{Shuffler}}(H)$ is
given by $S_{\mathrm{std}}=S_{H}\cup\\{\delta_{s}\mid s\in S_{H}\\}.$ Indeed,
it suffices to note that conjugating $\delta_{s}$ by generators of $S_{H}$
allows one to obtain transpositions between adjacent elements of any
arbitrarily large ball of $H$, and thus any permutation supported on it.

Note that for any $(f,x)\in{\mathsf{Shuffler}}(H)$, we have
$(f,x)\cdot(\mathsf{id},h)=(f,xh),$ for $h\in H,$ as well as
$(f,x)\cdot(\delta_{s},e_{H})=(f\circ(x\cdot\delta_{s}),x)=(f\circ\delta^{x}_{xs},x),$
for $s\in S_{H}.$ Hence, multiplying by elements of $H$ corresponds to a
translation of the second coordinate, while multiplying by $\delta_{s}$
corresponds to precomposing the first coordinate by a transposition in the
current position $x$ in the direction of $s$.

We summarize the above discussion in the following lemma.

######  Lemma 2.1.

Let $H$ be a countable group, and consider the extension
${\mathsf{Shuffler}}(H)\coloneqq\mathrm{FSym}(H)\rtimes H$.

  1. (1)

If $H$ is finitely generated by $S_{H}$, then ${\mathsf{Shuffler}}(H)$ is also
finitely generated and the set $S_{\mathrm{std}}\coloneqq
S_{H}\cup\\{\delta_{s}\mid s\in S_{H}\\}$ is a finite generating set.

  2. (2)

If $H$ is amenable, then so is ${\mathsf{Shuffler}}(H)$.

  3. (3)

If $H$ is elementary amenable, then so is ${\mathsf{Shuffler}}(H)$.

The following quantity will appear in the proof of Theorem 1.2.

######  Definition 2.2.

Given a word metric $d_{H}$ on $H$, we define the _displacement_ of a
permutation $\sigma\in\mathrm{FSym}(H)$ by
$\mathrm{Disp}(\sigma)\coloneqq\sum_{h\in H}d_{H}(h,\sigma(h)).$

Note that the above is well defined: since $\sigma$ is finitely supported, the
values $d_{H}(h,\sigma(h))$ vanish for all but finitely many elements $h\in
H$. We have the following lower bound for the word length in
${\mathsf{Shuffler}}(H)$ with respect to the generating set
$S_{\mathrm{std}}$.

######  Lemma 2.3.

For every $(\sigma,x)\in{\mathsf{Shuffler}}(H)$,

$\|(\sigma,x)\|_{S_{\mathrm{std}}}\geq\max\left\\{\frac{1}{2}\mathrm{Disp}(\sigma),\|x\|_{H}\right\\}.$

###### Proof.

Since the only elements of $S_{\mathrm{std}}$ that have non-trivial projection
to $H$ are those of $S_{H}$, it holds that
$\|(\sigma,x)\|_{S_{\mathrm{std}}}\geq\|x\|_{H}$. Indeed, the above implies
that any geodesic word of length $n$ for $(\sigma,x)$ in $S_{\mathrm{std}}$
projects to a word of length $n$ in $S_{H}$ that evaluates to $x$ in $H$.

On the other hand, each multiplication by a transposition $\delta_{s}\in
S_{\mathrm{std}}$ changes the value of $\mathrm{Disp}(\cdot)$ by at most $2$
units. This implies that $\mathrm{Disp}(\sigma)\leq
2\|(\sigma,x)\|_{S_{\mathrm{std}}}$. ∎

###  2.2. Wreath products subgroups in lampshufflers

Given groups $A$ and $B$, we recall that their wreath product is defined by
$A\wr B\coloneqq\bigoplus_{B}A\rtimes B$ (see also Subsection 3.3). As we
mentioned in the introduction, it is natural to compare
${\mathsf{Shuffler}}(H)$ to wreath products of the form $F\wr H$, for $F$ a
finite non-trivial group. The objective of this subsection is to show a
condition that guarantees that ${\mathsf{Shuffler}}(H)$ contains a subgroup
isomorphic to a wreath product $F\wr H$ with $F$ an arbitrary finite group. In
particular, we will see that this holds for $H=\mathbb{Z}^{d}$, $d\geq 1$, as
well as for any free group.

Recall that a group $H$ is called _co-Hopfian_ if every injective endomorphism
of $H$ is an isomorphism. In other words, a group is co-Hopfian if and only if
it is not isomorphic to a proper subgroup of itself.

######  Proposition 2.4.

Let $H$ be an infinite group that is not co-Hopfian. Then for every finite
group $F$, the group ${\mathsf{Shuffler}}(H)$ contains a subgroup isomorphic
to $F\wr H$.

###### Proof.

Suppose that $K\leqslant H$ is a proper subgroup with $K\cong H$ and fix
$n\geq 1$. Then we can choose $K$ such that its index $[H:K]$ is some value
$m\in\\{n,n+1,\ldots\\}\cup\\{\infty\\}$. Indeed, if $\varphi:H\to H$ is an
injective homomorphism then $[H:\varphi^{n}(H)]=[H:\varphi(H)]^{n}$. The
subgroup generated by $K$ together with the (finite) symmetric group on a
section of $H/K$ generates $\mathrm{FSym}(m)\wr K\cong\mathrm{FSym}(m)\wr H$,
where $\mathrm{FSym}(m)$ is the group of finitary permutations on a set of
cardinality $m$. Since any finite group embeds into $\mathrm{FSym}(m)$ for
some $m\geq 2$, this shows the proposition. ∎

Examples of groups that are not co-Hopfian are free abelian groups, free
groups, solvable Baumslag-Solitar groups [dlH00, Section III.22] and
Thompson’s group $F$ [Was11]. In contrast, the family of co-Hopfian groups
includes lattices in semi-simple Lie groups [Pra76], one-ended torsion-free
hyperbolic groups [Sel97], the group $\mathrm{Out}(F_{n})$, $n\geq 3$ [FH07,
HW20], and the mapping class group of a closed hyperbolic surface [IM99].

In the case of $H=\mathbb{Z}^{d}$, $d\geq 1$, we can show that the embedding
of a wreath product into ${\mathsf{Shuffler}}(\mathbb{Z}^{d})$ does not
distort its word metric. Recall that given two metric spaces $(X,d_{X})$ and
$(Y,d_{Y})$, the space $(X,d_{X})$ _embeds quasi-isometrically_ into
$(Y,d_{Y})$ if there exists a function $f:X\to Y$ and constants $C\geq 0$,
$K\geq 1$ such that for every $x_{1},x_{2}\in X$,

$\frac{1}{K}d_{X}(x_{1},x_{2})-C\leq d_{Y}(f(x_{1}),f(x_{2}))\leq
Kd_{X}(x_{1},x_{2})+C.$

######  Proposition 2.5.

For any $d\geq 1$ and any (non-trivial) finite group $F$, the wreath product
$F\wr\mathbb{Z}^{d}$ embeds quasi-isometrically into
${\mathsf{Shuffler}}(\mathbb{Z}^{d})$.

###### Proof.

Let $F$ be any non-trivial and finite group. Consider $m\geq 2$ such that $F$
is isomorphic to a subgroup of $\mathrm{Sym}(m)$ the symmetric group on $m$
elements. Since $F\wr\mathbb{Z}^{d}$ embeds quasi-isometrically into
$\mathrm{Sym}(m)\wr\mathbb{Z}^{d}$, in order to prove the proposition it
suffices to show that $\mathrm{Sym}(m)\wr\mathbb{Z}^{d}$ embeds quasi-
isometrically into ${\mathsf{Shuffler}}(\mathbb{Z}^{d})$.

Throughout the proof we will consider $\mathbb{Z}^{d}$ and its finite index
subgroup $H\coloneqq(m\mathbb{Z})^{d}$. In what follows we will use additive
notation when referring to the group operation of $\mathbb{Z}^{d}$ or $H$.

Let us denote $T\coloneqq\\{0,1,\ldots,m-1\\}^{d}\subseteq\mathbb{Z}^{d}$,
which corresponds to a set of representatives for $\mathbb{Z}^{d}/H$. Then
$\mathbb{Z}^{d}$ is partitioned into the cosets $\mathbf{h}+T$, for
$\mathbf{h}\in H$. This implies that we have the embedding of
$\mathrm{Sym}(m)\wr\mathbb{Z}^{d}\cong\mathrm{Sym}(T)\wr
H\leqslant{\mathsf{Shuffler}}(\mathbb{Z}^{d})$. In order to show that this is
a quasi-isometric embedding, let us introduce finite generating sets for these
groups.

Consider
$S_{\mathbb{Z}^{d}}=\\{\pm\hat{\mathbf{e}}_{1},\pm\hat{\mathbf{e}}_{2},\ldots,\pm\hat{\mathbf{e}}_{d},\mathbf{0}\\}$
the canonical generating set of $\mathbb{Z}^{d}$ together with the identity
element $\mathbf{0}\in\mathbb{Z}^{d}$. Consider the generating set
$S_{H}=\\{\pm m\hat{\mathbf{e}}_{1},\pm m\hat{\mathbf{e}}_{2},\ldots,\pm
m\hat{\mathbf{e}}_{d},\mathbf{0}\\}$ for $H$. With this, we define the finite
generating sets

$S_{\mathrm{wreath}}=\left\\{(\sigma,s)\mid\mathrm{Sym}(T)\text{ and }s\in
S_{H}\right\\}$

for $\mathrm{Sym}(T)\wr H$, and

$S_{\mathrm{ext}}=\left\\{(\sigma,s)\mid\mathrm{Sym}(T)\text{ and }s\in
S_{\mathbb{Z}^{d}}\cup S_{H}\right\\}$

for ${\mathsf{Shuffler}}(\mathbb{Z}^{d}).$ Note that
$S_{\mathrm{wreath}}\subseteq S_{\mathrm{ext}}$, and hence that
$\|g\|_{S_{\mathrm{ext}}}\leq\|g\|_{S_{\mathrm{wreath}}}$ for all
$g\in\mathrm{Sym}(T)\wr H$. In order to finish the proof, it suffices to show
the existence of a constant $C>0$ such that for every $g\in\mathrm{Sym}(T)\wr
H$, we have

$\|g\|_{S_{\mathrm{wreath}}}\leq C\|g\|_{S_{\mathrm{ext}}}.$ (1)

Let us consider an arbitrary element $g=(f,x)\in\mathrm{Sym}(T)\wr H$, and
denote $n\coloneqq\|g\|_{S_{\mathrm{ext}}}$.

Consider a word $w_{1}w_{2}\cdots w_{n}$ with $w_{i}\in S_{\mathrm{ext}}$ for
each $i=1,\ldots,n$ and $g=w_{1}w_{2}\cdots w_{n}$. For every $i=1,\ldots,n$,
define $\mathbf{h}_{i}\in H$ to be the unique element such that the projection
to $\mathbb{Z}^{d}$ of $w_{1}\cdots w_{i}$ belongs to $\mathbf{h}_{i}+T$. Also
denote $\mathbf{h}_{0}\coloneqq\mathbf{0}\in\mathbb{Z}^{d}$. In particular, we
have $\mathbf{h}_{n}=x$, which corresponds to the projection of $g$ to
$\mathbb{Z}^{d}$. We remark additionally that for every $i=0,1,\ldots,n-1$, we
have that $h_{i+1}=h_{i}+\sum_{j=1}^{d}\varepsilon_{j}m\hat{\mathbf{e}}_{j}$
for some values $\varepsilon_{j}\in\\{-1,0,1\\}$, for $j=1,\ldots,d$.

Note that for every $\mathbf{h}\in H$, the permutation $f$ restricts to a
bijection $f:\mathbf{h}+T\to\mathbf{h}+T$, and that

$\mathrm{supp}(f)\subseteq\bigcup_{i=0}^{n}(\mathbf{h}_{i}+B+T),$

where
$B=\left\\{\sum_{i=1}^{d}\varepsilon_{i}m\hat{\mathbf{e}}_{i}\mid\varepsilon_{1},\ldots,\varepsilon_{d}\in\\{0,1\\}\right\\}$.
This is since the function $f$ can only act non-trivially on copies of $T$
that correspond to $\mathbf{h}_{i}+T$, $i=0,1,\ldots,n$, or that are
neighboring to one of these cosets.

Then, since the generating set $S_{\mathrm{wreath}}$ allows to have any
permutation in $\mathrm{Sym}(T)$ accompanying any generator $s\in S_{H}$, in
order to show Equation (1) it suffices to prove the following statement: there
is a constant $C>0$, that only depends on $d$, such that there is a path of
length at most $Cn$ on the Cayley graph of $H$ with respect to $S_{H}$, that
starts at $\mathbf{0}\in H$, finishes at $x\in H$ and which visits all
elements in the set

$\\{\mathbf{h}_{i}+b\mid i=0,1,\ldots,n\text{ and }b\in B\\}.$

For every $i=0,1,\ldots,n-1$ we consider a path $p_{i}$ on the Cayley graph of
$H$ with respect to $S_{H}$ (whose vertices are identified with the lattice
$(m\mathbb{Z})^{d}\subseteq\mathbb{Z}^{d}$) that begins at $\mathbf{h}_{i}$,
finishes at $\mathbf{h}_{i+1}$ and visits all elements in the set
$\\{\mathbf{h}_{i}+b\mid b\in B\\}$. The length of such a path can be chosen
to be less than or equal to $2d\cdot 2^{d}+d$. Indeed, the path $p_{i}$ can be
formed as follows: consider the cycles that go from $\mathbf{h}_{i}$ to
$\mathbf{h}_{i}+b$ and back to $\mathbf{h}_{i}$ for each $b\in B$, which each
has length at most $2d$, and there are $2^{d}$ elements in $B$. By
concatenating these cycles together with a path from $\mathbf{h}_{i}$ to
$\mathbf{h}_{i+1}$, which can be chosen to have length at most $d$, we obtain
the path $p_{i}$ of length at most $2d\cdot 2^{d}+d$. Finally, we concatenate
all paths $p_{i}$, $i=0,1,\ldots,n$, and obtain a path of length at most
$(2d\cdot 2^{d}+d)n$ on the Cayley graph of $H$ with respect to $S_{H}$, that
starts at $\mathbf{0}\in H$, finishes at $x\in H$ and which visits all
elements in the set

$\\{\mathbf{h}_{i}+b\mid i=0,1,\ldots,n\text{ and }b\in B\\}.$

This path can then be used, as explained two paragraphs above, to construct a
word of length at most $(2d\cdot 2^{d}+d)n$ using generators from
$S_{\mathrm{wreath}}$ that evaluates as a group element to $g$. This finishes
the proof, since we have proved that one can choose $C=2d\cdot 2^{d}+d$ so
that Equation (1) holds. ∎

###  2.3. Cyclic extensions of locally finite groups

Our main theorem (Theorem 1.2) concerns the group
${\mathsf{Shuffler}}(\mathbb{Z})$, which is an extension by $\mathbb{Z}$ of
the locally finite group $\mathrm{FSym}(\mathbb{Z})$. In this subsection, we
discuss the geometric properties present in groups that exhibit this algebraic
structure and motivate the study of random walks on them.

Recall that a group $\mathcal{L}$ is called _locally finite_ if every finitely
generated subgroup is finite. A group $G$ is a _cyclic extension of a locally
finite group_ or _locally-finite-by- $\mathbb{Z}$_ if there is a short exact
sequence

$1\rightarrow\mathcal{L}\rightarrow G\rightarrow\mathbb{Z}\rightarrow 1,$ (2)

where $\mathcal{L}$ is a locally finite group. Observe that any such sequence
must necessarily split, so that $G=\mathcal{L}\rtimes\mathbb{Z}$. In
particular, the group ${\mathsf{Shuffler}}(\mathbb{Z})$ as well as wreath
products of the form
$F\wr\mathbb{Z}=\bigoplus_{\mathbb{Z}}F\rtimes\mathbb{Z}$, for a non-trivial
and finite group $F$, are cyclic extensions of locally finite groups. Other
groups in this category are the discrete affine groups of a regular tree.
These groups were introduced in [BTZ21], where their Poisson boundary was
described for finitary measures. If every finitely generated subgroup of
$\mathcal{L}$ is contained in a finite _normal_ subgroup of $\mathcal{L}$,
then we say that $\mathcal{L}$ is _locally normally finite_. Notably,
$\bigoplus_{\mathbb{Z}}F$ is locally normally finite, while
$\mathrm{FSym}(\mathbb{Z})$ is not. This provides an algebraic distinction
between the groups $F\wr\mathbb{Z}$ and ${\mathsf{Shuffler}}(\mathbb{Z})$.
Cyclic extensions of locally normally finite groups are studied in [BZ19].

Cyclic extensions of locally finite groups can have arbitrarily fast-growing
Følner functions. This was first observed in the last remark of Section 3 in
[Ers03] (see also [Gro08, Section 8.2]), and a proof of this result is given
in [OO13, Corollary 1.5]. In [BZ21, Theorem 1.1], it is proven that locally-
finite-by-$\mathbb{Z}$ groups exhibit a large class of speed, return
probability, entropy, isoperimetric profiles, and $L_{p}$-compression
functions. In particular, the authors prove that any sufficiently regular
function that grows at least exponentially can be realized as the Følner
function of a locally-finite-by-$\mathbb{Z}$ group, which admits a simple
random walk with a trivial Poisson boundary [BZ21, Corollary 4.7]. This
behavior differs from what happens for the linear algebraic Følner function,
introduced in [Gro08, Section 1.9]. In general, this function is bounded above
by the usual (combinatorial) Følner function, and both of them coincide for
left-orderable groups [Gro08, Section 3.2]. In contrast, the linear algebraic
Følner function of every locally-finite-by-$\mathbb{Z}$ group grows linearly
[Gro08, Section 8.1].

There are locally-finite-by-$\mathbb{Z}$ groups that admit simple random walks
with a non-trivial Poisson boundary. Examples of this are
$\mathbb{Z}/2\mathbb{Z}\wr\left(\mathbb{Z}/2\mathbb{Z}\wr\mathbb{Z}\right)$
and the discrete affine group of a regular tree [BTZ21]. On the other hand, we
mentioned above that [BZ21, Corollary 4.7] provides a large family of locally-
finite-by-$\mathbb{Z}$ groups that admit simple random walks with a trivial
Poisson boundary. As a more concrete example, simple random walks on the
groups $F\wr\mathbb{Z}$, for $F$ finite or $F=\mathbb{Z}$, and
${\mathsf{Shuffler}}(\mathbb{Z})$ also have a trivial boundary. The case of
wreath products is proven in [KV83, Proposition 6.2], while the case of
${\mathsf{Shuffler}}(\mathbb{Z})$ follows from the sublinear asymptotics of
the drift function [Yad09]. Moreover, every probability measure on
$F\wr\mathbb{Z}$ with a recurrent projection to the base group $\mathbb{Z}$
has a trivial Poisson boundary. This is proven in [KV83, Proposition 6.3] and
[Kai83] for finitary measures, in [Kai91] for finite first moment measures,
and in [LP21, Proposition 4.9] for the general case, by using the
classification of Choquet-Deny groups [FHTVF19]. In contrast, this
generalization does not hold for ${\mathsf{Shuffler}}(\mathbb{Z})$. Indeed,
the group $\mathrm{FSym}(\mathbb{Z})$ admits symmetric measures with finite
entropy and with a non-trivial Poisson boundary [Kai83] (this also follows
from [FHTVF19], since every non-trivial element of $\mathrm{FSym}(\mathbb{Z})$
has an infinite conjugacy class). In consequence,
${\mathsf{Shuffler}}(\mathbb{Z})$ admits (degenerate) random walks with a non-
trivial Poisson boundary and a recurrent projection to $\mathbb{Z}$.

##  3\. Background on random walks and Poisson boundaries

###  3.1. Random walks on groups

Let $G$ be a countable group and $\mu$ a probability measure on $G$. The
_(right) $\mu$-random walk_ $(G,\mu)$ is the Markov chain with state space
$G$, whose transition probabilities are given by

$p(g,h)\coloneqq\mu(g^{-1}h),\ g,h\in G.$

We assume that the $\mu$-random walk starts at the identity $e_{G}\in G$. The
space of infinite trajectories of the random walk $G^{\infty}$ is endowed with
the probability $\mathbb{P}$, which is the push-forward of the Bernoulli
measure $\mu^{\mathbb{N}}$ on the space of increments $G^{\infty}$ through the
map

$\displaystyle G^{\infty}$ $\displaystyle\to G^{\infty}$
$\displaystyle(g_{1},g_{2},g_{3},\ldots)$
$\displaystyle\mapsto(g_{1},g_{1}g_{2},g_{1}g_{2}g_{3},\ldots).$

Suppose that $G$ is finitely generated, and let $\ell_{G}$ be a word length on
$G$. For $\alpha>0$, a probability measure $\mu$ on $G$ is said to have a
_finite $\alpha$-moment_ if $\sum_{g\in G}\ell_{G}(g)^{\alpha}\mu(g)<\infty$.
This property does not depend on the choice of $\ell_{G}$, since changing the
word length on a group modifies the metric by a multiplicative constant.

###  3.2. The Poisson boundary

Let us now recall the definition of the Poisson boundary, together with some
equivalent definitions. For background on random walks on countable groups and
their Poisson boundaries, we refer to [KV83, Kai00], the surveys [Ers10,
Zhe22], and the introduction and Section 3 of [EK23].

Given two trajectories $\mathbf{x}=(x_{1},x_{2},\ldots)$ and
$\mathbf{y}=(y_{1},y_{2},\ldots)$ in $G^{\infty}$, say that they are _orbit
equivalent_ if there exist $p,N\geq 0$ such that $x_{p+n}=y_{n}$ for every
$n\geq N$. Consider the measurable hull of this equivalence relation in
$G^{\infty}$. That is, the $\sigma$-algebra of measurable subsets of
$G^{\infty}$ which are unions of the equivalence classes, modulo
$\mathbb{P}$-null sets. The associated quotient of the space of infinite
trajectories by this measurable hull is called the _Poisson boundary_
$\partial_{\mu}G$ of the random walk $(G,\mu)$. Equivalently, the Poisson
boundary is the space of ergodic components of the _shift map_ of the space of
infinite trajectories, defined by

$\displaystyle T:G^{\infty}$ $\displaystyle\to G^{\infty}$
$\displaystyle(x_{1},x_{2},x_{3},\ldots)$
$\displaystyle\mapsto(x_{2},x_{3},\ldots).$

If we do not allow the shift by $p$ in the definition of the orbit equivalence
relation above, we obtain the _tail equivalence_ relation. The associated
quotient space is called the _tail boundary_ of the random walk, and it
provides an alternative and equivalent definition of the Poisson boundary of a
random walk on a group [Der80, KV83]. We remark that the Poisson boundary can
be defined for general Markov chains, and these two definitions are no longer
equivalent in this broader context (see [BF64, Example 2] and [Kai92, Theorem
2.2]).

Recall that a function $f:G\to\mathbb{R}$ is called _$\mu$ -harmonic_ if for
every $g\in G$, it holds that $f(g)=\sum_{h\in G}f(gh)\mu(h)$. The Poisson
boundary of $(G,\mu)$ can be described in terms of the space of bounded
$\mu$-harmonic functions on the subgroup generated by $\mathrm{supp}(\mu)$. In
particular, the non-triviality of the Poisson boundary of a non-degenerate
random walk is equivalent to the existence of non-constant bounded
$\mu$-harmonic functions on $G$.

Now we introduce the concept of a $\mu$-boundary of $G$. Let us denote by
$\mathbf{bnd}:G^{\infty}\to\partial_{\mu}G$ the associated quotient map from
the space of trajectories onto the Poisson boundary. The space
$\partial_{\mu}G$ is endowed with the so-called _harmonic measure_
$\nu\coloneqq\mathbf{bnd}_{*}(\mathbb{P})$, which satisfies the equation
$\mu*\nu=\nu$. One says that $\nu$ is _$\mu$ -stationary_. Thus, the Poisson
boundary of $(G,\mu)$ has the structure of a measure space
$(\partial_{\mu}G,\mathcal{F},\nu)$ endowed with a measurable $G$-equivariant
map $\mathbf{bnd}:G^{\infty}\to\partial_{\mu}G$ that satisfies

  1. (1)

$\mathcal{I}=\mathbf{bnd}^{-1}(\mathcal{F})$ modulo $\mathbb{P}$-null sets,
where $\mathcal{I}$ is the sub-$\sigma$-algebra of shift-invariant events of
the space of trajectories $G^{\infty}$, and

  2. (2)

the measure $\nu=\mathbf{bnd}_{*}(\mathbb{P})$ is $\mu$-stationary, which by
definition means that it satisfies the equation
$\nu=\mu*\nu\coloneqq\sum_{g\in G}\mu(g)g\nu.$

In general, a measure space $(B,\mathcal{A},\lambda)$ endowed with a
measurable $G$-action is called a _$\mu$ -boundary_ of $G$ if there exists a
$G$-equivariant measurable map $\pi:G^{\infty}\to B$ for which
$\lambda=\pi_{*}(\mathbb{P})$ is $\mu$-stationary and such that
$\pi^{-1}(\mathcal{A})\subseteq\mathcal{I}$ modulo $\mathbb{P}$-null sets. The
Poisson boundary of $(G,\mu)$ is the _maximal_ $\mu$-boundary of $G$, in the
sense that for every $\mu$-boundary $(B,\mathcal{A},\lambda)$, the projection
$\pi:G^{\infty}\to B$ factors through the map $\mathbf{bnd}$, and it is unique
up to a $G$-equivariant measurable isomorphism.

###  3.3. The Poisson boundary of wreath products

We illustrate the above notions with the case of wreath products, which also
serves as a point of comparison with the results of this paper.

Recall that given groups $A$ and $B$, their wreath product $A\wr B$ as the
semidirect product $\bigoplus_{B}A\rtimes B$, where $B$ acts by translations
on the direct sum $\bigoplus_{B}A$. We remark that some authors use the
notation $B\wr A$. Wreath products are also called “lamplighter groups”, and
for an element $(f,x)\in A\wr B$, the function $f$ is referred to as the “lamp
configuration”.

Kaimanovich and Vershik [KV83] proved that for
$\mathbb{Z}/2\mathbb{Z}\wr\mathbb{Z}^{d}$, $d\geq 1$, and for any non-
degenerate finitely supported measure $\mu$ whose projection to
$\mathbb{Z}^{d}$ induces a transient random walk, the lamp configurations
stabilize almost surely. In other words, with probability one, the values
assigned by the lamp configuration to a given finite subset of
$\mathbb{Z}^{d}$ change only finitely many times along the trajectory of the
random walk. Hence, the space of limit lamp configurations has the structure
of a $\mu$-boundary, and its non-triviality implies that the Poisson boundary
is non-trivial as well. These were the first examples of measures with non-
trivial boundary on amenable groups, and Kaimanovich and Vershik conjectured
that the space of limit configurations coincides with the Poisson boundary.
This was proven under the hypotheses of a finite first moment of $\mu$ and
projection to $\mathbb{Z}^{d}$ with non-zero drift by Kaimanovich [Kai01,
Theorem 3.6.6], whereas the case of zero drift, for $d\geq 3$, remained open.
The Poisson boundary was later described for $A\wr B$ where $A$ is finite and
$B$ is a free group [KW07], or where $B$ has infinitely many ends, or is
hyperbolic [Sav10]. The case of measures on $A\wr\mathbb{Z}^{d}$ with a
centered projection to $\mathbb{Z}^{d}$ was proved for $d\geq 5$ by Erschler
[Ers11], and by Lyons and Peres for $d\geq 3$ [LP21], both with additional
moment conditions on $\mu$.

###  3.4. The conditional entropy criterion

Recall that the _entropy_ $H(\mu)$ of a probability measure $\mu$ on $G$ is
defined as $H(\mu)\coloneqq-\sum_{g\in G}\mu(g)\log(\mu(g))$. Avez [Ave72]
introduced the _asymptotic entropy_ of the random walk $(G,\mu)$, defined as
$h(\mu)\coloneqq\lim_{n\to\infty}H(\mu^{*n})/n$. The existence of this limit
is guaranteed by the subadditivity of the sequence $H_{n}\coloneqq
H(\mu^{*n})$, $n\geq 1$. Avez [Ave74] proved that if $h(\mu)=0$, then the
random walk has a trivial Poisson boundary. Furthermore, the _Entropy
Criterion_ , due to Derrienic [Der80] and Kaimanovich and Vershik [KV83]
states that if $H(\mu)<\infty$, then $h(\mu)=0$ if and only if the Poisson
boundary of the $\mu$-random walk on $G$ is trivial. This criterion was
strengthened by Kaimanovich to a _Conditional Entropy Criterion_ , which we
state below.

######  Theorem 3.1 ([Kai00, Theorem 4.6]).

Let $\mu$ be a probability measure on $G$ with finite entropy, and consider
$\mathbf{B}=(B,\mathcal{A},\nu)$ a $\mu$-boundary of $G$. Suppose that for
every $\varepsilon>0$ there exists a random sequence of finite subsets
$\\{Q_{n,\varepsilon}\\}_{n\geq 1}$ of $G$ such that

  1. (1)

the random set $Q_{n,\varepsilon}$ is a measurable function with respect to
$\mathcal{A}$, for every $n\geq 1$;

  2. (2)

$\displaystyle\limsup_{n\to\infty}\frac{1}{n}\log|Q_{n,\varepsilon}|<\varepsilon$
almost surely; and

  3. (3)

$\displaystyle\limsup_{n\to\infty}\mathbb{P}\left(x_{n}\in
Q_{n,\varepsilon}\right)>0$, where $\\{x_{n}\\}_{n\geq 1}$ is the trajectory
of the $\mu$-random walk.

Then $\mathbf{B}$ coincides with the Poisson boundary of $(G,\mu)$.

This result is a common tool used to prove the maximality of a $\mu$-boundary
for a random walk on a group, and we will use it in the proof of Theorem 1.2.
We mention that Lyons and Peres [LP21, Corollary 2.3] proved an alternative
version of this criterion, where the third condition of Proposition 3.1 is
replaced by

$\limsup_{n\to\infty}\mathbb{P}\left(\text{ there exists }m\geq n\text{ such
that }x_{m}\in Q_{n,\varepsilon}\right)>0.$

This condition is easier to verify in some situations [LP21, BTZ21]. For
Theorem 1.2 we will apply the original version.

##  4\. Random walks on ${\mathsf{Shuffler}}(H)$

###  4.1. Stabilization of the permutation coordinate

We study conditions on the measure $\mu$ that guarantee the stabilization of
the permutation coordinate to a limit function $F_{\infty}:H\to H$. We first
give a precise definition of stabilization.

######  Definition 4.1.

We say that the permutation coordinate $\\{F_{n}\\}_{n\geq 1}$ of the
$\mu$-random walk $\left\\{(F_{n},S_{n})\right\\}_{n\geq 0}$ on
${\mathsf{Shuffler}}(H)$ _stabilizes_ if almost surely for every $h\in H$,
there exists $N\geq 1$ such that $F_{n}(h)=F_{N}(h)$ for all $n\geq N$.

Whenever the permutation coordinate stabilizes, we can associate with almost
every trajectory $\left\\{(F_{n},S_{n})\right\\}_{n\geq 0}$ of the
$\mu$-random walk a limit function $F_{\infty}:H\to H$, which satisfies for
every $h\in H$, $F_{n}(h)=F_{\infty}(h)$ for large enough $n$. Since every
function $F_{n}$ is a bijection from $H$ to itself, $F_{\infty}$ will be
injective. However, it may happen that the limit function is not surjective.

######  Example 4.2.

Consider $F(X)$ the free group on a finite set $X\neq\varnothing$, and let
$\mu$ be any probability measure on ${\mathsf{Shuffler}}(F(X))$ whose support
is the set $\\{(\delta_{x},x)\mid x\in X\\}$. The projection $\\{S_{n}\\}_{n}$
of the $\mu$-random walk to $F(X)$ is supported on the free semigroup
generated by $X$, and hence it will converge to a geodesic ray
$\gamma:[0,+\infty)\to F(X)$. Since the support of $\mu$ consists of elements
of the form $(\delta_{x},x)$, the permutation coordinate of the $\mu$-random
walk will stabilize to a limit function $F_{\infty}$, that satisfies
$F_{\infty}(\gamma(i))=\gamma(i+1)$, $i\geq 0$, and $F_{\infty}(h)=h$ for any
$h$ outside of the image of $\gamma$. In particular, the identity element does
not have a preimage through $F_{\infty}.$ Note also that the Poisson boundary
of $({\mathsf{Shuffler}}(F(X)),\mu)$ is non-trivial whenever $|X|\geq 2$.

######  Proposition 4.3.

Let $H$ be an infinite countable group and $\mu$ a non-degenerate probability
measure on ${\mathsf{Shuffler}}(H)$. Suppose that the permutation coordinate
of the $\mu$-random walk stabilizes. Then the Poisson boundary of
$({\mathsf{Shuffler}}(H),\mu)$ is non-trivial.

###### Proof.

Denote by $F_{\infty}:H\to H$ the limit function of the permutation coordinate
of the random walk $(F_{n},S_{n})$ on ${\mathsf{Shuffler}}(H)$. If the Poisson
boundary is trivial, then the function $F_{\infty}$ is the same for almost
every trajectory of the random walk. Consider the left action of
${\mathsf{Shuffler}}(H)$ on the space of limit functions $F_{\infty}$. The
stabilization together with the non-degeneracy assumption imply that
$F_{\infty}=f\circ F_{\infty},\text{ for all }f\in\mathrm{FSym}(H).$ This is a
contradiction since every function $f\in\mathrm{FSym}(H)$ that acts non-
trivially on $F_{\infty}(H)$ will not satisfy this equation. ∎

A similar result holds for wreath products $A\wr B$, where it is enough to
suppose that the semigroup generated by $\mathrm{supp}(\mu)$ contains two
distinct elements with equal projections to $B$ (see the proof of Theorem 3.3
in [Kai91] and the discussion after Lemma 1.1 in [Ers11]). Below, we provide
an example that shows that in ${\mathsf{Shuffler}}(H)$ an analogous hypothesis
does not suffice to guarantee the non-triviality of the Poisson boundary.

We will consider subgroups of ${\mathsf{Shuffler}}(\mathbb{Z})$ whose
projection to $\mathbb{Z}$ are proper subgroups of $\mathbb{Z}$. Among these
subgroups, we can find wreath products (Proposition 2.4), which admit finite
first moment measures with non-trivial boundary. Hence, in order to find
subgroups with trivial boundary we will also need to restrict the possible
values for the permutation coordinate of the elements of these subgroups.

######  Example 4.4.

Let us fix $M\geq 3$ and consider the finite subset
$\Sigma_{M}\leqslant\mathrm{FSym}(\mathbb{Z})$ formed by all
$f\in\mathrm{FSym}(\mathbb{Z})$ such that $\mathrm{supp}(f)\subseteq[-M,M]$,
and $f(x)=x+M$ whenever $-M\leq x\leq 0$. That is, a permutation
$f\in\Sigma_{M}$ coincides with the identity outside of $[-M,M]$, acts as a
translation by $M$ on the interval $[-M,0]$ and maps bijectively the set
$[1,M]$ to $[-M,-1]$.

Let $K$ be the subgroup of ${\mathsf{Shuffler}}(\mathbb{Z})$ generated by
elements of the form $(f,M+1)$, for $f\in\Sigma_{M}$. Let us denote by $S_{K}$
the set formed by the above generators, together with their inverses. Note
that for $f\in\Sigma_{M}$, the inverse of $(f,M+1)$ is given by
$(\tilde{f},-(M+1))$, where

$\tilde{f}(x)=\begin{cases}x+M,&\text{ if }x\in[-M-1,-1],\\\
-M-1+f^{-1}(x+M+1),&\text{ if }x\in[-2M-1,-M-2],\text{ and}\\\ x,&\text{
otherwise}.\end{cases}$

In particular, we see that the values of $\tilde{f}$ are uniquely determined
on the interval $[-M-1,1]$. Furthermore, when multiplying two elements
$(f_{1},j_{1}(M+1)),(f_{2},j_{2}(M+1))\in S_{K}$, one obtains

$(f_{1},j_{1}(M+1))\cdot(f_{2},j_{2}(M+1))=(f_{3},(j_{1}+j_{2})(M+1)),$

where

$f_{3}=f_{1}\circ\left(j_{1}(M+1)\cdot f_{2}\right),$

and the places where $f_{3}$ is not uniquely determined are a translation of
those of $f_{2}$, which is a set of size $M$. From this, one can see that the
elements of $K$ are all of the form $g=(f,j(M+1))$, for $j\in\mathbb{Z}$ and
for $f\in\mathrm{FSym}(\mathbb{Z})$ a permutation whose values are uniquely
determined by the value of $j$, except for those of the interval
$[(j-1)(M+1)+1,j(M+1)-1]$, which has size $M$. Further, if the element $g$ is
a product of $n$ generators in $S_{K}$, then it holds that $|j|\leq n$. Thus,
the growth function of $K$ is bounded above by $nM!$ and as a result, the
group $K$ has a linear growth function.

Gromov’s Theorem on groups of polynomial growth [Gro81] implies that $K$ is
virtually nilpotent, and the Bass–Guivarc’h formula [Bas72, Gui73] shows that
any virtually nilpotent group of linear growth is virtually $\mathbb{Z}$. We
conclude that $K$ is virtually cyclic, and hence any random walk supported on
$K$ has a trivial Poisson boundary. Nonetheless, Lemma 1.1 implies that the
permutation coordinate will stabilize for a given measure $\mu$ with a finite
first moment measure supported on $K$ with a non-centered projection to
$\mathbb{Z}$. Since we already know that the Poisson boundary is trivial, it
must hold that almost every trajectory of the random walk stabilizes to the
same limit function. Indeed, if the projection of $\mu$ to $\mathbb{Z}$ has
positive drift, then the limit function $F_{\infty}$ is almost surely given by
$F_{\infty}(x)=x+M$, $x\in\mathbb{Z}$, whereas if the drift is negative, the
limit function is $F_{\infty}(x)=x-M$, $x\in\mathbb{Z}$.

It is natural to draw a parallel with Proposition 4.3. In the above example,
the permutation coordinate of every trajectory stabilizes to the same limit
function $F$, which is not surjective. In the case of positive drift in the
projection to $\mathbb{Z}$, the image of $F$ is $\mathbb{Z}\backslash[-M,-1]$.
We saw that any element $g\in K$ is of the form $g=(f,j(M+1))$, with
$j\in\mathbb{Z}$ and where the values of $f$ are uniquely determined, except
for those of the interval $[(j-1)(M+1)+1,j(M+1)-1]$. When looking at the
action of $g$ on the limit function $F$ we get

$g\cdot F=f\circ(j(M+1)\cdot F),$

and we note that the function $j(M+1)\cdot F$ has as its image
$\mathbb{Z}\backslash[(j-1)(M+1)+1,j(M+1)-1]$, which is exactly the set where
$f$ is uniquely determined. In other words, all the elements of $K$ act
trivially on $F$.

We now state and prove the stabilization lemma in its general form, and then
prove Lemma 1.1. In addition to transience of the random walk induced on $H$,
the second hypothesis below is that
$\mathbb{E}\left(|\mathrm{supp}(\sigma_{1})|\right)<\infty$. This means that
the number of elements on which a randomly chosen permutation $\sigma_{1}$
acts non-trivially has a finite expectation.

######  Lemma 4.5.

Let $H$ be a countable group and $\mu$ be a probability measure on
${\mathsf{Shuffler}}(H).$ Suppose that $\mu$ induces a transient random walk
on $H$ and that $\mathbb{E}\left(|\mathrm{supp}(\sigma_{1})|\right)<\infty$.
Then the permutation coordinate of the $\mu$-random walk on
${\mathsf{Shuffler}}(H)$ stabilizes.

###### Proof.

Fix an arbitrary element $h\in H$, and for every $n\geq 1$ consider the event
$A_{n}=\left\\{F_{n+1}(h)\neq F_{n}(h)\right\\}.$ We will prove that
$\sum_{n\geq 0}\mathbb{P}(A_{n})<+\infty$, so that the Borel-Cantelli Lemma
[Fel68, Lemma VIII.3.1] will imply that almost surely only finitely many of
these events happen. Since $H$ is countable, the above implies that the
stabilization of $F_{n}(h)$ for every $h\in H$ happens with probability $1$.

Using the group operation and the definition of the action of $H$ on
$\mathrm{FSym}(H)$, we see that

$F_{n+1}(h)=F_{n}\circ(S_{n}\cdot\sigma_{n+1})(h)=F_{n}\left(S_{n}\sigma_{n+1}(S^{-1}_{n}h)\right),$

so that $A_{n}\subseteq\\{\sigma_{n+1}(S^{-1}_{n}h)\neq S^{-1}_{n}h\\}.$ With
this, we can obtain an upper estimate for the probability of $A_{n}$. Indeed,

$\displaystyle\mathbb{P}(A_{n})$
$\displaystyle\leq\mathbb{P}\left(\sigma_{n+1}(S^{-1}_{n}h)\neq
S^{-1}_{n}h\right)$ $\displaystyle=\sum_{x\in
H}\mathbb{P}\left(\sigma_{n+1}(x^{-1}h)\neq x^{-1}h\right)\mathbb{P}(S_{n}=x)$
$\displaystyle=\sum_{x\in
H}\mathbb{P}\left(x^{-1}h\in\mathrm{supp}(\sigma_{n+1})\right)\mathbb{P}(S_{n}=x)$
$\displaystyle=\sum_{x\in
H}\sum_{(f,y)\in{\mathsf{Shuffler}}(H)}\mathds{1}_{\left\\{x^{-1}h\in\mathrm{supp}(f)\right\\}}\mu(f,y)\mathbb{P}(S_{n}=x).$

Now we are going to sum over all $n$. Note that since we assume that the
projection of $\mu$ to $H$ is transient, there exists a constant $C>0$ such
that for every $x\in H$, $\sum_{n\geq 1}\mathbb{P}(S_{n}=x)<C.$ Indeed, the
left-hand side is the expected number of visits to $x$, which is equal to the
probability of ever reaching $x$ multiplied by the expected number of visits
to $e_{H}$. The first term is at most $1$ (since it is a probability), and the
second one is a finite constant, thanks to our transience hypothesis.

We can conclude that

$\displaystyle\sum_{n\geq 1}\mathbb{P}(A_{n})$ $\displaystyle\leq\sum_{n\geq
1}\sum_{x\in
H}\sum_{(f,y)\in{\mathsf{Shuffler}}(H)}\mathds{1}_{\left\\{x^{-1}h\in\mathrm{supp}(f)\right\\}}\mu(f,y)\mathbb{P}(S_{n}=x)$
$\displaystyle\leq C\sum_{(f,y)\in{\mathsf{Shuffler}}(H)}\sum_{x\in
H}\mathds{1}_{\left\\{x^{-1}h\in\mathrm{supp}(f)\right\\}}\mu(f,y)$
$\displaystyle=C\sum_{(f,y)\in{\mathsf{Shuffler}}(H)}|\mathrm{supp}(f)|\mu(f,y)=C\mathbb{E}(|\mathrm{supp}(\sigma_{1})|)<\infty.$

which is finite thanks to our hypothesis. ∎

###### Proof of Lemma 1.1.

When $H$ is finitely generated, so is ${\mathsf{Shuffler}}(H)$ and the
condition $\mathbb{E}(|\mathrm{supp}(\sigma_{1})|)<\infty$ follows from the
finite first moment hypothesis. Indeed, recall the definition of
$S_{\mathrm{std}}$ from Lemma 2.1. Each transposition in $S_{\mathrm{std}}$
changes the value of exactly two elements of $H$, and hence a geodesic word
for $(f,y)$ needs at least as many transpositions as half the size of the
support of $f$. In other words, we have the inequality $|\mathrm{supp}(f)|\leq
2\|(f,y)\|_{S_{\mathrm{std}}}$ for every $(f,y)\in{\mathsf{Shuffler}}(H)$.
This implies that

$\displaystyle\mathbb{E}(|\mathrm{supp}(\sigma_{1})|)$
$\displaystyle=\sum_{(f,y)\in{\mathsf{Shuffler}}(H)}|\mathrm{supp}(f)|\mu(f,y)$
$\displaystyle\leq\sum_{(f,x)\in{\mathsf{Shuffler}}(H)}2\|(f,x)\|_{S_{\mathrm{std}}}\mu(f,x)<\infty,$

and so we can apply Lemma 4.5. ∎

By combining Proposition 4.3 with Lemma 4.5 we obtain the following corollary.

######  Corollary 4.6.

Let $\mu$ be a non-degenerate probability measure on ${\mathsf{Shuffler}}(H)$
that induces a transient random walk on $H$, such that
$\mathbb{E}(|\mathrm{supp}(\sigma_{1})|)<\infty$. Then the Poisson boundary of
$({\mathsf{Shuffler}}(H),\mu)$ is non-trivial.

######  Remark 4.7.

It may happen that the permutation coordinate of a random walk on
${\mathsf{Shuffler}}(H)$ with a transient projection to $H$ does not
stabilize. Indeed, whenever $H$ is amenable, the group
${\mathsf{Shuffler}}(H)$ is amenable (Lemma 2.1) and it was shown by
Rosenblatt [Ros81] and Kaimanovich and Vershik [KV83, Theorem 4.4] that every
amenable group admits a non-degenerate probability measure with a trivial
Poisson boundary. For such $\mu$, Proposition 4.3 implies that the permutation
coordinate cannot stabilize. Furthermore, if $H$ is not virtually $\mathbb{Z}$
or virtually $\mathbb{Z}^{2}$, the projected random walk to $H$ will be
transient, due to [Var86] (see also [Woe00, Theorem 3.24]).

The above remark implies that ${\mathsf{Shuffler}}(\mathbb{Z}^{d})$, $d\geq
3$, carries a random walk with a non-degenerate symmetric step distribution,
with a transient projection to $\mathbb{Z}^{d}$ and such that the permutation
coordinate does not stabilize. On the other hand, the existence of such
measures for $d=1$ or $d=2$ is not immediate since the projected random walk
to the corresponding base group could be recurrent. In the next proposition,
we prove that for $H=\mathbb{Z}$ one can choose these measures so that the
projection to $\mathbb{Z}$ is transient, by modifying the proofs of [KV83,
Theorem 4.4] and [Ros81, Theorem 1.10].

######  Proposition 4.8.

There exists a non-degenerate symmetric probability measure $\mu$ on
${\mathsf{Shuffler}}(\mathbb{Z})$, that induces a transient random walk on
$\mathbb{Z}$ and such that the Poisson boundary of
$({\mathsf{Shuffler}}(\mathbb{Z}),\mu)$ is trivial.

###### Proof.

Let us write $G={\mathsf{Shuffler}}(\mathbb{Z})$ and $\pi:G\to\mathbb{Z}$ the
projection map.

Let $\\{K_{i}\\}_{i\geq 1}$ be an increasing sequence of finite subsets of $G$
such that $e\in K_{1}$ and $G=\bigcup_{i\geq 1}K_{i}$. Let us consider

  * •

A sequence $\\{t_{i}\\}_{i\geq 1}$ of positive numbers such that $\sum_{i\geq
1}t_{i}=1$,

  * •

a decreasing sequence $\\{\varepsilon_{i}\\}_{i\geq 1}$ of positive numbers
such that $\sum_{i\geq 1}\varepsilon_{i}<+\infty$, and

  * •

sequences of integers $\\{n_{i}\\}_{i\geq 1}$ and $\\{p_{i}\\}_{i\geq 1}$ with
$n_{i},p_{i}\xrightarrow[i\to\infty]{}+\infty$ such that

$(t_{1}+t_{2}+\cdots+t_{i-1})^{n_{i}}\leq\varepsilon_{i}\text{ and
}(t_{1}+t_{2}+\cdots+t_{p_{i}-1})^{i}\leq\varepsilon_{i}.$

For example, one can choose $t_{i}=2^{-i}$, $p_{i}=\lfloor\log(i)\rfloor+1$,
$\varepsilon_{i}=\left(1-2^{-\log(i)}\right)^{i}$ and

$n_{i}=\left\lceil\frac{i\log\left(1-2^{-\log(i)}\right)}{\log\left({1-2^{-i+1}}\right)}\right\rceil.$

Since $G$ is amenable, we can find a sequence of symmetric Følner sets
$\\{A_{m}\\}_{m\geq 1}$ such that, denoting
$\alpha_{m}=\frac{1}{|A_{m}|}\chi_{A_{m}}$ the uniform probability measure on
$A_{m}$, we have

$\|\alpha_{m}-g\alpha_{m}\|\leq\varepsilon_{m},\text{ for all }g\in
K_{m}\cup(A_{m-1})^{n_{m}}.$

These sets can be chosen so that $A_{m}$ contains $K_{m}\cup(A_{m-1})^{n_{m}}$
and that $\pi(A_{m})\subseteq\mathbb{Z}$ is a symmetric interval around $0$,
say $\pi(A_{m})=[-N_{m},N_{m}]$, such that $\\{N_{m}\\}_{m}$ are increasing
positive integers, and that whenever $m\geq p_{n}$ we have

$\left(\pi_{*}\alpha_{m}\right)^{*q}\left(\left[-(n-1)N_{m-1},(n-1)N_{m-1}\right]\right)<\varepsilon_{n},$
(3)

for every $1\leq q\leq n$. In other words, we guarantee that for every $m\geq
p_{n}$, the first $n$ steps of the projected random walk on $\mathbb{Z}$
(whose increments distribute according to $\pi_{*}\alpha_{m}$) stay out of the
set $\left[-(n-1)N_{m-1},(n-1)N_{m-1}\right]$ with high probability. The
measure we are looking for is $\mu\coloneqq\sum_{m\geq 1}t_{m}\alpha_{m}.$

Indeed, $\mu$ is a symmetric non-degenerate measure on $G$, which has a
trivial Poisson boundary, just as in the proof [KV83, Theorem 4.3]. Denote
$\nu=\pi_{*}\mu$ the projection of $\mu$ to $\mathbb{Z}$, and let us prove
that $\nu$ induces a transient random walk on $\mathbb{Z}$.

By construction, we have $\nu=\sum_{m\geq 1}t_{m}\beta_{m},$ where
$\beta_{m}=\pi_{*}\alpha_{m}$. We will prove that for every $n\geq 1$ one has
$\nu^{*n}(0)\leq 2\varepsilon_{n},$ and since $\\{\varepsilon_{n}\\}_{n\geq
1}$ is summable, this will imply that the $\nu$-random walk on $\mathbb{Z}$ is
transient.

Note that

$\nu^{*n}=\sum_{\mathbf{k}}t_{k_{1}}\cdots
t_{k_{n}}\beta_{k_{1}}*\cdots*\beta_{k_{n}},$

where $\mathbf{k}=(k_{1},\ldots,k_{n})$ ranges over all possible multi-
indices. We write $\nu^{*n}=\gamma_{1}+\gamma_{2}$, where

$\gamma_{1}=\sum_{|\mathbf{k}|<p_{n}}t_{k_{1}}\cdots
t_{k_{n}}\beta_{k_{1}}*\cdots*\beta_{k_{n}},\text{ for
}|\mathbf{k}|=\max_{1\leq i\leq n}k_{i},$

and $\gamma_{2}=\nu^{*n}-\gamma_{1}.$

First, note that our choice of $p_{n}$ guarantees that

$\gamma_{1}(0)\leq\sum_{|\mathbf{k}|<p_{n}}t_{k_{1}}\cdots
t_{k_{n}}=(t_{1}+\cdots+t_{p_{n}-1})^{n}\leq\varepsilon_{n}.$

Now let us bound the value of $\gamma_{2}(0)$. Fix a multi-index $\mathbf{k}$
such that $|\mathbf{k}|\geq p_{n}$ and consider an index $j$ such that $k_{j}$
is the largest entry. Since $\mathbb{Z}$ is abelian, the convolution of
measures is an abelian operation, and we can write
$\beta_{k_{1}}*\cdots*\beta_{k_{n}}=\beta_{k_{j}}^{*q}*\theta,$ where $q\geq
1$ and $\theta$ is an $(n-q)$-th convolution of $\beta_{i}$’s with $i<k_{j}$,
so that it satisfies

$\mathrm{supp}(\theta)\subseteq[-(n-1)N_{k_{j}-1},(n-1)N_{k_{j}-1}].$

With this, we get

$\displaystyle\gamma_{2}(0)$
$\displaystyle=\sum_{x\in\mathbb{Z}}\beta_{k_{j}}^{*q}(x)\theta(-x)$
$\displaystyle=\sum_{|x|\leq(n-1)N_{k_{j}-1}}\beta_{k_{j}}^{*q}(x)\theta(-x)$
$\displaystyle\leq\sum_{|x|\leq(n-1)N_{k_{j}-1}}\beta_{k_{j}}^{*q}(x)$
$\displaystyle=\beta_{k_{j}}^{*q}\left(\left[-(n-1)N_{k_{j}-1},(n-1)N_{k_{j}-1}\right]\right)$
$\displaystyle\leq\varepsilon_{n},$

where we used the fact that $\beta_{k_{j}}$ satisfies Equation (3), with
$k_{j}\geq p_{n}$.

We conclude that $\nu^{*n}(0)=\gamma_{1}(0)+\gamma_{2}(0)\leq
2\varepsilon_{n},$ which finishes the proof. ∎

If we weaken the hypothesis
$\mathbb{E}\left(|\mathrm{supp}(\sigma_{1})|\right)<\infty$ from Lemma 4.5 it
is possible that the permutation coordinate never stabilizes. Indeed, with
ideas similar to an example of [Kai83], we obtain the following.

######  Proposition 4.9.

The group ${\mathsf{Shuffler}}(\mathbb{Z})$ admits probability measures $\mu$
with an infinite first moment and a finite $(1-\varepsilon)$-moment, for every
$0<\varepsilon<1$, that induce a transient random walk on $\mathbb{Z}$ and for
which the permutation coordinate of the $\mu$-random walk does not stabilize.
Such measures can be chosen to satisfy
$\mathbb{E}(|\mathrm{supp}(\sigma_{1})|)=\infty$ and
$\mathbb{E}(|\mathrm{supp}(\sigma_{1})|^{1-\varepsilon})<\infty$ for every
$0<\varepsilon<1$.

###### Proof.

For each $n\geq 1$, denote by $r_{n}:\mathbb{Z}\to\mathbb{Z}$ the permutation

$r_{n}(x)=\left\\{\begin{aligned} x+1,&\text{ if }0\leq x<n-1,\\\ 0,&\text{ if
}x=n-1,\text{ and}\\\ x,&\text{ otherwise.}\end{aligned}\right.$

We define the measure $\mu$ on ${\mathsf{Shuffler}}(\mathbb{Z})$ as follows.
Let

$\mu((\mathsf{id},1))=1/8,\ \mu((\mathsf{id},-1))=3/8,$

and

$\mu((r_{n},0))=\frac{1}{2n(n+1)},\ \text{ for }n\geq 1.$

Note that $\sum_{n\geq 1}\frac{1}{n(n+1)}=1$, so that $\mu$ is indeed a
probability measure. Also note that $|\mathrm{supp}(r_{n})|=n$. From this, the
fact that the harmonic series $\sum_{n\geq 1}\frac{1}{n}$ diverges implies
that $\mathbb{E}(|\mathrm{supp}(\sigma_{1})|)$ is infinite. Moreover, since
$\|(r_{n},0)\|_{S_{\mathrm{std}}}\geq|\mathrm{supp}(r_{n})|$, we also have
that $\mu$ has an infinite first moment. On the other hand, for every
$\varepsilon>0$ the series $\sum_{n\geq 1}\frac{n^{1-\varepsilon}}{n(n+1)}$ is
convergent and thus $\mathbb{E}(|\mathrm{supp}(\sigma_{1})|^{1-\varepsilon})$
is finite. The element $r_{n}$ has word length at most $3n$ (since it can be
expressed as the product of at most $n$ transpositions together with $2n$
movements in the $\mathbb{Z}$ coordinate), and hence

$\sum_{n\geq
1}\frac{\|(r_{n},0)\|_{S_{\mathrm{std}}}^{1-\varepsilon}}{n(n+1)}\leq
3^{1-\varepsilon}\sum_{n\geq 1}\frac{n^{1-\varepsilon}}{n(n+1)},$

which is finite. Hence, $\mu$ has a finite $(1-\varepsilon)$-moment.

Let us show that the value $F_{n}(0)$, $n\geq 1$, almost surely changes
infinitely often. By definition of the group operation and the $\mu$-random
walk, we can write $F_{n}=F_{n-1}\circ(S_{n}\cdot\sigma_{n})$. Hence,
$F_{n}(0)\neq F_{n-1}(0)$ if and only if $S_{n}\cdot\sigma_{n}(0)\neq 0$,
which can be rewritten as $\sigma_{n}(-S_{n})\neq-S_{n}$, by using the
definition of the action of $\mathbb{Z}$ on $\mathrm{FSym}(\mathbb{Z})$ (here
we use an additive notation for the group operation on $\mathbb{Z}$).

The induced random walk on $\mathbb{Z}$ is drifted to the negative numbers,
and hence almost surely $S_{n}\xrightarrow[n\to\infty]{}-\infty$. Also, at
time $n$ the projection to $\mathbb{Z}$ satisfies $S_{n}\geq-n$, since the
distribution of the increments of the induced random walk on $\mathbb{Z}$ is
supported on $\\{1,-1\\}$. Consider the event $A_{n}=\\{\sigma_{n}(i)\neq
i\text{ for }0\leq i<n\\}$, and note that

$\mathbb{P}(A_{n})\geq\sum_{k>n}\mathbb{P}(\sigma_{n}=r_{k})=\sum_{k>n}\mu((r_{k},0))=\sum_{k>n}\frac{1}{2k(k+1)}=\frac{1}{2(n+1)}.$

Since the sequence of events $\\{A_{n}\\}_{n\geq 1}$ is independent and the
series $\sum_{n}\mathbb{P}(A_{n})$ diverges, the Borel-Cantelli Lemma implies
that almost surely infinitely many of these events occur. In consequence, the
value of the permutation coordinate at $0$ changes infinitely often. ∎

In Kaimanovich’s example mentioned above, the difference between the states of
two adjacent lamps does stabilize [Kai83], so that the Poisson boundary is
non-trivial. A similar example is described by Lyons and Peres after the proof
of Theorem 5.1 in [LP21]. Examples of random walks on
$\mathbb{Z}/2\mathbb{Z}\wr\mathbb{Z}^{d}$, $d\geq 1$, which have a non-trivial
Poisson boundary but for which there is no functional defined by a finite set
that stabilizes along infinite trajectories are given in [Ers11, Section 6].

##  5\. Proof of the main theorem

Let us consider a finitely generated group $H$. Let $\mu$ be a probability
measure on ${\mathsf{Shuffler}}(H)$ with a finite first moment and a transient
projection to $H$. In this case, Lemma 1.1 implies that the permutation
coordinate $(F_{n})_{n}$ of the $\mu$-random walk stabilizes to a limit
injective function $F_{\infty}:H\to H$. As a result, the space
$\mathcal{F}(H)\coloneqq\\{f:H\to H\mid f\text{ is injective}\\}$ has the
structure of a measure space $(\mathcal{F}(H),\lambda)$, where $\lambda$ is
the _hitting measure_ and satisfies for any $A\subseteq\mathcal{F}(H)$
measurable, $\lambda(A)\coloneqq\mathbb{P}(F_{\infty}\in A).$ Alternatively,
$\lambda$ is the push-forward of $\mathbb{P}$ through the map
${\mathsf{Shuffler}}(H)^{\infty}\to\mathcal{F}(H)$ that associates with every
sample path of the $\mu$-random walk on ${\mathsf{Shuffler}}(H)$ the
associated limit function $F_{\infty}$ of the permutation coordinate. Note
that this map is shift-invariant, which implies that the measure $\lambda$ is
$\mu$-stationary.

The space $(\mathcal{F}(H),\lambda)$ is thus a $\mu$-boundary, as described in
Subsection 3.2. That is, it is a quotient of the Poisson boundary. In this
section, we prove Theorem 1.2, which states that for $H=\mathbb{Z}$, the
$\mu$-boundary $(\mathcal{F}(\mathbb{Z}),\lambda)$ actually coincides with the
Poisson boundary of the random walk $({\mathsf{Shuffler}}(\mathbb{Z}),\mu)$.

The proof of Theorem 1.2 uses Kaimanovich’s Conditional Entropy Criterion
(Theorem 3.1). The main idea is that conditioned on the limit function to
which the permutation coordinate converges, for every $\varepsilon>0$ and any
large enough $n$ we can find a finite subset
$Q_{n}\subseteq{\mathsf{Shuffler}}(\mathbb{Z})$ with $|Q_{n}|<\exp(\varepsilon
n)$, and such that $(F_{n},S_{n})\in Q_{n}$ with some fixed positive
probability.

The fact that $\mu$ has a finite first moment implies that the projection
$\mu_{\mathbb{Z}}$ of $\mu$ to $\mathbb{Z}$ also does. Since
$\mu_{\mathbb{Z}}$ induces a transient random walk, it holds that the
$\mu_{\mathbb{Z}}$-random walk on $\mathbb{Z}$ has non-zero drift
$\sum_{x\in\mathbb{Z}}x\mu_{\mathbb{Z}}(x)$. The law of large numbers then
allows us to confine the position coordinate $S_{n}$ within an interval
$I_{n}$ of length $2\varepsilon n$ and to estimate the values of the
permutation coordinate outside this interval. However, this is not enough for
our purposes, since a rough estimate for the number of values that the
permutation coordinate can take inside $I_{n}$ is $(2\varepsilon n)!$, which
leads to sets $Q_{n}$ that have an exponential size. To overcome this
difficulty, we look at the possible values for the displacement of $F_{n}$.
Recall that the displacement of $\sigma\in{\mathsf{Shuffler}}(\mathbb{Z})$ is
defined as $\mathrm{Disp}(\sigma)=\sum_{i\in\mathbb{Z}}|\sigma(i)-i|$
(Definition 2.2). The first moment hypothesis gives us control over the
possible values for the displacement associated with the permutation
increments that modify the values in the interval $I_{n}$, which in turn
reduces the previously mentioned estimate into a subexponential one.

###  5.1. The proof

We first state two preliminary lemmas that follow from the hypothesis of $\mu$
having a finite first moment and the Strong Law of Large Numbers [Fel68,
Section VIII.4]. Then, we proceed with the proof.

######  Lemma 5.1.

Consider a probability measure $\mu$ on ${\mathsf{Shuffler}}(\mathbb{Z})$ with
a finite first moment. Then there exists a constant $D>0$ such that for every
$\varepsilon>0$ and almost every sequence of i.i.d. increments
$\\{(\sigma_{k},X_{k})\\}_{k\geq 1}$ there exists $N\geq 1$ such that for
every $n\geq N$ one has

  1. (1)

$|X_{n}|\leq\varepsilon n$,

  2. (2)

$\sigma_{n}\in\mathrm{Sym}\left(\left[-\varepsilon n,\varepsilon
n\right]\right)$, and

  3. (3)

$\displaystyle\sum_{k=n-\varepsilon
n}^{n}\mathrm{Disp}(\sigma_{k})<D\varepsilon n$.

###### Proof.

We will use the Borel-Cantelli Lemma for the first two items. We see that

$\displaystyle\sum_{n\geq 1}\mathbb{P}\left(|X_{n}|\geq\varepsilon n\right)$
$\displaystyle=\sum_{n\geq
1}\sum_{(F,x)\in{\mathsf{Shuffler}}(\mathbb{Z})}\mathds{1}_{\left\\{|x|\geq\varepsilon
n\right\\}}\mu(F,x)$
$\displaystyle=\sum_{(F,x)\in{\mathsf{Shuffler}}(\mathbb{Z})}\frac{1}{\varepsilon}|x|\mu(F,x)$
$\displaystyle\leq\frac{1}{\varepsilon}\sum_{(F,x)\in{\mathsf{Shuffler}}(\mathbb{Z})}\|(F,x)\|_{S_{\mathrm{std}}}\mu(F,x)<+\infty.$

Similarly, we have

$\displaystyle\sum_{n\geq
1}\mathbb{P}\left(\mathrm{supp}(\sigma_{n})\nsubseteq\left[-\varepsilon
n,\varepsilon n\right]\right)$ $\displaystyle=\sum_{n\geq
1}\sum_{(F,x)\in{\mathsf{Shuffler}}(\mathbb{Z})}\mathds{1}_{\left\\{\mathrm{supp}(F)\nsubseteq\left[-\varepsilon
n,\varepsilon n\right]\right\\}}\mu(F,x)$ $\displaystyle\leq\sum_{n\geq
1}\sum_{(F,x)\in{\mathsf{Shuffler}}(\mathbb{Z})}\mathds{1}_{\left\\{n\leq\frac{1}{\varepsilon}\max\\{|y|:\
y\in\mathrm{supp}(F)\\}\right\\}}\mu(F,x)$
$\displaystyle\leq\frac{1}{\varepsilon}\sum_{(F,x)\in{\mathsf{Shuffler}}(\mathbb{Z})}\|(F,x)\|_{S_{\mathrm{std}}}\mu(F,x)<+\infty,$

Since both sums are finite, the Borel-Cantelli Lemma implies that almost
surely these events occur finitely many times, and thus neither of them
happens for $n$ sufficiently large.

The third item follows from the Strong Law of Large Numbers, since the
sequence of random variables $\\{\mathrm{Disp}(\sigma_{k})\\}_{k\geq 1}$ are
i.i.d. of finite first moment. Indeed, using Lemma 2.3, we have

$\mathbb{E}(\mathrm{Disp}(\sigma_{1}))\leq
2\mathbb{E}(\|(\sigma_{1},X_{1})\|_{S_{\mathrm{std}}})<+\infty.$

∎

The next lemma is a direct consequence of the Strong Law of Large Numbers.

######  Lemma 5.2.

Fix a probability measure $\nu$ on $\mathbb{Z}$ with finite first moment and
positive drift. Denote by $\\{S_{n}\\}_{n\geq 0}$ the associated $\nu$-random
walk on $\mathbb{Z}$. Then there exists a constant $C_{1}>0$ such that for
every $\varepsilon>0$, almost surely there exists $N\geq 1$ such that for
$n\geq N$ we have

$C_{1}n-\varepsilon n\leq S_{n}\leq C_{1}n+\varepsilon n.$

Let us now proceed with the proof of the main theorem.

###### Proof of Theorem 1.2.

Since the projection of $\mu$ to $\mathbb{Z}$ is transient and has a finite
first moment, its drift $\mathbb{E}(X_{1})$ is non-zero, and we lose no
generality if we furthermore suppose that it is positive. We will assume this
throughout the rest of the proof.

Denote by $F_{\infty}$ the random variable defined as the limit of the
permutation component $\\{F_{n}\\}_{n\geq 0}$ of the $\mu$-random walk on
${\mathsf{Shuffler}}(\mathbb{Z})$, which is almost surely well-defined thanks
to Lemma 1.1. To prove the theorem, it suffices to check the hypotheses of
Theorem 3.1 for the boundary of limit functions $F_{\infty}$.

Fix an arbitrary $\varepsilon>0$. Thanks to Lemmas 5.1 and 5.2, there exist
constants $C_{1},D>0$ and $N\geq 1$ large enough so that for every $n\geq N$
we have that

$C_{1}n-\varepsilon n\leq S_{n}\leq C_{1}n+\varepsilon n,$

and that the increments of the $\mu$-random walk satisfy

$|X_{n}|<\varepsilon n,\text{ and }\sigma_{n}\in\mathrm{FSym}([-\varepsilon
n,\varepsilon n]),$

together with

$\displaystyle\sum_{k=n-\tilde{\varepsilon}n}^{n}\mathrm{Disp}(\sigma_{k})<D\tilde{\varepsilon}n,$

where $\tilde{\varepsilon}=\frac{4\varepsilon}{C_{1}+2\varepsilon}$. This
choice of $\widetilde{\varepsilon}$ is to simplify the computations below.

The above guarantees that $F_{n}(y)=y$ for every $y>(C_{1}+2\varepsilon)n$.
Indeed, the maximum value that the projection to $\mathbb{Z}$ could have
visited is $C_{1}+\varepsilon n$, and since the permutation component of the
increments has a range of at most $\varepsilon n$, there have been no
modifications of the permutation component of the random walk beyond
$C_{1}+\varepsilon n+\varepsilon n=(C_{1}+2\varepsilon)n.$

Similarly, for every instant after $n$ we know that the projection to
$\mathbb{Z}$ will not visit any value smaller than $(C_{1}-\varepsilon)n$, so
that for every $y<(C_{1}-2\varepsilon)n$ the value $F_{n}(y)$ is already fixed
to its limit $F_{\infty}(y)$. Thus, we know the exact value of $F_{n}(y)$ for
every $y\in\mathbb{Z}$ such that $|y-C_{1}n|>2\varepsilon n$.

We now estimate the possible number of values that $F_{n}$ can take in the
interval $[(C_{1}-2\varepsilon)n,(C_{1}+2\varepsilon)n]$. To do so, we remark
that if $k_{0}$ is the first moment that the permutation component of the
random walk is not trivial on this interval, then

$\displaystyle\sum_{i=(C_{1}-2\varepsilon)n}^{(C_{1}+2\varepsilon)n}|F_{n}(i)-i|\leq\sum_{k=k_{0}}^{n}\mathrm{Disp}(\sigma_{k}).$
(4)

For $n$ large enough, the smallest possible value for $k_{0}$ is
$\frac{C_{1}-2\varepsilon}{C_{1}+2\varepsilon}n$. Indeed, the maximum value of
$S_{k}$ is $C_{1}k+\varepsilon k$ and the support of the permutation component
increments allows for an extra $\varepsilon k$, so that we get the inequality

$(C_{1}+2\varepsilon)k_{0}\geq(C_{1}-2\varepsilon)n.$

Now note that

$n-\frac{C_{1}-2\varepsilon}{C_{1}+2\varepsilon}n=\frac{4\varepsilon}{C_{1}+2\varepsilon}n,$

and recall that we defined
$\tilde{\varepsilon}=\frac{4\varepsilon}{C_{1}+2\varepsilon}$, so that we have

$\sum_{k=n-\tilde{\varepsilon}n}^{n}\mathrm{Disp}(\sigma_{k})<D\tilde{\varepsilon}n=\frac{4D}{C_{1}+2\varepsilon}\varepsilon
n.$

Denote $D^{\prime}=\frac{4D}{C_{1}+2\varepsilon}$. Thanks to Equation (4), we
can interpret the above as saying that the permutation $F_{n}$ must assign a
non-negative value $d_{i}\coloneqq|F_{n}(i)-i|$ to each element
$i\in[(C_{1}-2\varepsilon)n,(C_{1}+2\varepsilon)n]$ such that

$\displaystyle\sum_{i=(C_{1}-2\varepsilon)n}^{(C_{1}+2\varepsilon)n}d_{i}<D^{\prime}\varepsilon
n.$

The number of ways to do this is the same as the number of ways of
distributing $D^{\prime}\varepsilon n$ identical balls into $4\varepsilon n+1$
distinguishable boxes, together with a factor of $2^{4\varepsilon n+1}$ which
accounts for the fact that for the same value of $d_{i}$ there are at most two
choices of $F_{n}(i)$ (depending on whether $F_{n}(i)\geq i$ or $F_{n}(i)<i$).
This gives an upper bound of

$2^{4\varepsilon n+1}\cdot{(4+D^{\prime})\varepsilon n\choose
D^{\prime}\varepsilon n}$

for the possible values of the function $F_{n}$.

To use Kaimanovich’s criterion, we define
$Q_{n}\subseteq{\mathsf{Shuffler}}(\mathbb{Z})$ to be the set of elements of
the form $(F,x)$ where $(C_{1}-\varepsilon)n\leq x\leq(C_{1}+\varepsilon)n$
and where $F$ is a permutation as described above. The random set $Q_{n}$ is
measurable with respect to $\sigma(F_{\infty})$. As a consequence of the above
estimates, we have that $(F_{n},S_{n})\in Q_{n}$ almost surely, for $n$ large
enough, and that

$|Q_{n}|\leq(4\varepsilon n+1)2^{4\varepsilon
n+1}\cdot{(4+D^{\prime})\varepsilon n\choose D^{\prime}\varepsilon n}.$

Finally, thanks to Stirling’s approximation [Fel68, Section II.9], we have

$\displaystyle\limsup_{n\to\infty}\frac{1}{n}\log|Q_{n}|$ $\displaystyle\leq
4\varepsilon\log
2+\limsup_{n\to\infty}\frac{1}{n}\log{(4+D^{\prime})\varepsilon n\choose
D^{\prime}\varepsilon n}$ $\displaystyle\leq 4\varepsilon\log
2+4\varepsilon\log\left(\frac{4+D^{\prime}}{4\varepsilon}\right)+D^{\prime}\varepsilon\log\left(\frac{4+D^{\prime}}{D^{\prime}}\right)$
$\displaystyle\leq C_{2}\varepsilon,$

for some constant $C_{2}>0$. With this, we have checked the hypotheses of
Theorem 3.1 and hence finished the proof. ∎

##  6\. Boundary triviality for recurrent projections to the base group

Theorem 1.2 describes the Poisson boundary of random walks on
${\mathsf{Shuffler}}(\mathbb{Z})$ with a finite first moment and a transient
projection to $\mathbb{Z}$. On the other hand, the situation is more delicate
when the projection to $\mathbb{Z}$ is recurrent since the group
$\mathrm{FSym}(\mathbb{Z})$ admits measures with a non-trivial Poisson
boundary [Kai83]. In this section, we prove that the Poisson boundary is
trivial for finitary measures on ${\mathsf{Shuffler}}(\mathbb{Z})$ or
${\mathsf{Shuffler}}(\mathbb{Z}^{2})$ that induce a recurrent random walk on
the base group.

We first show the result for $H=\mathbb{Z}$, following similar ideas to [KV83,
Proposition 6.2].

######  Proposition 6.1.

Consider $\mu$ a finitely supported probability measure on
${\mathsf{Shuffler}}(\mathbb{Z})$ such that its projection to $\mathbb{Z}$
induces a recurrent random walk. Then the Poisson boundary of
$({\mathsf{Shuffler}}(\mathbb{Z}),\mu)$ is trivial.

###### Proof.

Denote by $\nu$ the projection of $\mu$ to $\mathbb{Z}$, which has a zero mean
and is finitely supported. Consider the $\mu$-random walk
$\\{(F_{n},S_{n})\\}_{n\geq 0}$ on ${\mathsf{Shuffler}}(\mathbb{Z})$. We first
recall that Kolmogorov’s Maximal Inequality [Fel68, Section IX.7] states that
for any $\lambda>0$, we have

$\mathbb{P}\left(\max_{1\leq k\leq n}|S_{k}|\geq\lambda\right)\leq
n\sigma^{2}/\lambda^{2},$

where $\sigma^{2}$ is the variance of $\nu$. In particular for
$\lambda=n^{3/4}$, we get

$\mathbb{P}\left(\max_{1\leq k\leq n}|S_{k}|<n^{3/4}\right)\geq
1-\frac{\sigma^{2}}{n^{1/2}}.$

Thus, with probability at least $1-\sigma^{2}/n^{1/2}$, the random walk at
time $n$ belongs to the set

$A_{n}=\left\\{(f,x)\in G\mid|x|\leq n^{3/4},\
\mathrm{supp}(f)\subseteq[-n^{3/4}-M,n^{3/4}+M]\right\\},$

where $M=\max\left\\{C\geq 0\mid\text{for every
}(f,x)\in\mathrm{supp}(\mu)\text{ and }|y|>C,\ f(y)=y\right\\}$ is the size of
the largest support of functions $f$ that participate in the support of $\mu$.

The size of the set $A_{n}$ is subexponential. Indeed, we have

$\displaystyle\frac{1}{n}\log|A_{n}|\leq\frac{1}{n}\log\left((2n^{3/4}+1)\cdot(2n^{3/4}+1+M)!\right),$

which converges to $0$. This follows by applying Stirling’s approximation to
bound from above the term $\log((2n^{3/4}+1+M)!)$. We can thus apply Theorem
3.1 with the trivial boundary since the sets $A_{n}$ are deterministic and we
have

$\mathbb{P}\left((F_{n},S_{n})\in A_{n}\right)\geq\mathbb{P}\left(\max_{1\leq
k\leq n}|S_{k}|<n^{3/4}\right)\geq 1-\frac{\sigma^{2}}{n^{1/2}}>1/2,$

for any $n$ large enough. ∎

In order to prove the analogous result for $H=\mathbb{Z}^{2}$, we need more
detailed calculations. Indeed, in the proof of Proposition 6.1 we argued that
the projection of the random walk to $\mathbb{Z}$ at time $n$ stayed inside an
interval of length of order $n^{3/4}$ with some positive probability. Then a
rough estimate for the total number of permutations in this interval gives
rise to a subset of ${\mathsf{Shuffler}}(\mathbb{Z})$ whose size is of order
$(n^{3/4})!$. This grows subexponentially and hence we can apply Theorem 3.1.
In the case of $\mathbb{Z}^{2}$, we can similarly argue that with a fixed
positive probability, the projection of the random walk to $\mathbb{Z}^{2}$ at
time $n$ has not visited the outside of a ball of radius $C_{1}n^{1/2}$, for
some constant $C_{1}>0$. However, since the base group now has quadratic
growth, a rough estimate for the number of permutations gives an exponential
number of possibilities, and so we cannot apply Theorem 3.1. We go past these
complications by giving more detailed estimates for the range of the projected
random walk to $\mathbb{Z}^{2}$, which is $O(n/\log(n))$, and by looking at
the displacement of the permutation coordinate increments.

######  Proposition 6.2.

Consider $\mu$ a finitely supported probability measure on
${\mathsf{Shuffler}}(\mathbb{Z}^{2})$ such that its projection to
$\mathbb{Z}^{2}$ induces a recurrent random walk. Then the Poisson boundary of
$({\mathsf{Shuffler}}(\mathbb{Z}^{2}),\mu)$ is trivial.

###### Proof.

By using Kolmogorov’s maximal inequality on both coordinates of
$\mathbb{Z}^{2}$, we see that for a large enough constant $C_{1}>0$ we have

$\mathbb{P}\left(\max_{1\leq k\leq n}\|S_{k}\|\leq C_{1}n^{1/2}\right)>1/2$

for all $n\geq 1$, where $\|\cdot\|$ denotes the $L_{1}$ norm on
$\mathbb{Z}^{2}$. That is, $\|(x_{1},x_{2})\|=|x_{1}|+|x_{2}|$, for
$(x_{1},x_{2})\in\mathbb{Z}^{2}$.

We need to estimate the $n$-th instant $(F_{n},S_{n})$ of the random walk. Let
us denote by $R_{n}\coloneqq\left|\\{S_{0},S_{1},\ldots,S_{n}\\}\right|$ the
range of the induced random walk on $\mathbb{Z}^{2}$. In other words, $R_{n}$
is the number of distinct elements of $\mathbb{Z}^{2}$ visited up to time $n$.
Since we assume that $\mu$ has finite support, the following limit

$\lim_{n\to\infty}\frac{R_{n}}{n/\log(n)}$

exists almost surely and is positive. This was first proven for the simple
random walk on $\mathbb{Z}^{2}$ in [DE51]. The same arguments in that paper
prove that for any finitely supported $\mu$ such that the induced random walk
on $\mathbb{Z}^{2}$ is recurrent, one has
$\mathbb{E}(R_{n})=C\frac{n}{\log(n)}+o\left(\frac{n}{\log(n)}\right)$ for a
constant $C>0$. In addition, it is proven in [JP72] that for $\mu$ as above,
the strong law of large numbers $\lim_{n\to\infty}\frac{R_{n}}{E(R_{n})}=1$
holds almost surely. The combination of both results implies the statement
above. In particular for our proof, the above implies that there exists a
constant $C_{2}>0$ such that almost surely for every large enough $n$ we have
$R_{n}<C_{2}\frac{n}{log(n)}$.

With this, the $n$-th instant of the random walk is determined by choosing at
most $C_{2}\frac{n}{\log(n)}$ elements of $\mathbb{Z}^{2}$ to visit inside the
ball of radius $C_{1}\sqrt{n}$, then choosing one of these elements to be the
final position $S_{n}$ of the random walk on $\mathbb{Z}^{2}$, and finally
choosing the values for the permutation coordinate $F_{n}$. The first two
terms above give a factor of

${(C_{1}\sqrt{n}+1)^{2}\choose C_{2}\frac{n}{\log(n)}}\cdot
C_{2}\frac{n}{\log(n)},$

which grows subexponentially. Indeed, we note that both
$\frac{1}{n}\log(n/\log(n))=\frac{1}{n}\log(n)-\frac{1}{n}\log\log n$, and

$\frac{1}{n}\log{(C_{1}\sqrt{n}+1)^{2}\choose C_{2}\frac{n}{\log(n)}}$

converge to $0$, as it follows from Stirling’s approximation.

In order to estimate the number of possible values for the permutation
coordinate $F_{n}$, we look at the displacement function. Note that we have
$\sum_{x\in\mathbb{Z}^{2}}\|x-F_{n}(x)\|\leq C_{3}n,$ for some constant
$C_{3}>0$. Indeed, since $\mu$ has finite support, each increment will map
each element to its image in a uniformly bounded neighborhood, and so the
total displacement at every step is bounded by a fixed constant.

With the above, we can associate to the permutation $F_{n}(x)$ values
$d_{x}\geq 0$, for each $x$ in the support of size $C_{2}\frac{n}{\log(n)}$,
whose sum must be at most $C_{3}n$. The total number of ways of assigning
these numbers to a fixed support is given by

${C_{3}n+C_{2}\frac{n}{\log(n)}-1\choose C_{3}n}.$

Suppose that we have fixed a support of size $C_{2}\frac{n}{\log(n)}$ as well
as the displacements of each element $\\{d_{x}\\}_{x}$. We remark that for
every element $x$, its image $F_{n}(x)$ can be any element that satisfies
$\|x-F_{n}(x)\|=d_{x}$. For a fixed value of $d_{x}$ there are $2d_{x}+1$ such
elements, and hence the total number of permutations for this fixed support
and displacement is bounded above by
$\prod_{i=1}^{C_{2}\frac{n}{\log(n)}}(2d_{i}+1).$ Since we have the constraint
$\sum_{i=1}^{C_{2}\frac{n}{\log(n)}}d_{i}=C_{3}n$, the above product is
maximized when all the values $2d_{i}+1$ are equal, and hence we have the
upper bound

$\left(\frac{2C_{3}n+C_{2}\frac{n}{\log(n)}}{C_{2}\frac{n}{\log(n)}}\right)^{C_{2}\frac{n}{\log(n)}}.$

This also grows subexponentially.

In conclusion, our analysis shows that with a probability of at least $1/2$,
the $n$-th instant $(F_{n},S_{n})$ of the random walk on
${\mathsf{Shuffler}}(\mathbb{Z}^{2})$ belongs to a set $A_{n}$ of size bounded
above by

${(C_{1}\sqrt{n}+1)^{2}\choose\frac{C_{2}n}{\log(n)}}\cdot\frac{C_{2}n}{\log(n)}\cdot{C_{3}n+\frac{C_{2}n}{\log(n)}-1\choose
C_{3}n}\cdot\left(\frac{2C_{3}n+\frac{C_{2}n}{\log(n)}}{\frac{C_{2}n}{\log(n)}}\right)^{\frac{C_{2}n}{\log(n)}},$

which grows subexponentially. We can thus apply Theorem 3.1 to conclude that
the Poisson boundary is trivial. ∎

## References

  * [Anc87] Alano Ancona.  Negatively curved manifolds, elliptic operators, and the Martin boundary.  Ann. of Math. (2), 125(3):495–536, 1987.
  * [Ave72] André Avez.  Entropie des groupes de type fini.  C. R. Acad. Sci. Paris Sér. A-B, 275:A1363–A1366, 1972.
  * [Ave74] André Avez.  Théorème de Choquet-Deny pour les groupes à croissance non exponentielle.  C. R. Acad. Sci. Paris Sér. A, 279:25–28, 1974.
  * [Bas72] H. Bass.  The degree of polynomial growth of finitely generated nilpotent groups.  Proc. London Math. Soc. (3), 25:603–614, 1972.
  * [BF64] David Blackwell and David Freedman.  The tail $\sigma$-field of a Markov chain and a theorem of Orey.  Ann. Math. Statist., 35:1291–1295, 1964.
  * [BGTT22] Édouard Bonnet, Colin Geniet, Romain Tessera, and Stéphan Thomassé.  Twin-width VII: groups.  arXiv preprint arXiv:2204.12330, 2022.
  * [Bla55] David Blackwell.  On transient Markov processes with a countable number of states and stationary transition probabilities.  Ann. Math. Statist., 26:654–658, 1955.
  * [BTZ21] Jérémie Brieussel, Ryokichi Tanaka, and Tianyi Zheng.  Random walks on the discrete affine group.  Groups Geom. Dyn., 15(3):935–963, 2021.
  * [BZ19] Jérémie Brieussel and Tianyi Zheng.  Shalom’s property $H_{\rm FD}$ and extensions by $\mathbb{Z}$ of locally finite groups.  Israel J. Math., 230(1):45–70, 2019.
  * [BZ21] Jérémie Brieussel and Tianyi Zheng.  Speed of random walks, isoperimetry and compression of finitely generated groups.  Ann. of Math. (2), 193(1):1–105, 2021.
  * [CD60] Gustave Choquet and Jacques Deny.  Sur l’équation de convolution $\mu=\mu\ast\sigma$.  C. R. Acad. Sci. Paris, 250:799–801, 1960.
  * [CFFT22] Kunal Chawla, Behrang Forghani, Joshua Frisch, and Giulio Tiozzo.  The Poisson boundary of hyperbolic groups without moment conditions.  arXiv preprint arXiv:2209.02114, 2022.
  * [Cho80] Ching Chou.  Elementary amenable groups.  Illinois J. Math., 24(3):396–407, 1980.
  * [DE51] A. Dvoretzky and P. Erdős.  Some problems on random walk in space.  In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1950, pages 353–367. University of California Press, Berkeley-Los Angeles, Calif., 1951.
  * [Der75] Yves Derriennic.  Marche aléatoire sur le groupe libre et frontière de Martin.  Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 32(4):261–276, 1975.
  * [Der80] Yves Derriennic.  Quelques applications du théorème ergodique sous-additif.  In Conference on Random Walks (Kleebach, 1979) (French), volume 74 of Astérisque, pages 183–201, 4. Soc. Math. France, Paris, 1980.
  * [dlH00] Pierre de la Harpe.  Topics in geometric group theory.  Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 2000.
  * [DM61] E. B. Dynkin and M. B. Maljutov.  Random walk on groups with a finite number of generators.  Dokl. Akad. Nauk SSSR, 137:1042–1045, 1961.
  * [DSW60] J. L. Doob, J. L. Snell, and R. E. Williamson.  Application of boundary theory to sums of independent random variables.  Contributions to probability and statistics, 182:197, 1960.
  * [EK23] Anna Erschler and Vadim A. Kaimanovich.  Arboreal structures on groups and the associated boundaries.  Geometric and Functional Analysis, May 2023.
  * [Ers03] Anna Erschler.  On isoperimetric profiles of finitely generated groups.  Geom. Dedicata, 100:157–171, 2003.
  * [Ers10] Anna Erschler.  Poisson-Furstenberg boundaries, large-scale geometry and growth of groups.  In Proceedings of the International Congress of Mathematicians. Volume II, pages 681–704. Hindustan Book Agency, New Delhi, 2010.
  * [Ers11] Anna Erschler.  Poisson-Furstenberg boundary of random walks on wreath products and free metabelian groups.  Comment. Math. Helv., 86(1):113–143, 2011.
  * [ES06] Gábor Elek and Endre Szabó.  On sofic groups.  J. Group Theory, 9(2):161–171, 2006.
  * [EZ20] Anna Erschler and Tianyi Zheng.  Isoperimetric inequalities, shapes of Følner sets and groups with Shalom’s property $H_{FD}$.  Ann. Inst. Fourier (Grenoble), 70(4):1363–1402, 2020.
  * [Fel68] William Feller.  An introduction to probability theory and its applications. Vol. I.  John Wiley & Sons, Inc., New York-London-Sydney, third edition, 1968\.
  * [FH07] Benson Farb and Michael Handel.  Commensurations of Out(Fn).  Publ.math.IHES., 105(1):1–48, June 2007.
  * [FHTVF19] Joshua Frisch, Yair Hartman, Omer Tamuz, and Pooya Vahidi Ferdowsi.  Choquet-Deny groups and the infinite conjugacy class property.  Ann. of Math. (2), 190(1):307–320, 2019.
  * [FM98] Benson Farb and Howard Masur.  Superrigidity and mapping class groups.  Topology, 37(6):1169–1176, 1998.
  * [FS20] Ohad N Feldheim and Sasha Sodin.  The umpteen operator and its Lifshitz tails.  arXiv preprint arXiv:2010.01552, 2020.
  * [Fur71] Harry Furstenberg.  Random walks and discrete subgroups of Lie groups.  In Advances in Probability and Related Topics, Vol. 1, pages 1–63. Dekker, New York, 1971.
  * [GM12] François Gautero and Frédéric Mathéus.  Poisson boundary of groups acting on $\mathbb{R}$-trees.  Israel J. Math., 191(2):585–646, 2012.
  * [GM22] Maxime Gheysens and Nicolas Monod.  Between free and direct products of groups.  arXiv preprint arXiv:2201.03625, 2022.
  * [Gro81] Mikhael Gromov.  Groups of polynomial growth and expanding maps.  Inst. Hautes Études Sci. Publ. Math., (53):53–73, 1981.
  * [Gro08] Misha Gromov.  Entropy and isoperimetry for linear and non-linear group actions.  Groups Geom. Dyn., 2(4):499–593, 2008.
  * [GT24] Anthony Genevois and Romain Tessera.  Lamplighter-like geometry of groups, 2024.
  * [Gui73] Yves Guivarc’h.  Croissance polynomiale et périodes des fonctions harmoniques.  Bull. Soc. Math. France, 101:333–379, 1973.
  * [Hor16] Camille Horbez.  The Poisson boundary of $\mathrm{Out}(F_{N})$.  Duke Math. J., 165(2):341–369, 2016.
  * [HW20] Camille Horbez and Richard D. Wade.  Commensurations of subgroups of ${\rm Out}(F_{N})$.  Trans. Amer. Math. Soc., 373(4):2699–2742, 2020.
  * [HY18] Yair Hartman and Ariel Yadin.  Furstenberg entropy of intersectional invariant random subgroups.  Compos. Math., 154(10):2239–2265, 2018.
  * [IM99] Nikolai V. Ivanov and John D. McCarthy.  On injective homomorphisms between Teichmüller modular groups. I.  Invent. Math., 135(2):425–486, 1999.
  * [Jaw04] Wojciech Jaworski.  Countable amenable identity excluding groups.  Canad. Math. Bull., 47(2):215–228, 2004.
  * [JP72] Naresh C. Jain and William E. Pruitt.  The range of random walk.  In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. III: Probability theory, pages 31–50. Univ. California Press, Berkeley, Calif., 1972.
  * [Kai83] V. A. Kaimanovich.  Examples of nonabelian discrete groups with nontrivial exit boundary.  Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 123:167–184, 1983.  Differential geometry, Lie groups and mechanics, V.
  * [Kai91] Vadim A. Kaimanovich.  Poisson boundaries of random walks on discrete solvable groups.  In Probability measures on groups, X (Oberwolfach, 1990), pages 205–238. Plenum, New York, 1991.
  * [Kai92] Vadim A. Kaimanovich.  Measure-theoretic boundaries of Markov chains, $0$-$2$ laws and entropy.  In Harmonic analysis and discrete potential theory (Frascati, 1991), pages 145–180. Plenum, New York, 1992.
  * [Kai00] Vadim A. Kaimanovich.  The Poisson formula for groups with hyperbolic properties.  Ann. of Math. (2), 152(3):659–692, 2000.
  * [Kai01] Vadim A. Kaimanovich.  Poisson boundary of discrete groups, a survey.  2001\.
  * [KM96] Vadim A. Kaimanovich and Howard Masur.  The Poisson boundary of the mapping class group.  Invent. Math., 125(2):221–264, 1996.
  * [KV83] V. A. Kaimanovich and A. M. Vershik.  Random walks on discrete groups: boundary and entropy.  Ann. Probab., 11(3):457–490, 1983.
  * [KW07] Anders Karlsson and Wolfgang Woess.  The Poisson boundary of lamplighter random walks on trees.  Geom. Dedicata, 124:95–107, 2007.
  * [Led85] François Ledrappier.  Poisson boundaries of discrete groups of matrices.  Israel J. Math., 50(4):319–336, 1985.
  * [LP21] Russell Lyons and Yuval Peres.  Poisson boundaries of lamplighter groups: proof of the Kaimanovich-Vershik conjecture.  J. Eur. Math. Soc. (JEMS), 23(4):1133–1160, 2021.
  * [LZ98] Vladimir Ya. Lin and Mikhail Zaidenberg.  Liouville and Carathéodory coverings in Riemannian and complex geometry.  In Voronezh Winter Mathematical Schools, volume 184 of Amer. Math. Soc. Transl. Ser. 2, pages 111–130. Amer. Math. Soc., Providence, RI, 1998.
  * [Mar66] G. A. Margulis.  Positive harmonic functions on nilpotent groups.  Soviet Math. Dokl., 7:241–244, 1966.
  * [MT21] Joseph Maher and Giulio Tiozzo.  Random walks, WPD actions, and the Cremona group.  Proc. Lond. Math. Soc. (3), 123(2):153–202, 2021.
  * [OO13] Alexander Yu. Olshanskii and Denis V. Osin.  A quasi-isometric embedding theorem for groups.  Duke Math. J., 162(9):1621–1648, 2013.
  * [Pra76] Gopal Prasad.  Discrete subgroups isomorphic to lattices in semisimple Lie groups.  Amer. J. Math., 98(1):241–261, 1976.
  * [Ros81] Joseph Rosenblatt.  Ergodic and mixing random walks on locally compact groups.  Math. Ann., 257(1):31–42, 1981.
  * [Sav10] Ecaterina Sava.  A note on the Poisson boundary of lamplighter random walks.  Monatsh. Math., 159(4):379–396, 2010.
  * [Sel97] Z. Sela.  Structure and rigidity in (Gromov) hyperbolic groups and discrete groups in rank $1$ Lie groups. II.  Geom. Funct. Anal., 7(3):561–593, 1997.
  * [Stë83] A. M. Stëpin.  Approximability of groups and group actions.  Uspekhi Mat. Nauk, 38(6(234)):123–124, 1983.
  * [Var86] Nicholas Th. Varopoulos.  Théorie du potentiel sur des groupes et des variétés.  C. R. Acad. Sci. Paris Sér. I Math., 302(6):203–205, 1986.
  * [Ver73] A. M. Vershik.  Approximation in measure theory.  PhD thesis, 1973.  Doctor of Science Thesis, Leningrad Univ., Leningrad. (Russian).
  * [VG97] A. M. Vershik and E. I. Gordon.  Groups that are locally embeddable in the class of finite groups.  St. Petersbg. Math. J., 9(1):1, 1997.
  * [Was11] Bronlyn Wassink.  Subgroups of R. Thompson’s group $F$ that are isomorphic to $F$.  Groups Complex. Cryptol., 3(2):239–256, 2011.
  * [Woe89] Wolfgang Woess.  Boundaries of random walks on graphs and groups with infinitely many ends.  Israel J. Math., 68(3):271–301, 1989.
  * [Woe00] Wolfgang Woess.  Random walks on infinite graphs and groups, volume 138 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 2000.
  * [Yad09] Ariel Yadin.  Rate of escape of the mixer chain.  Electron. Commun. Probab., 14:347–357, 2009.
  * [Zhe22] Tianyi Zheng.  Asymptotic behaviors of random walks on countable groups.  Proceedings of the International Congress of Mathematicians, to appear, 2022.