Non-noise sensitivity for word hyperbolic groups

Let $\Gamma$ be a countable group, and $\mu$ be a probability measure on it. The main interest is in the case when $\Gamma$ is finitely generated with a finite set of generators $S$ and $\mu$ is the uniform distribution on $S$, but we will also consider the case when $\mu$ has an unbounded support. The $\mu$-random walk starting from the identity $o$ is defined by a product of independent sequence of increments with the identical distribution $\mu$. The noise sensitivity question concerning a $\mu$-random walk on $\Gamma$ asks the following: If we choose some real parameter $\rho\in(0,1)$ and replace each increment by an independent sample with the same law $\mu$ with probability $\rho$ or retain it with probability $1-\rho$, independently, then is the resulting random walk asymptotically independent of the original one?

More precisely, the $\mu$-random walk $\{w_{n}\}_{n=0}^{\infty}$ starting from $o$ is defined by $w_{n}=x_{1}\cdots x_{n}$ for an independent sequence $\{x_{n}\}_{n=1}^{\infty}$ with the identical distribution $\mu$ and $w_{0}:=o$. Let $\mu_{n}$ denote the distribution of $w_{n}$, which is the $n$-fold convolutions of $\mu$. For each $\rho\in[0,1]$, let us consider the $\pi^{\rho}$-random walk $\{(w_{n}^{(1)},w_{n}^{(2)})\}_{n=0}^{\infty}$ on $\Gamma\times\Gamma$ defined by

where $\mu\times\mu$ denotes the product measure and $\mu_{{\rm diag}}((x,y))=\mu(x)$ if $x=y$ and $0$ otherwise. For any two probability measures $\nu_{1}$ and $\nu_{2}$ on a countable set $X$, the total-variation distance is defined by

The $\ell^{1}$-noise sensitivity was introduced by Benjamini and Brieussel [BB21, Definition 2.1]. There it has been shown that this notion in general highly depends not only on $\Gamma$ but also on $\mu$. Among others, they have proved that if $\Gamma$ admits a surjective homomorphism onto the infinite cyclic group ${\mathbb{Z}}$ and the support of $\mu$ is a finite set of generators, then a $\mu$-random walk on $\Gamma$ is not $\ell^{1}$-nose sensitive. Moreover, if $(\Gamma,\mu)$ is non-Liouville, i.e., there exists a non-constant bounded $\mu$-harmonic function on $\Gamma$, then a $\mu$-random walk on $\Gamma$ is not $\ell^{1}$-noise sensitive [BB21, Theorem 1.1]. It is believed that these two properties are the only possible obstructions for the $\ell^{1}$-noise sensitivity for random walks on groups. We show that non-elementary word hyperbolic groups with large class of $\mu$ reveal a strong negation of the $\ell^{1}$-noise sensitivity if $\rho$ is small enough. This also offers in the non-Liouville setting a way to show that random walks are not $\ell^{1}$-noise sensitive in some refined sense for a class of groups possibly without non-trivial homomorphisms onto ${\mathbb{Z}}$.

Let $\Gamma$ be a word hyperbolic group. A probability measure $\mu$ on $\Gamma$ is called non-elementary if the support generates a non-elementary subgroup ${\rm gr}(\mu)$ as a group. In this setting, it is equivalent to say that ${\rm gr}(\mu)$ contains a free group of rank greater than one (and $\Gamma$ is necessarily non-elementary). Furthermore we say that $\mu$ has finite first moment if

for some (equivalently, every) word norm $|\cdot|$. First we note that all $\mu$-random walk on $\Gamma$ for a non-elementary $\mu$ is not $\ell^{1}$-noise sensitive without any moment condition.

This in fact follows from the proof of [BB21, Theorem 4.1] due to the non-Liouville property. We provide a proof in this setting to illustrate our approach. Second we show that under the finite first moment condition if $\rho$ is close enough to $0$, then the distribution of a $\pi^{\rho}$-random walk and the joint distribution of independent copies of two $\mu$-random walks are mutually singular at infinity.

In the case when $\mu$ is not a non-elementary probability measure, these statements are no longer true. Indeed, it suffices to consider elementary word hyperbolic groups, which are either finite groups or contain ${\mathbb{Z}}$ as a finite index subgroup (see e.g., [Gro87] and [GdlH90] for background). If $\Gamma$ is a finite group, then for every probability measure $\mu$ on it, a $\mu$-random walk on $\Gamma$ is $\ell^{1}$-noise sensitive. Indeed, $\pi^{\rho}$ and $\mu\times\mu$ have the same support on $\Gamma\times\Gamma$ and the distributions of corresponding random walks with the same initial state tend to a common stationary distribution for time with the same parity (cf. [BB21, Proposition 5.1]). Benjamini and Brieussel have shown that on the infinite dihedral group, a lazy simple random walk on a Cayley graph is $\ell^{1}$-noise sensitive [BB21, Theorem 1.4].

As it is mentioned above, if $\Gamma$ has a surjective homomorphism onto ${\mathbb{Z}}$, then a $\mu$-random walk can not be $\ell^{1}$-noise sensitive. This follows by computing covariance of the random walk on each factor of ${\mathbb{Z}}^{2}$ as the image of product of homomorphisms and the classical central limit theorem. The method thus works for $\mu$ with finite second moment. We note, however, that so far this and the non-Liouville property have been the only known ways to disprove $\ell^{1}$-noise sensitivity. See [BB21] and [Kal18, Section 3.3.4] for discussions concerning the subject of matters, various interesting notions of noise sensitivity for random walks on groups, questions and conjectures.

The proofs of Theorems 1.2 and 1.3 rely on the boundary of word hyperbolic groups, in particular, the fact that a $\mu$-boundary or the Poisson boundary for $(\Gamma,\mu)$ is realized on a topological boundary of the group. In this setting, we show that if $h(\pi^{\rho})\neq h(\pi^{\rho^{\prime}})$ for $0\leq\rho,\rho^{\prime}\leq 1$, then

where $h(\pi^{\rho})$ is the asymptotic entropy for a $\pi^{\rho}$-random walk (see Section 2 for the definition, and Remark 5.1). It is proven by showing that the harmonic measure $\nu_{\pi^{\rho}}$ on the product of boundaries $(\partial\Gamma)^{2}$ is exact dimensional with a natural (quasi-) metric, i.e.,

where $l$ stands for the drift defined by a product metric in $\Gamma\times\Gamma$ (see Theorem 3.1 for the precise statement). The proof follows the methods in [Tan19], adapting to a product of word hyperbolic groups. By (1.1), together with the continuity of $h(\pi^{\rho})$ in $\rho\in[0,1]$ (Corollary 4.2), as it is established by a general result of Erschler and Kaimanovich [EK13], we show that there exists some $0<\rho_{\ast}\leq 1$ with $h(\pi^{\rho})<h(\pi^{1})$ for all $0<\rho<\rho_{\ast}$, deducing Theorem 1.3.

It would be interesting to determine $\rho_{\ast}$ in Theorem 1.3. For example, in the case when $\mu$ is a uniform distribution on a finite set of size $m\geq 2$, freely generating a free semi-group, the asymptotic entropy is explicitly computed as

and $h(\pi^{\rho})<h(\pi^{1})=2\log m$ if $\rho<1$. This implies that $\rho_{\ast}=1$ in the special case. It might be expected that $\rho_{\ast}=1$ in many cases, however, we do not know how to show this in general.

Organization of this paper is the following: In Section 2 we review known facts and tools on random walks and word hyperbolic groups, in Section 3 we show that the harmonic measure for $\pi$ whose marginals are a common non-elementary probability measure $\mu$ on $\Gamma$ with finite first moment is exact dimensional in Theorem 3.1, in Section 4 the continuity of asymptotic entropy in the parameter is established in Corollary 4.2, following [EK13], in Section 5 we show Theorems 1.2 and 1.3, and in Appendix A, we give a review concerning Poisson boundary for random walks and a proof on continuity of asymptotic entropy for the sake of convenience, mainly for an expository purpose.

The $\mu$-random walk $\{w_{n}\}_{n=0}^{\infty}$ on a word hyperbolic group $\Gamma$ converges to a point $w_{\infty}$ in $\partial\Gamma$ almost surely as $n\to\infty$ in $\Gamma\cup\partial\Gamma$ if ${\rm gr}(\mu)$ is non-elementary [Kai00, Theorem 7.6]. This implies that the $\pi$-random walk $\{{\bm{w}}_{n}\}_{n=0}^{\infty}$ on $\Gamma\times\Gamma$ converges to a point ${\bm{w}}_{\infty}:=(w_{\infty}^{(1)},w_{\infty}^{(2)})$ in $(\partial\Gamma)^{2}$ almost surely as $n\to\infty$ in the product space $(\Gamma\cup\partial\Gamma)^{2}$, where ${\bm{w}}_{n}=(w_{n}^{(1)},w_{n}^{(2)})$ and each $w_{n}^{(i)}$ tends to $w_{\infty}^{(i)}$ almost surely for $i=1,2$. Let $\nu_{\mu}$ and $\nu_{\pi}$ denote the limiting distribution of $w_{\infty}$ on $\partial\Gamma$ and that of $(w_{\infty}^{(1)},w_{\infty}^{(2)})$ on $(\partial\Gamma)^{2}$, respectively. We call $\nu_{\mu}$ and $\nu_{\pi}$ harmonic measures on $\partial\Gamma$ and on $(\partial\Gamma)^{2}$, respectively. Note that the push-forward of $\nu_{\pi}$ on each factor $\partial\Gamma$ coincides with $\nu_{\mu}$. The harmonic measure $\nu_{\pi}$ (resp. $\nu_{\mu}$) is $\pi$-stationary (resp. $\mu$-stationary), i.e.,

where $\pi\ast\nu_{\pi}:=\sum_{{\bm{x}}\in\Gamma\times\Gamma}\pi({\bm{x}}){\bm{x}}\nu_{\pi}$ and ${\bm{x}}\nu_{\pi}=\nu_{\pi}\circ{\bm{x}}^{-1}$, and similarly,

The $\nu_{\pi}$ and $\nu_{\mu}$ are unique such measures satisfying (3.1) and (3.2), respectively [Kai00, cf. Theorem 2.4]. Concerning more on background, see [Kai00].

For the harmonic measure $\nu_{\pi}$ for the $\pi$-random walk, we show the following:

Let us define the (upper) Hausdorff dimension of $\nu_{\pi}$ by

where $\dim_{\rm H}E$ stands for the Hausdorff dimension of $E$ relative to $q_{\times}$ in $(\partial\Gamma)^{2}$. Theorem 3.1 together with the Frostman-type lemma (cf. [Tan19, Section 2.2]) shows the following:

Let us keep the same setting and notations as in Theorem 3.1 throughout this section. We use the following ray approximation of a $\mu$-random walk on a word hyperbolic group $\Gamma$: Let $\Pi$ be a Borel measurable map from $\partial\Gamma$ to the space ${\mathcal{P}}$ of unit speed geodesic rays from $o$ in $(\Gamma,d)$ endowed with the topology of convergence on compact sets. (Here $\Pi$ is defined as a Borel measurable map by choosing a total order on a fixed set of generators and the lexicographical minimal geodesic for each point in the boundary.) Letting

we have

[Kai00, Section 7.4], where one should write instead $\lfloor ln\rfloor$ (the integer part of $ln$) here and below, however, we keep “$ln$” for the sake of simplicity. Let us define the map

as a Borel measurable map. For a $\pi$-random walk $\{{\bm{w}}_{n}\}_{n=0}^{\infty}$ on $\Gamma\times\Gamma$, we have by (3.3),

Recall that the Shannon theorem for random walks:

which follows from the Kingman subadditive ergodic theorem ([KV83, Theorem 2.1] and [Der80, Section IV] where Y. Derriennic attributes to an observation by J. P. Conze).

First we show the dimension upper bound in the claim.