Jean-Philippe Goiran

Gilles Brocard

provençale au littoral tyrrhénien

La remontée du niveau marin en Méditerranée : de la côte

La remontée du niveau marin, amorcée à la fin de la glaciation, va transformer les paysages littoraux. Les témoins pariétaux de ces changements sont spectaculaires dans les calanques au sud de Marseille, près du cap Morgiou, où se trouve la grotte Cosquer, dont les parois ont été ornées entre 27 000 et 19 000 ans. On entrait alors dans la grotte par une ouverture située au pied d'une falaise littorale, à environ 35 m sous le zéro marin actuel. La mer a effacé toute trace de peinture pariétale dans les parties inondées de la grotte. Pour arriver jusqu'aux salles situées au-dessus du niveau de la mer principale, il faut parcourir 175 m d'un long couloir naturel. Deux phases d'ornementation ont été mises en évidence. La première vers 27 000 ans BP (Gravettien) est riche en dessins (type pochoir) de mains humaines en négatif noir (charbon) ou rouge (argile ocre). La seconde, vers 19 000 ans BP (Solutréen) comporte beaucoup d'animaux terrestres : bisons, chevaux, bouquetins, félins… et surtout des faunes marines inhabituelles des grottes ornées : phoques, méduses, voire des cétacés.

Si la montée des mers a détruit les peintures les plus basses, elle a aussi permis de préserver de dégradations postérieures ces parties de la grotte demeurées inaccessibles. Mais une question intriguait les scientifiques : depuis quand le boyau d'entrée de la grotte a-t-il été ennoyé ? Les scientifiques ont repéré et prélevé des algues calcaires coralligènes (Mesophyllum lichenoides) sur les parois de l'entrée pour les dater. Leur datation, réalisée au laboratoire radiocarbone de Lyon, indique un ennoiement du couloir d'entrée vers 7 000 ans av. J.-C. (soit 9 000 ans BP). Fig. 2 : profil transversal de la grotte Cosquer et du couloir d'accès et de son entrée avec la position des prélèvements Mesophyllum lichenoides pour datation au radiocarbone. Source [START_REF] Sartoretto | Quand la Grotte Cosquer a-t-elle été fermée par la montée des eaux ? Note dans la Revue Méditerranée[END_REF] Que s'est-il donc passé dans la grotte entre 19 000 BP et 9 000 BP ? Durant 10 000 longues années (à la fin du paléolithique supérieur et durant tout le mésolithique), la grotte est en principe toujours accessible aux humains, sans qu'aucune trace de leur passage, empreinte ou dessin sur ses parois, ne soit décelée, en tout cas dans les parties hautes, préservées, de la grotte.

Sur le littoral de Toscane, sur le pourtour du Monte Argentario, des grottes immergées et émergées ont, elles aussi, permis de mieux comprendre l'évolution des paysages côtiers. L'analyse des spéléothèmes (stalagmites et stalactites) de calcite a permis de reconstituer à la fois l'environnement de l'époque, le contexte paléogéographique, mais aussi les variations relatives du niveau marin. Le paradoxe étant que, pour l'étape n°3, même si le niveau marin continue de monter, les apports sableux sont suffisamment importants pour qu'un double tombolo puisse naturellement émerger. Une lagune dite « de tombolo » se met en place, dont les rivages sont occupés par des populations proto-historiques. Par la suite, l'histoire du peuplement s'intensifie et une cité étrusque se construit en son centre (sur un 3 e tombolo plus ancien).

La remontée du niveau marin empêche une lecture de la stratigraphie et de la géométrie de ces couches sédimentaires et de l'histoire de ces paysages. Les carottages et la géophysique sont deux approches qui permettent de faire progresser nos connaissances en géomorphologie côtière.

Récemment le CNRS -INSHS -INSU et l'IFREMER ont financé, en accord avec les autorités italiennes, une vaste campagne de prospections géophysiques (REF billet BLOG décembre 2022). En parcourant la frange côtière, le navire Haliotis opéré par Genavir a permis l'acquisition de profils sismiques révélant l'agencement des couches de sédiments déposées depuis la remontée du niveau de la mer.

La sismique haute résolution repose sur l'émission puis la réception d'ondes acoustiques. Le sonar produit une onde dirigée vers le fond marin. Ces ondes sont réfléchies par le fond et les différentes couches sédimentaires sous-jacentes, et leur écho est enregistré à la réception. La succession des échos renvoyés par les différentes couches permet de visualiser leur superposition. En se déplaçant de proche en proche, on peut observer les changements de profondeur de ces couches, et dessiner ainsi progressivement leur géométrie, leurs recoupements, et ainsi révéler l'architecture sédimentaire des dépôts. Les scientifiques peuvent en déduire les processus qui les ont mis en place sur les derniers milliers d'années, et comprendre les tendances les plus récentes.

Ce programme IFREMER nommé HISOPE vient compléter, en mer, le projet IMU-URBO. Le projet IMU-URBO est financé par le Laboratoire d'Excellence -LabEx IMU (Intelligences des Mondes Urbains). Le projet IMU-URBO se déroule dans la lagune d'Orbetello, en lien avec les réserves littorales du WWF et l'Université de Florence. L'objectif est de comprendre la coévolution de la cité étrusque d'Orbetello et de sa lagune, une entité naturelle et une entité artificielle dont les destins sont étroitement liés. Les profils géophysiques acquis au large des deux réserves WWF (celles de la lagune d'Orbetello et celle du lago di Burano) dans le cadre de la mission IFREMER-HISOPE, et les profils géophysiques acquis dans les deux lagunes mettent en évidence deux dynamiques différentes. La lagune d'Orbetello est séparée de la mer par un cordon littoral constitué par une puissante accumulation sableuse (le cordon de la Feniglia). En revanche, le long du lido de Burano, on note un transit sédimentaire côtier, voire une érosion généralisée du cordon, sans accumulation de sable dans les proportions de celles observées à la Feniglia. La réserve naturelle WWF de la lagune dite du « Lago di Burano » est donc menacée à long terme à la fois par la montée du niveau marin, par le déficit d'apport sableux à la côte (provenant des cours d'eau), et par la recrudescence des tempêtes érosives. Un travail comparatif sur les archives sédimentaires de ces deux lagunes est en cours.

Fig. 3 :

 3 Fig. 3 : La lagune d'Orbetello (Toscane, Italie) encadrée par ses deux tombolos reliant le Monte Argentario. La ville d'Orbetello sur le 3 e tombolo central, plus ancien. La lagune de Burano séparée de la mer par un lido sableux. Les tracés, de couleur bleue, représentent les profils sismiques en mer. Jusque vers 7 000 BP la vitesse de remontée du niveau marin ne permettaient pas aux sédiments en provenance des continents ou de la mer de s'accumuler le long de ces rivages en transformation rapide. Les vallées en arrière du littoral se retrouvent ennoyées, et les côtes deviennent, pour une grande part, des côtes rocheuses, sinueuses, constituées d'innombrables caps, rias (vallées ennoyées), et estuaires. A partir de 7000 BP, la vitesse de remontée du niveau marin s'infléchit. Ce ralentissement de la remontée du niveau marin permet alors, enfin, aux alluvions de s'accumuler. Les fleuves et la mer commencent à remplir les estuaires et les rias d'argiles et de sables. De longues barres de sable (tombolos et lidos) se constituent derrière les caps et les îles, formant des lagunes. En conséquence, le Monte Argentario connaît une évolution en 3 étapes. (1) Lors du bas niveau marin, les populations du Paléolithique supérieur et du Mésolithique peuvent accéder à pied au Monte Argentario. (2) À la fin du Mésolithique et au début du Néolithique, le Monte Argentario devient, en raison de la remontée marine, une île séparée du continent par un bras de mer. (3) Enfin, la mise en place de cordons sableux à l'arrière de l'île (les tombolos) permet aux populations du Néolithique et de l'âge du Bronze d'accéder à « pied sec »au « Monte ».

Remerciements

Quatre principaux programmes de recherche : (i) IDEX-UDL-ULD2, (ii) LabEx IMU, (iii) Scientific grant Florida State University, (iv) HISOPE-IFREMER. Le Dott. Fabio Cianchi (Cordinatore Oasi WWF Maremma (Laguna di Orbetello & Lago di Burano), Fondazione WWF Italia). La Prof.ssa Adele Bertini (Univ. Firenze). Andrea U. De Giorgi (Florida State University, USA). Enrico Maria Giuffre et Matteo Milletti (Soprintendenza Archeologia Belle Arti e Paesaggio per le province di Siena, Grosseto e Arezzo). Marco Leporati-Persiano (Consultant, Regione Lazio). I Pescatori e i Canotieri di Orbetello. La Flotte Océanographique Française (IFREMER). Genavir. Barbara Davidde (Soprintendenza Nazionale per il patrimonio culturale subacqueo).


Itaï Benjamini
email: itai.benjamini@gmail.com

Jérémie Brieussel
email: jeremie.brieussel@umontpellier.fr

Noise sensitivity of random walks on groups

Keywords: Mathematics Subject Classification. 60B15, 05C81, 20F65 Random walks on groups, noise sensitivity

A random walk on a group is noise sensitive if resampling every step independently with a small probability results in an almost independent output. We precisely define two notions:

1 -noise sensitivity and entropy noise sensitivity. Groups with one of these properties are necessarily Liouville. Homomorphisms to free abelian groups provide an obstruction to 1 -noise sensitivity. We also provide examples of 1 and entropy noise sensitive random walks.

Noise sensitivity raises many open questions which are described at the end of the paper.

Introduction

Physically, noise is a non-significant perturbation of an observation. In signal theory, noise is an unintentional perturbation of a message. Noise is an inherent phenomenon to physical observations and to communication. Its influence on a channel capacity was already taken into account by Shannon in his mathematical theory of communication [START_REF] Shannon | A mathematical theory of communication[END_REF].

In probability theory, the noise of an event E(x 1 , . . . , x n ) (i.e. a Boolean function) depending on a large number of variables can be modeled as the effect of replacing a (small) proportion ρ ∈ (0, 1) of the variables by random entries. An event is noise sensitive if the realisation of E gives no (or very little) information on what happens when the entries are perturbed by noise. For instance in bond percolation at critical probability 1 2 , having a left-right crossing on an n × n square lattice is a noise sensitive event [START_REF] Benjamini | Noise sensitivity of Boolean functions and applications to percolation[END_REF]; [START_REF] Garban | The Fourier spectrum of critical percolation[END_REF]. On the contrary, (weighted) majority functions are noise stable [START_REF] Benjamini | Noise sensitivity of Boolean functions and applications to percolation[END_REF]. The effect of noise in percolation and voting games has been widely studied over the last decades. We refer to [START_REF] Benjamini | Noise sensitivity of Boolean functions and applications to percolation[END_REF]; [START_REF] Garban | Noise sensitivity of Boolean functions and percolation[END_REF]; [START_REF] Garban | The Fourier spectrum of critical percolation[END_REF]; [START_REF] Kalai | Three puzzles on mathematics, computation, and games[END_REF] and references therein for more on these topics.

In the present paper we investigate sensitivity to noise of random walks on groups. A random walk on a group G is a sequence of products X n = s 1 . . . s n of independent variables s i following identical distribution µ. Given such a product X n , we can noise it by resampling independently each increment s i with a probability ρ ∈ (0, 1), this provides a new variable Y ρ n depending on X n . In the Cayley graph, the original word X n can be interpreted as a sequence of instructions for a moving particule and Y ρ n as the effective trajectory if instructions are misread with probability ρ. Broadly speaking, the random walk (G, µ) is noise sensitive if Y ρ n generally seems independent of X n . This vague statement can be specified in a number of ways and we refer to Section 2 for several precise definitions. We retain two principal notions of noise sensitivity in this context. The random walk (G, µ) is 1 -noise sensitive if the law of the pair (X n , Y ρ n ) and the law of a pair (X n , X n ) of two independent samples are close in the sense that their 1 -distance tends to zero. The random walk is entropy noise sensitive if the ratio between the conditional entropy H(Y ρ n |X n ) and H(X n ) tends to one, which means that the average amount of information needed to describe Y ρ n once we already know X n is (asymptotically) as big as the average amount of information needed to describe X n .

These notions of noise sensitivity are relevant for infinite groups. They are trivially satisfied for finite groups by eventual equidistribution -see Theorem 5.1. For simplicity, we restricted our investigations to finitely generated groups and finitely supported probability measures, though the notions make sense in a wider setting.

We first point out two elementary obstructions to 1 -noise sensitivity.

Theorem 1.1. Let G be a countable group and µ a finitely supported probability measure on G.

(1) If G admits a non-trivial homomorphism onto a free abelian group, then (G, µ) is not 1 -noise sensitive.

(2) If (G, µ) is 1 -noise sensitive, then it is Liouville. This is a concatenation of Corollary 5.4 and Theorem 4.1. The first part essentially follows from the central limit theorem. For the second part, recall that the space of bounded harmonic functions on (G, µ) is parametrized by the Poisson boundary [START_REF] Furstenberg | Random walks and discrete subgroups of Lie groups[END_REF]. The random walk (G, µ) is Liouville if this boundary is reduced to a point, i.e. if all bounded harmonic functions are constant. In the non-Liouville case, the first increment s 1 already carries information on the position of X n . For instance in a free group, the first letter of a minimal representative word of X n is correlated to the first increment. This prevents 1 -noise sensitivity of the free group. In fact, this obstruction can be strengthen to show that the free group is not even noise sensitive at large scale, see Proposition 4.2.

By [START_REF] Kaȋmanovich | Random walks on discrete groups: boundary and entropy[END_REF], Liouville property is also equivalent to the vanishing of the asymptotic entropy lim 1 n H(X n ) which measures the average amount of information in one increment of X n . This provides an elementary obstruction to entropy noise sensitivity.

Theorem 1.2. If (G, µ) is entropy noise sensitive, then it is Liouville. This is a particular case of Theorem 4.3. It follows directly from the upper semi-continuity of the asymptotic entropy Amir et al. (2013, Proposition 4). [START_REF] Frisch | Choquet-Deny groups and the infinite conjugacy class property[END_REF], any non-virtually nilpotent finitely generated group admits a symmetric probability measure of finite entropy (usually not finitely supported) for which it is non-Liouville. It is a fortiori neither 1 -noise sensitive, nor entropy noise sensitive.

Despite these obstructions, we provide examples of noise sensitive random walks on groups.

Theorem 1.3. Regarding entropy noise sensitivity:

• finitely generated abelian groups are entropy noise sensitive with respect to any finitely supported measure, • the lamplighter group Z/2Z Z is entropy noise sensitive with respect to the switch-walk-switch measure,

• the permutational extension of the first Grigorchuk group described in [START_REF] Bartholdi | Growth of permutational extensions[END_REF] is partially entropy noise sensitive for some switch and walk measure, i.e.

∃c > 0, ∀ρ ∈ (0, 1), lim inf

H(Y ρ n |X n ) H(X n ) ≥ c.
The first point is in Proposition 5.2, the second is Theorem 7.1 and the third point a particular case of Theorem 7.3.

Theorem 1.4. On the infinite dihedral group D ∞ = a, b|a 2 , b 2 ,

• the simple random walk is not 1 -noise sensitive,

• the lazy simple random walk is 1 -noise sensitive.

This is Theorem 6.1. It follows that 1 -noise sensitivity is not a geometric property, since it depends on the measure. Moreover as our notions of noise sensitivity are stable under taking direct products (of groups and measures), we obtain noise sensitive random walks on groups commensurable to Z d for any rank d.

We expect that morphisms to Z and non-Liouville property (significance of the first increment) are the only two obstructions for a group to be noise sensitive. This raises the: Question 1.5. If (G, µ) is Liouville and has no virtual morphism onto Z, is it 1 -noise sensitive?

Another (unexpected) type of obstruction to 1 -noise sensitivity would probably be very interesting and significant. As a particular case, we conjecture that:

Conjecture 1.6. The first Grigorchuk group is 1 -noise sensitive for finitely supported µ.

As for entropy noise sensitivity, we believe it is widely spread and we conjecture:

Conjecture 1.7. A random walk (G, µ) is entropy noise sensitive if and only if it is Liouville.

In particular, we believe that 1 -noise sensitivity implies entropy noise sensitivity -see Section 3. Physically, an 1 -noise sensitive process can somewhat not be observed, since the observation Y ρ n does not provide any significant information on the actual output X n . Speculatively, this could account for the rarity of Liouville (probability) groups in natural science. Indeed besides virtually nilpotent ones, all known Liouville groups are genuinely mathematical objects, introduced by mathematicians to solve their problems, without reference to physical sciences [START_REF] Alešin | Finite automata and the Burnside problem for periodic groups[END_REF]; [START_REF] Kaȋmanovich | Random walks on discrete groups: boundary and entropy[END_REF]; [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF][START_REF] Grigorchuk | On the growth degrees of p-groups and torsion-free groups[END_REF]; [START_REF] Amir | Amenability of linear-activity automaton groups[END_REF]; [START_REF] Brieussel | Behaviors of entropy on finitely generated groups[END_REF]; Matte Bon (2014); [START_REF] Nekrashevych | Palindromic subshifts and simple periodic groups of intermediate growth[END_REF].

Organization of the paper. Precise definitions of noise sensitivity are given in Section 2 and some of their relationships are studied in Section 3. The effects of Liouville property on noise sensitivity are discussed in Section 4. Section 5 is devoted to finite and abelian groups, Section 6 to the infinite dihedral group. Wreath products are studied in Section 7. Some perspectives and open questions are presented in the final Section 8.

Notions of noise sensitivity

Let G be a countable group. We endow it with a probability measure µ whose support generates G as a semi-group. The random walk (G, µ) is the sequence of random variables X n = s 1 . . . s n where (s k ) k≥1 are independent of law µ. The law of X n is the n-fold convolution µ n := µ * n .

Given X n and a noise parameter ρ ∈ [0, 1], we consider another random variable where the increments s k are refreshed (i.e. resampled independently according to µ) with probability ρ. More precisely, we define Y ρ n = r 1 . . . r n where

r k = s k with probability 1 -ρ, s k with probability ρ,
where s k is an independent random variable of law µ. We interpret Y ρ n as a version of X n perturbed by some noise. Of course the law of Y ρ n alone is the same as that of X n . We denote by π ρ n the joint law of (X n , Y ρ n ) on G × G. It is the distribution at time n of the random walk on G × G with measure π ρ := (1 -ρ)µ diag + ρµ 2 where µ diag is the diagonal measure on the product taking values µ diag (x, y) = µ(x) when x = y and µ diag (x, y) = 0 otherwise, and µ 2 := µ × µ. In particular, π ρ n is symmetric in the two variables, π 1 n = µ 2 n is the law of a µ 2 -random walk on G × G at time n and π 0 n = µ diag n is the original random walk embedded diagonally in G × G. In this paper, we investigate the notion of noise sensitivity of a random walk, that is how much Y ρ n for ρ ∈ (0, 1) can differ from X n . Informally, we say that Y ρ n is noise sensitive if the couple (X n , Y ρ n ) resembles a couple (X n , X n ) of two independent samples of the random walk, i.e. if the two probability measures π ρ n and µ 2 n are close. We present several precise quantitative ways of measuring noise sensitivity.

2.1. Measure-theoretic notions of noise sensitivity. Let us start with the most natural notion.

Definition 2.1. 1 -noise sensitivity. The random walk (G, µ) is 1 -noise sensitive if ∀ρ ∈ (0, 1), π ρ n -µ 2 n 1 -→ n→∞ 0.
We recall that the 1 -distance (or twice total variation) between two probability measures ξ 1 , ξ 2 on a countable space E is

ξ 1 -ξ 2 1 := x∈E |ξ 1 (x) -ξ 2 (x)| ∈ [0, 2].
The 1 -distance is also characterised in terms of coupling:

ξ 1 -ξ 2 1 = inf ν∈Coup(ξ 1 ,ξ 2 ) ν(x = y),
where a coupling ν of ξ 1 and ξ 2 is a probability measure on E × E whose marginals are ξ 1 and ξ 2 .

Let us now define a weaker notion of noise sensitivity, related to entropy. Recall that the Shannon entropy of a random variable X of law ξ taking values in a countable set E is

H(X) = H(ξ) := - x∈E ξ(x) log(ξ(x)) = E ξ I ξ (x),
where I ξ (x) = -log(ξ(x)) is the information function. Informally, the entropy of X is the average number of digits needed to describe the value of X. Moreover the conditional entropy of another random variable Y with respect to X is

H(Y |X) = E X H X (Y ) = x∈X(E) P(X = x)   - y∈E P(Y = y|X = x) log P(Y = y|X = x)  
i.e. the expectation with respect to X of the entropy of the law of Y conditioned by the value of X. Informally this is the average amount of information needed to describe Y when we already know X.

Definition 2.2. Entropy noise sensitivity. The random walk (G, µ) is entropy noise sensitive if

∀ρ ∈ (0, 1), H(Y ρ n |X n ) H(X n ) -→ n→∞ 1.
The random walk is partially entropy noise sensitive if

∃c > 0, ∀ρ ∈ (0, 1), ∃N, ∀n ≥ N, H(Y ρ n |X n ) ≥ cH(X n ).
Informally speaking, partial entropy noise sensitivity ensures that no matter how small the noise parameter, there is always a fixed proportion of information that cannot be recovered from the noised sample.

It is well known that for any two random variables H ((X, Y )) = H(Y |X) + H(X). In the present context, we get

H(Y ρ n |X n ) = H(π ρ n ) -H(µ n ).
2.2. Metric notions of noise sensitivity. As the notion of 1 -convergence of measures is strong, it can be interesting to relax it. We propose here other notions of noise sensitivity, related to metrics on the group, and motivated by the usual interest in geometric group theory for the large scale aspects of the metric. They can be omitted in first reading. Given a metric d on a space E, we may define other notions of convergence of measures, for instance via the Wasserstein distances, defined for p ∈ [1, ∞) by:

W p (ξ 1 , ξ 2 ) := inf ν∈Coup(ξ 1 ,ξ 2 ) E ν [d(x, y) p ] 1 p .
In practice, we will rather use a related notion based on the following quantity: given s > 0 set

U s (ξ 1 , ξ 2 ) := inf ν∈Coup(ξ 1 ,ξ 2 ) ν (d(x, y) ≥ s) .
By Markov inequality, we have:

U s (ξ 1 , ξ 2 ) 1 p ≤ W p (ξ 1 , ξ 2 ) s (2.1)
Definition 2.3. Noise sensitivity at scale s n . Given a left-invariant distance on G × G and a sequence (s n ), the random walk (G, µ) is noise sensitive at scale

s n if ∀ρ ∈ (0, 1), U sn (π ρ n , µ 2 n ) -→ n→∞ 0.
From a mass transport point of view, this means that for n large, all but an ε proportion of the "sand pile" mass distribution of µ 2 n can be obtained from π ρ n , moving sand by distance less than s n . Unless mentioned otherwise, we assume the distance on G × G is a word distance, e.g. d G×G ((x, y), (x , y )) = d G (x, x ) + d G (y, y ) where d G is a word distance on G. We recall that all word distances on a finitely generated group are equivalent up to multiplicative constants.

We point out:

• Noise sensitivity at scale 1 is equivalent to 1 -noise sensitivity when the distance takes integer values, e.g. in discrete groups with word metric.

• If a Wasserstein distance satisfies W p (π ρ n , µ 2 n ) = o(s n ), then (G, µ) is noise sensitive at scale s n by (2.1). • If s n ≥ s n and (G, µ) is noise sensitive at scale s n , then it is noise sensitive at scale s n , because U s (ξ 1 , ξ 2 ) ≤ U s (ξ 1 , ξ 2 ) whenever s ≥ s. • The quantity U s resembles a distance in the sense that U s (ξ 1 , ξ 3 ) ≤ U s 1 (ξ 1 , ξ 2 ) + U s 2 (ξ 2 , ξ 3 ) whenever s 1 + s 2 = s.
(2.2)

The last point is proved along the same lines that W 1 is a distance. Namely let ν 12 and ν 23 be appropriate couplings to get U s 1 (ξ 1 , ξ 2 ) and U s 2 (ξ 2 , ξ 3 ). There exists γ a probability on E 3 whose projections satisfy p 12 γ = ν 12 and p 23 γ = ν 23 . The coupling ν 13 := p 13 γ gives (2.2).

Definition 2.4. Noise sensitivity at large scale The random walk (G, µ) is noise sensitive at large scale if there exists a sequence such that

s n = o(Ed G (X n , X n )) and (G, µ) is noise sensitive at scale s n .
The spread Ed G (X n , X n ) of the random walk can be considered as the natural scale to describe the distribution µ n . Noise sensitivity at large scale essentially means that most refreshed samples Y ρ n look independent of X n at the spread scale. For instance, the central limit theorem for virtually abelian groups provides a gaussian description of the distribution of µ n at the spread scale √ n. For such a group, noise sensitivity at large scale implies that the limit gaussian distribution of (X n , Y ρ n ) is the same as that of (X n , X n ).

Definition 2.5. Noise sensitivity in average distance. Given a left-invariant distance d G on G (e.g. a word distance when G is finitely generated), the random walk (G, µ) is noise sensitive in average distance if

∀ρ ∈ (0, 1), lim inf n→∞ Ed G (X n , Y ρ n ) Ed G (X n , X n ) ≥ 1.
The random walk (G, µ) is partially noise sensitive in average distance if

∃c > 0, ∀ρ ∈ (0, 1), ∃N, ∀n ≥ N, Ed G (X n , Y ρ n ) ≥ cEd G (X n , X n ).

Relationships between notions of noise sensitivity

The 1 noise sensitivity seems to be the strongest among the notions defined above. It implies noise sensitivity at any (in particular at large) scale.

3.1. 1 -noise sensitivity and entropy noise sensitivity. We believe that 1 -noise sensitivity implies entropy noise sensitivity, which would be a consequence of Conjecture 1.7. We prove it under an additional assumption of homogeneity.

Definition 3.1. A sequence (ξ n ) of probability measures on G has homogeneous entropy if

h n (ε) := sup 1 H(ξ n ) x∈A ξ n (x) log(ξ n (x)) A ⊂ G, ξ n (A) ≤ ε -→ ε→0 0 uniformly in n.
Informally, this means that the smallest atoms do not contribute much to the entropy. Proposition 3.2. If a random walk (G, µ) is 1 -noise sensitive and if the sequence of measures (π ρ n ) n has homogeneous entropy for each ρ ∈ (0, 1], then (G, µ) is entropy noise sensitive. Proof : The case of finite groups is trivial by Proposition 5.1. We assume G is infinite. Let ν n be a coupling between two sequences (ξ 1 n ) and (ξ 2 n ) with homogeneous entropy such that ν n (x 1 = x 2 ) → 0. Then for small ε > 0 and each i = 1, 2, denote

A i ε := {(1 -ε)ξ i n (x) ≤ ν n (x, x) ≤ ξ i n (x)}. For n large enough, ξ i n (A i ε ) ≥ 1 -ε, thus ν n {(x, x) : x ∈ A i ε } ≥ (1 -ε) 2 ≥ 1 -2ε and by taking marginal ξ 3-i n (A i ε ) ≥ 1 -2ε. It follows that ξ i n (A 1 ε ∩ A 2 ε ) ≥ 1 -3ε.
As the modulus of continuity of the function x log(x) is ω(ε) = ε| log ε|, one has for all x, y ∈ (0, 1]

x y -1 ≤ ε ⇐⇒ |x -y| ≤ εy =⇒ |x log x -y log y| ≤ ω(εy) ≤ εy |log ε + log y| =⇒ x log x y log y -1 ≤ ε| log ε| | log y| + ε
Using the homogeneity assumption:

H(ξ i n ) = - x ξ i n (x) log(ξ i n (x)) = - x∈A 1 ε ∩A 2 ε ξ i n (x) log(ξ i n (x)) + h i n (3ε)H(ξ i n ) = - x∈A 1 ε ∩A 2 ε ν n (x, x) log(ν n (x, x)) ξ i n (x) log(ξ i n (x)) ν n (x, x) log(ν n (x, x)) + h i n (3ε)H(ξ i n ) = -(1 + ψ i n (ε)) x∈A 1 ε ∩A 2 ε ν n (x, x) log(ν n (x, x)) + h i n (3ε)H(ξ i n ),
where

|ψ i n (ε)| ≤ ε| log ε| log 2 + ε -→ ε→0
0 provided all the atoms of ν n have mass at most 1 2 . We apply these equalities for ξ

1 n = π ρ n and ξ 2 n = µ 2 n = π 1 n (the condition on the atoms of ν n is satisfied for n large because G is infinite). We get that x∈A 1 ε ∩A 2 ε ν n (x, x) log(ν n (x, x)) = H(π ρ n ) + o(H(π ρ n )) = H(µ 2 n ) + o(H(µ 2 n )). It follows that H(π ρ n ) H(µ 2 n ) → 1,
which is equivalent to entropy noise sensitivity. Remark 3.3. For random walks on groups, homogeneous entropy, as well as homogeneous spread (see Definition 3.4 below), are related to the tail decay of the distribution µ n . They are not easy to check on a given group, for it is usually hard to compute entropy or spread in the first place. However they are satisfied for random walks on virtually abelian groups by gaussian decay. They are also satisfied by symmetric random walks on the lamplighter group Z/2Z Z, because of the gaussian decay of the range of a random walk on Z -see formula (7.1) in the proof of Theorem 7.1. Such argument on the range can probably be adapted to the case of iterated lamplighter groups, and possibly to the case of diagonal products of lamplighter groups as in [START_REF] Brieussel | Speed of random walks, isoperimetry and compression of finitely generated groups[END_REF]. However detailed computations are out of the scope of the present article. Non-Liouville random walks also have homogeneous entropy and spread by Shannon's theorems, see e.g. [START_REF] Kaȋmanovich | Random walks on discrete groups: boundary and entropy[END_REF]. We do not know if there exist random walks on groups with non-homogeneous entropy or non-homogeneous spread.

3.2. Noise sensitivity at large scale and noise sensitivity in average distance. We also believe that if (G, µ) is noise sensitive at large scale, then it is noise sensitive in average (word) distance. Remark 4.4 shows that the converse is not true. Again, we prove this under an additional assumption.

Definition 3.4. We say the random walk (G, µ) has homogeneous spread if

f n (ε) := sup    1 Ed G (X n , X n ) (x,y)∈A d G (x, y)µ 2 n (x, y) A ⊂ G × G, µ 2 n (A) ≤ ε    -→ ε→0 0 uniformly in n.
Informally, this means that far away points do not contribute to the spread.

Proposition 3.5. If a random walk (G, µ) is noise sensitive at large scale and has homogeneous spread, then it is noise sensitive in average word distance.

Proof : There exists a sequence

s n = o(Ed G (X n , X n )) such that U sn (π ρ n , µ 2 n ) → 0. So there exists a probability ν n ∈ Coup(π ρ n , µ 2 n ) such that ν n (A n ) → 1 where A n is the event d G 2 ((x, y), (x , y )) ≤ s n . We compute Ed G (X n , Y ρ n ) = G 2 π ρ n (x, y)d G (x, y) = G 4 ν n (x, y, x , y )d G (x, y) ≥ An ν n (x, y, x , y )d G (x , y ) -2s n by triangle inequality, = G 2 ν n (G 2 × {(x , y )}) ∩ A n d G (x , y ) -2s n .
Given ε > 0, for n large enough there exist

B n ⊂ G 2 such that µ 2 n (B n ) ≥ 1 -ε and ∀(x , y ) ∈ B n , ν n (G 2 × {(x , y )}) ∩ A n ≥ (1 -ε)µ 2 n (x , y ). Then Ed G (X n , Y ρ n ) ≥ (1 -ε) Bn µ 2 n (x , y )d G (x , y ) -2s n ≥ (1 -ε)(1 -f n (ε))E µ 2 n d G (x , y ) -2s n .
Noise sensitivity in average distance now follows from the homogeneity assumption.

Noise sensitivity and Liouville property

A function on a group G is µ-harmonic if f (y) = x∈G µ(x)f (yx) for all y. A random walk (G, µ) is Liouville if there are no non-constant bounded µ-harmonic functions. This is equivalent to the fact that the Poisson boundary is reduced to a point [START_REF] Furstenberg | Random walks and discrete subgroups of Lie groups[END_REF] and also equivalent to the fact that the entropy H(X n ) of the random walk is sublinear [START_REF] Kaȋmanovich | Random walks on discrete groups: boundary and entropy[END_REF].

Theorem 4.1. If (G, µ) is 1 -noise sensitive, then (G, µ) is Liouville.
The converse is not true because of infinite abelian groups, see Proposition 5.2.

Proof : First observe that 1 -noise sensitivity implies

µ diag * µ 2 n-1 -µ 2 n 1 -→ n→∞ 0. (4.1)
Indeed, taking the convex decomposition of the first factor

π ρ = (1 -ρ)µ diag + ρµ 2 , the 1 -noise sensitivity first implies (1 -ρ) µ diag * π ρ n-1 -µ 2 n 1 → 0. On the other hand µ diag * π ρ n-1 -µ diag * µ 2 n-1 1 → 0 by left multiplication. Convergence (4.1) follows.
Assume by contradiction that (G, µ) is not Liouville, i.e. admits a non-trivial Poisson boundary (Π, ν). We claim that there exists a subset A ⊂ Π such that

ν(A) 2 < z∈G µ(z)ν(z -1 A) 2 . (4.2)
Indeed, as ν is stationary ν(A) = z∈G µ(z)ν(z -1 A) and the above inequality (4.2) holds with ≤ in place of < by Jensen. As the square function is strictly convex, equality implies ν(z -1 A) = ν(A) for all z in the support of µ and a fortiori for all z. Therefore equality for all A would imply triviality of the Poisson boundary, whence the claim. Now by stationarity of ν 2 with respect to µ 2 , we have for each n that

ν(A) 2 = (x,y)∈G×G µ 2 n (x, y)ν(x -1 A)ν(y -1 A) and z∈G µ(z)ν(z -1 A) 2 = (x,y)∈G×G µ diag * µ 2 n-1 (x, y)ν(x -1 A)ν(y -1 A)
Convergence (4.1) implies that the difference between right hand sides tends to zero, raising a contradiction to (4.2) that ν(A)

2 = z∈G µ(z)ν(z -1 A) 2 .
For the free groups, this theorem can be improved.

Theorem 4.2. Finitely supported random walks on free groups are not noise sensitive at large scale.

Proof : We follow the same line of reasoning as in the previous proof. We are now given a sublinear sequence s n such that U sn (π ρ n , µ 2 n ) → 0. By diagonal coupling of the first factor, we deduce

U s n-1 (π ρ n , π ρ * µ 2 n-1 ) → 0. By (2.
2) in Section 2.2, we obtain:

U sn+s n-1 (π ρ * µ 2 n-1 , µ 2 n ) -→ 0. (4.3)
Let us consider a subset A satisfying (4.2) in the Poisson boundary which is now the geometric boundary of the Cayley tree, i.e. the set of infinite geodesic rays out of the neutral element e. Up to taking a close enough approximation, we may assume that A is open-closed, i.e. a finite union of "cylinder" sets. Recall that "cylinder" sets C h are indexed by h ∈ F, and C h is the collection of geodesic rays out of e crossing h. Moreover, the point h partitions F \ {h} into the set Ĉh consisting of points g from which there is a geodesic ray towards C h not going through h and its complement Ĉc h .

Recall that the speed (or drift) λ := lim 1 n Ed(e, X n ) > 0 is positive. Given α ∈ (0, λ), we define [x] n to be the point at distance αn from e on the geodesic ray from e to x, when x is at distance at least αn from the identity. Otherwise [x] n = e. We will use the fact that

P(d(e, X n ) ≥ αn) -→ n→∞ 1. (4.4)
We claim that

G 2 µ 2 n (g)gν(A) - G 2 µ 2 n (g)[g] n ν(A) -→ n→∞ 0 (4.5)
where we write gν(A)

:= ν(x -1 A)ν(y -1 A) for g = (x, y) and [g] n = ([x] n , [y] n ).
Convoluting by π ρ which has finite support, we get

G 2 π ρ * µ 2 n-1 (g)gν(A) - G 2 π ρ * µ 2 n-1 (g)[g] n ν(A) -→ n→∞ 0. (4.6)
Now let ν n denote appropriate couplings to get (4.3), we have:

G 2 µ 2 n (g)[g] n ν(A) - G 2 π ρ * µ 2 n-1 (g)[g] n ν(A) = (g 1 ,g 2 )∈G 4 ν n (g 1 , g 2 ) ([g 1 ] n ν(A) -[g 2 ] n ν(A)) ≤ 2 (g 1 ,g 2 )∈G 4 ν n (g 1 , g 2 )1 {[g 1 ]n =[g 2 ]n} ≤ U sn+s n-1 (π ρ * µ 2 n-1 , µ 2 n ) + 4P [d G (e, X n ) ≤ αn + s n + s n-1 ] -→ n→∞ 0
where the last inequality is due to the geometry of the tree that if both x, x are at distance ≥ αn+s from identity and d(x, x ) ≤ s, then [x] n = [x ] n . The convergence to 0 follows by (4.3) and (4.4) for α < α < λ as αn + s n + s n-1 < α n for n large. Together with (4.5) and (4.6), we deduce

G 2 µ 2 n (g)gν(A) - G 2 π ρ * µ 2 n-1 (g)gν(A) -→ n→∞ 0
raising the same contradiction as at the end of the proof of Theorem 4.1.

There remains to prove the claim (4.5). As A is a finite union of cylinder sets, it is enough to prove that for any h 1 , h 2 in F, one has

(x,y)∈G 2 µ n (x)xν(C h 1 )µ n (y)yν(C h 2 ) - (x,y)∈G 2 µ n (x)[x] n ν(C h 1 )µ n (y)[y] n ν(C h 2 ) -→ n→∞ 0 (4.7)
We use the facts that xν(A) = ν(x -1 A) is the probability that a random walk started in x tends to a boundary point in A, and that for any ε > 0 there exists N such that when d(x, z) ≥ N , the probability that a random walk started in x ever hits z is at most ε. Using union bounds, we can deduce that for any R ≥ 0, there exists N such that when d(x, h 1 ) ≥ N , a random walk started at x hits the ball B(h 1 , R) with probability at most ε. We use it for R large enough that a random walk trajectory cannot move from Ĉh 1 to its complement (or vice-versa) without stepping in B(h 1 , R).

It follows that for d(e, x) ≥ αn ≥ N + d(e, h 1 ) we have

if x ∈ Ĉh 1 , then xν(C h 1 ) ≥ 1 -ε and [x] n ν(C h 1 ) ≥ 1 -ε, if x ∈ Ĉc h 1 , then xν(C h 1 ) ≤ ε and [x] n ν(C h 1 ) ≤ ε.
Finally, let us denote Λ n the set of points (x, y) in G 2 such that d(e, x) ≥ αn and d(e, y) ≥ αn where n is large enough to have d(e, x) ≥ αn ≥ N + d(e, h 1 ) and the analogous property for y, h 2 in place of x, h 1 . For (x, y) ∈ Λ n , one has

|xν(C h 1 )yν(C h 2 ) -[x] n ν(C h 1 )[y] n ν(C h 2 )| ≤ 5ε
by checking the four cases. Then the expression in (4.7) is

(x,y)∈G 2 µ n (x)µ n (y) (xν(C h 1 )yν(C h 2 ) -[x] n ν(C h 1 )[y] n ν(C h 2 )) ≤ 2µ 2 n (Λ c n ) + 5εµ 2 n (Λ n ) ≤ 4ε + 5ε
where µ 2 n (Λ c n ) is bounded above using (4.4) for n large.

The above proof can probably be generalised to groups with hyperbolic properties. However in full generality, it is not clear if sublinearly close points have close actions on the harmonic measure.

Theorem 4.3. If (G, µ) is partially entropy noise sensitive, then (G, µ) is Liouville.
This is one direction of Conjecture 1.7.

Proof : Assume (G, µ) is not Liouville, which means that the associated Poisson boundary is not trivial. By [START_REF] Kaȋmanovich | Random walks on discrete groups: boundary and entropy[END_REF], this implies

h ∞ (µ) := lim n→∞ H(µ n ) n > 0. Thus H(X n ) = H(µ n ) = h ∞ (µ)n + o(n). Similarly h ∞ (π ρ ) := lim n→∞ H(π ρ n ) n ≥ h ∞ (µ) because H(π ρ n ) = H(X n , Y ρ n ) = H(Y ρ n |X n ) + H(X n ) ≥ H(X n ) = H(µ n ). It follows that H(π ρ n ) = h ∞ (π ρ )n + o(n).
Moreover π ρ = (1 -ρ)µ diag + ρµ 2 tends to µ diag weakly as ρ → 0, and H(π ρ ) → H(µ diag ) = H(µ) as these measures have support in the finite set supp(µ) 2 . The upper semi-continuity of asymptotic entropy Amir et al. (2013, Proposition 4) implies

lim ρ→0 h ∞ (π ρ ) = h ∞ (µ).
Therefore we have

lim n→∞ H(Y ρ n |X n ) H(X n ) = h ∞ (π ρ ) -h ∞ (µ) h ∞ (µ) -→ ρ→0 0,
ruling out partial entropy noise sensitivity.

Remark 4.4. Noise sensitivity in average distance does not imply Liouville property. Indeed for the simple random walk on the free group F 2 , one easily computes

Ed F 2 (X n , X n ) ∼ n ∼ Ed F 2 (X n , Y ρ n )
for any ρ > 0. It follows that average distance noise sensitivity does not imply large scale noise sensitivity.

Finite and abelian groups

5.1. Finite groups.

Proposition 5.1. Any finite group is 1 -noise sensitive, entropy noise sensitive and noise sensitive in average distance with respect to any generating probability measure.

Proof : The measure

π ρ := (1 -ρ)µ diag + ρµ 2 is generating of G 2 , so π ρ n satisfies π ρ n -unif G 2 1 ≤ β n 1
for some β 1 < 1 (see e.g. Saloff-Coste ( 2004)). Similarly µ 2 n -unif G 2 1 ≤ β n 2 for some β 2 < 1. Therefore the random walk in G is 1 -noise sensitive, with total variation converging exponentially fast to zero.

Since the set G is finite, it follows that

H(π ρ n ) → H(unif G 2 ) = 2H(unif G ) and H(µ n ) → H(unif G
). This implies entropy noise sensitivity.

Moreover let Z denote a uniformly random variable in

G, it is immediate that |Ed G (X n , X n ) - Ed G (e, Z)| ≤ diam(G) µ n -unif G 1 and |Ed G (X n , Y ρ n ) -Ed G (e, Z)| ≤ diam(G) ( µ n -unif G 1 + π ρ n -unif G 2 1 )
. By 1 -noise sensitivity, both converge to zero, whence distance noise sensitivity. This result is not surprising since we defined noise sensitivity only asymptotically. An interesting further question is whether it is possible that noise sensitivity manifests itself before cut-off, that is before the random walk seems equidistributed. However we will not pursue in this direction. 5.2. Infinite abelian groups. In abelian groups, computations are explicit, based on the local central limit theorem.

Proposition 5.2. Let G be an infinite finitely generated abelian group and µ be any finitely supported probability measure. Then

• (G, µ) is entropy noise sensitive,

• (G, µ) is not, even partially, noise sensitive in average word distance,

• (G, µ) is not 1 -noise sensitive.

The proof of the first point is based on the following folklore lemma.

Lemma 5.3. Let X n be a random walk on Z d with step distribution µ finitely supported and generating. Then

H(X n ) = d 2 log n + o(log n).
Proof of Lemma 5.3: We denote m = EX 1 . We fix ε > 0. The central limit theorem gives K such that

P(|X n -nm| ≤ K √ n) ≥ 1 -ε. Then H(X n ) = H(X n ||X n -nm| ≤ K √ n)P(|X n -nm| ≤ K √ n) + H(X n ||X n -nm| > K √ n)P(|X n -nm| > K √ n) + h 1 , (5.1)
where 0 ≤ h 1 ≤ log 2 is the entropy of the conditioning partition. The local central limit theorem [START_REF] Davis | An elementary proof of the local central limit theorem[END_REF]; [START_REF] Lawler | Random walk: a modern introduction[END_REF] provides two constants c 1 , c 2 > 0 depending only on K such that for all n large enough, for all |x -nm| ≤ K

√ n, c 1 n d 2 ≤ P(X n = x||X n -nm| ≤ K √ n) ≤ c 2 n d 2
(5.2)

It follows that for n large enough

d 2 log(n) + log 1 -ε c 2 = log (1 -ε)n d 2 c 2 ≤ H(X n ||X n -nm| ≤ K √ n) ≤ d 2 log(n) + log 1 -ε c 1 (5.3)
and the lower bound together with (5.1) give lim inf H(Xn) log n ≥ d 2 .

On the other hand, as X n is confined in a ball of radius Cn and of volume at most C n d , we have

H(X n ||X n -nm| > K √ n) ≤ log(C n d ) = d log(n) + log(C ).
For n large enough, we deduce with (5.1) and (5.3)

H(X n ) ≤ (1 -ε) d 2 log(n) + εd log(n) + C
which gives lim sup H(Xn) log n ≤ d 2 . Proof of Proposition 5.2: Such a group G is isomorphic to Z d × F for some finite abelian group F . Lemma 5.3 still holds in this more general setting for the finite group F contributes at most a constant to entropy.

We first prove entropy noise sensitivity, we have to show lim

H(Y ρ n |Xn) log n = d 2 . The inequality H(Y ρ n |X n ) ≤ H(X n )
provides the upper bound. Let be the number of refreshed variables in Y ρ n . Given , we can write

(X n , Y ρ n ) = (X n-X , X n-X )
where X and X are independent, of law µ . They are also independent of X n-which has law µ n-. As follows a binomial law B(n, ρ), we have for any ε > 0

P(A ε ) = P( ∈ [(ρ -ε)n, (ρ + ε)n]) -→ n→∞ 1
(5.4)

where we denote

A ε = { ∈ [(ρ -ε)n, (ρ + ε)n]}.
As further conditioning does not increase entropy, we have the lower bound

H(Y ρ n |X n ) = H(X n-X |X n ) ≥ H(X n-X |X n , X n-, ) = H(X |X n , X n-, ) = H(X | ). It follows that H(Y ρ n |X n ) ≥ n k=0 H(X k )P( = k) ≥ n k=(ρ-ε)n H(X k )P( = k) ≥ H(X (ρ-ε)n )P( ≥ (ρ -ε)n)
and thus by Lemma 5.3 and (5.4)

H(Y ρ n |X n ) ≥ d 2 log((ρ -ε)n) + o(log n) (1 + o(1)) = d 2 log n + o(log n)
which is the required lower bound to get entropy noise sensitivity.

Regarding the spread, there exist two constants c 3 , c 4 > 0 depending only on µ such that

c 3 √ n ≤ Ed G (X n , X n ) ≤ c 4 √ n.
(5.5)

Conditioning as above by the number of refreshed variables, we have

Ed G (X n , Y ρ n ) = Ed G (X n-X , X n-X ) = Ed G (X , X ) = Cn k=0 E d G (X , X )| = k P( = k)
where C = 2 max{d G (e, x)|x ∈ suppµ}. By splitting the sum at (ρ + ε)n for arbitrary ε > 0 and using (5.4), we get

Ed G (X n , Y ρ n ) ≤ c 4 (ρ + ε)nP( ≤ (ρ + ε)n) + c 4 √ CnP( > (ρ + ε)n) = c 4 √ ρ + ε √ n(1 + o(1)).
With (5.5) we deduce that

lim sup n→∞ Ed G (X n , Y ρ n ) Ed G (X n , X n ) ≤ c 4 c 3 √ ρ -→ ρ→0 0.
This rules out partial noise sensitivity in average word distance, and thus 1 -noise sensitivity by Proposition 3.5.

Corollary 5.4. Let (G, µ) be a group with a surjective homomorphism G Z and µ finitely supported, then (G, µ) is not 1 -noise sensitive.

Proof : It follows from Proposition 5.2 because 1 -noise sensitivity is preserved under taking quotients G Ḡ (for the induced measure): if µ 1 , µ 2 are two measures on G, then μ1 -μ2 1 ≤ µ 1 -µ 2 1 .

Product groups.

Proposition 5.5. Let G 1 , G 2 be two finitely generated groups with probabilities µ 1 and µ 2 respectively. If both (G 1 , µ 1 ) and (G 2 , µ 2 ) are noise sensitive in the sense of one definition of section 2, then (G 1 × G 2 , µ 1 × µ 2 ) is noise sensitive as well in this definition.

Proof : It follows straightforwardly from the definitions.

The choice of product probability measure is important here, because noise sensitivity notions may depend on the choice of probability. It is the case for 1 -noise sensitivity and noise sensitivity in average distance by Corollary 6.3.

The infinite dihedral group

Let D ∞ = a, b|a 2 = b 2 = 1 denote the infinite dihedral group. The random walk on D ∞ driven by 1 2 (δ a + δ b ) is called simple. The random walk driven by 1 3 (δ e + δ a + δ b ) is called lazy simple. Theorem 6.1. Let D ∞ be the infinite dihedral group.

• The simple random walk on D ∞ is not 1 -noise sensitive.

• The lazy simple random walk on D ∞ is 1 -noise sensitive.

The Cayley graph of D ∞ with respect to the generating set {a, b} is a line, so it coincides with the Cayley graph of Z. Therefore random walks on D ∞ are related to random walks on the integers, which explains the first statement. However the edge labelings are very different. This difference will be key to the second statement.

Corollary 6.2. The simple random walk on D ∞ is not noise sensitive in average word distance. The lazy simple random walk on D ∞ is noise sensitive in average word distance.

Proof of Corollary 6.2: The first statement is justified below in the proof of Theorem 6.1. The second statement follows from Proposition 3.5.

Note that both simple and lazy simple random walks on D ∞ are entropy noise sensitive by the same argument as in abelian case.

Corollary 6.3. The 1 -noise sensitivity and the noise sensitivity in average word distance are not group properties but depend on the probability measure. A fortiori they are not preserved under quasi-isometries. Corollary 6.4. For any positive integer d, there exists a group commensurable with Z d which is

1 -noise sensitive for some probability measure.

Proof : Take a direct product D d ∞ and use Proposition 5.5. Remark 6.5. Theorem 6.1 shows that virtually abelian groups may be 1 noise sensitive. Informally, this is due to the noise sensitivity of the action of the finite quotient on the torsion free subgroup. It is obvious that if we are given a trajectory in the streets of New York by a sequence of moves North-South-East-West and we misread one instruction, we will still end up close to the aim. However if the instructions are given in terms of Forward-Backward-Left-Right and we miss a turn, we will most likely end up very far from the aim. It would be interesting to understand precisely when a virtually abelian group is noise sensitive or not. 6.1. Couplings of (lazy or not) simple random walks on Z. We record here three lemmas that will be used in the proof of Theorem 6.1. The first one is very classical and the other two are easy consequences.

Lemma 6.6. Let S n , resp. S n , denote a (lazy or not) simple random walk on Z started at 0, resp. at x √ n. There exists σ = σ x ∈ {0, 1}, such that

lim sup n→∞ ||law(S n ) -law(S n -σ)|| 1 -→ x→0 0.
For lazy simple random walks, this holds true with σ = 0.

Proof : Let us start with the case of (non lazy) simple random walk. We assume x √ n is even and take σ = 0. The case x √ n odd and σ = 1 is similar. We consider the following coupling of S n and S n : while S k = S k , sample the increments independently, once S k S k take the same increments. This ensures that S k = S k for any k ≥ T = min{k :

S k = S k }. We have ||law(S n ) -law(S n -σ)|| 1 ≤ 2P(T > n).
Now while k ≤ T , the random variable S k -S k has the law of a random walk with step distribution

1 2 δ 0 + 1 4 δ 2 + 1 4 δ -2 . Then P(T > n)
is the probability that such a random walk, starting at the even integer x √ n, does not hit 0 by time n. The later tends to 0 with x by Révész (2013, Theorem 2.13). For lazy simple random walks, the random variable S k -S k has a step distribution charging positively each increment in {-2, -1, 0, 1, 2}, and it can hit 0 as above without parity issue.

We will actually rather use the proof than the lemma, and we call the coupling above the standard coupling between two simple random walks on Z started at different positions. Lemma 6.7. Let S n , resp. S n , denote a (lazy or not) simple random walk on Z started at 0, resp. at x √ n, and let δ ∈ R. There exists σ ∈ {0, 1} such that

lim sup n→∞ ||law(S n ) -law(S (1+δ)n -σ)|| 1 -→ 0
when both x and δ tend to 0. This holds true with σ = 0 for lazy simple random walks.

Proof : This is a consequence of the previous lemma. We consider only the (non lazy) simple random walk and assume that δ > 0 and that both x √ n and δn are even. Similar arguments apply in the other cases. We first sample S δn . By the central limit theorem, for any ε > 0, there exists A > 0 such that for n large

P |S δn | ≤ A √ δn ≥ 1 -ε.
Conditioning on this event, we apply Lemma 6.6 to S n and S -1 δn S (1+δ)n which is starting at x √ n with x -Aδ ≤ x ≤ x + Aδ. The probability to achieve their standard coupling is greater than 1 -ε as long as x and δ are small enough. It follows that the probability to couple S n and S (1+δ)n is at least 1 -2ε for n large.

In order to ease notations, we write [a ± b] as a shortcut for the interval [a -b, a + b]. Lemma 6.8. Assume + , -∈ 4 9 ± δ n and ∈ [(1 ± δ)n], then for any given integer s,

lim sup n→∞ 1 2 δ 1 + 1 2 δ -1 * + * 1 2 δ 0 + 1 4 δ 1 + 1 4 δ -1 * - -δ s * 1 3 δ 0 + 1 3 δ 1 + 1 3 δ -1 * 1 -→ δ→0 0.
We could replace s by x √ n with x tending to 0 but this will not be necessary. There is no shift σ = 0 because of the lazy aspect of the random walk.

Proof : Fix ε > 0. Set µ S = 1 2 δ 1 + 1 2 δ -1 and µ LS = 1 3 δ 0 + 1 3 δ 1 + 1 3 δ -1 . Then 1 2 δ 1 + 1 2 δ -1 ba -2 b -1 e 0 a 1 ab 2 a +1 a -1 a +1 a -1 b +1 b -1 b +1 b -1 • • • • • • Figure 6.1. Cayley graph of D ∞ and identification with Z. with 1 -ε ≤ P m ∈ 3 4 ± δ -≤ P m ∈ 1 3 ± 2δ n for n large. Similarly we have δ s * µ * LS = δ s * µ
started at most 1 apart, gives a probability no less than 1 -ε that the two considered random walks achieve coupling. We conclude that

1 2 δ 1 + 1 2 δ -1 * + * 1 2 δ 0 + 1 4 δ 1 + 1 4 δ -1 * - -δ s * 1 3 δ 0 + 1 3 δ 1 + 1 3 δ -1 * 1 ≤ 4ε
provided δ is small enough and n large.

6.2. Proof of Theorem 6.1. Let us now describe precisely the labelling of the Cayley graphs of Z and D ∞ , pictured in Figure 6.1. In the integers, from each vertex there is an edge to the right labelled by +1 and and edge to the left labelled by -1. In the dihedral group, let us say that the words (ab) k correspond to even positions and the words (ab) k a to odd positions. At each even position, there is an edge to the left labelled by a and an edge to the right labelled by b. At each odd position, this is the converse.

Proof of the first part of Theorem 6.1: For the simple random walk, the key observation is that position X n and time n have the same parity. The path parametrized by X n corresponds to a random walk on the integers where the increments at odd times are +1 for a and -1 for b, and the increments at even times are +1 for b and -1 for a. This provides a simple random walk on the integers, which is neither 1 -noise sensitive nor noise sensitive in average word distance by Proposition 5.2.

For lazy random walks, time and position no longer have the same parity. Let us first observe the effect of refreshing one increment. Denote X n = v 0 sv 1 and Y n = v 0 rv 1 with s, r independent, µ-distributed in {a, b, e}. By abuse of notation, we denote X n = v 0 + s + v 1 the corresponding path in the integers, as above.

When s ∈ {a, b} and r = e (or vice-versa), it corresponds in the integers to s = ±1 (the sign depends on the parity of v 0 ) being replaced by r = 0 (or vice-versa). Thus v 0 s and v 0 r have different parity, so the next moves of the random walk, described by the word v 1 , will be mirrored of the moves in the original walk. We write

Y n = v 0 + r -v 1 .
When s = a and r = b (or vice-versa), then s = ±1 (depending on v 0 ) is replaced by r = ∓1. The parity is not modified and we write

Y n = v 0 + r + v 1 . L 0 α i = -α i-1 α i = α i-1 s i ∈ D ∞ e a b e e a a b b r i ∈ D ∞ e e e a b a b a b even position s i ∈ Z 0 1 -1 0 0 1 1 -1 -1 r i ∈ Z 0 0 0 1 -1 1 -1 1 -1 odd position s i ∈ Z 0 -1 1 0 0 -1 -1 1 1 r i ∈ Z 0 0 0 -1 1 -1 1 -1 1 Figure 6.2.
Correspondence of the effect of noising in the dihedral and integer model. The position is the integer

v 0 + • • • + s j i-1 + v i-1
, as in (6.1).

Now denote X n = v 0 s j 1 v 1 s j 2 . . . s jm v m a lazy simple random walk where s j i are the increments to be refreshed and v i = s j i +1 . . . s j i+1 -1 are words. With the notations above, it corresponds to a sum

X n = v 0 + s j 1 + v 1 + s j 2 + v 2 • • • + s jm + v m (6.1) in the integers. The refreshed sample Y ρ n = v 0 r j 1 v 1 . . . r jm v m corresponds to a sum Y ρ n = α 0 v 0 + r j 1 + α 1 v 1 + r j 2 + α 2 v 2 • • • + r jm + α m v m (6.2)
where α i = ±1 are given by α 0 = 1 and α i = -α i-1 if and only if s i ∈ {a, b} and r i = e or vice-versa, i.e. there is a change of parity, which occurs with probability 4/9. This is summarised in Table 6.2. At this stage, we can get an intuition of the result because the sum r j is actually independent of the sum s j and the Lyapunov central limit theorem applied to the random variables ±v i ensures that the sums v i and α i v i are essentially independent. Making this precise would prove noise sensitivity at large scale.

However, to obtain 1 convergence, we need to construct a coupling between (X n , Y ρ n ) and (X n , X n ). For this, we will use the additive model of expressions (6.1) and (6.2).

Proof of the second part of Theorem 6.1: Let us first explain how we sample (X n , Y ρ n ) in the integer model (6.1,6.2). We first sample the locations L of the refreshed increments, according to a Bernoulli law of parameter ρ. Among L, we sample the locations L 0 where (s i , r i ) = (e, e) (or (s i , r i ) = (0, 0) in the integer model), according to a Bernoulli law of parameter 1 9 . Then we sample the v i , i.e. the increments s i for i not in L according to 1 3 (δ e + δ a + δ b ). Then we sample the values of α i according to a Bernoulli law of parameter 1 2 . This partitions L \ L 0 into L + α L - α . Finally, we sample the pairs (s i , r i ) according to 1 4 (δ (1,-1) + δ (1,1) + δ (-1,1) + δ (-1,-1) ) for i in L + α and according to 1 4 (δ (1,0) +δ (-1,0) +δ (0,1) +δ (0,-1) ) for i in L - α . In view of Table 6.2, this yields a sample of (X n , Y ρ n ) in the integer model. Now we explain how to couple (X n , Y ρ n ) with (X n , X n ). More precisely, we will couple the conditioned law (Y ρ n |X n ) with X n (which is equal to (X n |X n ) by independence) on a large enough subset.

We first sample the subsets L and L 0 , thus we have integer expressions of X n and Y ρ n as in (6.1,6.2). We will mimic these expressions for X n and write it in the form

X n = v 0 + s j 1 + v 1 + s j 2 + v 2 • • • + s jm + v m + i∈L 0 s i
where v i = i∈{j i +1,...,j i+1-1 }\L 0 s i . In other words, we pull out the terms in L 0 . Then we will call length of v i , and denote by (v i ), the cardinal of the set {j i + 1, . . . , j i+1 -1} \ L 0 . This choice makes sure that (v i ) = (v i ) for all i. This length follows a geometric law of parameter 1-8 9 ρ 1-1 account the specificity of L 0 ). It follows that for any integer k ≥ 0 there is a constant c k > 0 such that for any δ > 0

P [#{i : (v i ) = k} ∈ [(c k ± δ)n]] -→ n→∞ 1. (6.3)
In order to construct a coupling between (X n , Y ρ n ) and (X n , X n ), we will take advantage of commutativity of the addition of integers in order to decompose the conditioned process (Y ρ n |X n ) and X n into a finite sequence of independent rescaled simple random walks, run during close times. For this, we fix an integer K to be determined later and define:

X long n = {i: (v i )>K} v i and X short n = K k=0 {i: (v i )≤K,|v i |=k} v i = K k=0 kS (k) m(k) (6.4)
and similarly

Y long n = {i: (v i )>K} α i v i and Y short n = K k=0 {i: (v i )≤K,|v i |=k} α i v i = K k=0 kS (k) m(k) (6.5)
where m(k) is the cardinal of the subset {i : (v i ) ≤ K, |v i | = k}. The sum of the v i 's on the latter subset has the law of a simple random walk, which we denote S (k) m(k) , rescaled by the multiplicative factor k. As the α i 's are independent uniform on {±1}, the sum of the α i v i 's indexed by this very subset is an independent simple random walk S (k) m(k) . We also denote

X α+ n = j∈L + α s j , X α- n = j∈L - α s j , Y α+ n = j∈L + α r j , Y α- n = j∈L - α r j ,
in order to have

X n = X long n + X short n + X α+ n + X α- n and Y ρ n = Y long n + Y short n + Y α+ n + Y α- n . Similarly we decompose X n = X long n + X short n + X α+ n + X α- n + X 0 n into X long n = {i: (v i )>K} v i , X short n = K k=0 {i: (v i )≤K,|v i |=k} v i = K k=0 kS (k) m (k) ,
and

X α+ n = j∈L + α s j , X α- n = j∈L - α s j , X 0 n = j∈L 0 s j ,
Using (6.3) and the distributions of the v i 's conditioned by their lengths, we obtain for each k ≥ 0 a constant c k > 0 such that for any δ > 0 and n large

P m(k) ∈ (c k ± δ)n -→ n→∞ 1 (6.6)
and the same holds for m (k). Observe that c 1 > c 1 . Also note that by (6.3) and tail decay of the geometric law, there exists a sequence ε K -→ K→∞ 0 such that

P (X long n ) ≤ ε K n -→ n→∞ 1 (6.7)
where

(X long n ) = i: (v i )>K (v i ) is the length of X long n
as a word (we removed the trivial increments in L 0 ).

We are now ready to describe the required coupling. We fix some ε > 0. By Lemma 6.7, there exists x, δ > 0 such that any two simple random walks started distance ≤ x √ n apart and run for times in [(1 ± δ)n] achieve a standard coupling with probability at least 1 -ε, provided n is large enough. Moreover by the central limit theorem applied to a (lazy or not) simple random walk S n , there exists A > 0 such that for n large

P |S n | ≤ A √ n ≥ 1 -ε.
We choose K large enough that

4A √ ε K c 1 ≤ x.
The central limit theorem and (6.7) show that

P |X long n | ≤ A √ ε K n ≥ 1 -ε and the same inequality holds with Y long n or X long n in place of X long n . Let B 0 = {|Y long n | > A √ ε K n}∪ {|X long n | > A √ ε K n} denote the "
bad" set at step 0. We have P(B 0 ) ≤ 2ε.

We also choose

δ 1 > 0 such that δ 1 c 1 ≤ δ. We set B 1 = {m(1) / ∈ [(c 1 ±δ 1 )n]}∪{m (1) / ∈ [(c 1 ±δ 1 )n]}. Applying (6.6) with k = 1, we have P(B 1 ) ≤ 2ε K provided n is large enough. Conditioned on X n and on B 0 ∩ B 1 , the random variables Y long n + S (1) m(1) and X long n + S (1) m (1) are simple random walks started distance |Y long n -X long n | ≤ 2A √ ε K √ n apart and run for times m(1), m (1) ∈ [(c 1 ± δ 1 )n] ⊂ [(1 ± δ)c 1 n] by choice of δ 1 .
The choice of K permits to use Lemma 6.7 and we obtain for n large

P |Y long n + S (1) m(1) -(X long n + S (1) m (1) )| ≤ 1 B 0 ∩ B 1 , X n ≥ 1 -ε.
(6.8) Now we will use Lemma 6.7 repeatedly as follows. For ε = ε K > 0, there exists δ > 0 such that two simple random walks started distance at most 1 apart and run for times in [(1 ± δ )n] achieve a standard coupling with probability at least

1 -ε . For each 2 ≤ k ≤ K, we choose δ k > 0 with δ k c k ≤ δ . We denote B k the "bad" event that {m(k), m (k)} is not included in [(c k ± δ k )n].
For n large enough, we have P(B k ) ≤ 2ε by (6.6), so the "bad" event B = ∪ K k=0 B k has probability P(B) ≤ 4ε and thus P(B ) ≥ 1 -4ε.

Let us denote G k the "good" event at step k, still conditioned by X n , that

G k = Y long n + S (1)
m(1) + • • • + kS (k) m(k) -X long n + S (1)
m (1) + • • • + kS (k) m (k) ≤ 1 |X n Inequality (6.8) implies P(G 1 |B , X n ) ≥ 1 -ε.
We also have:

∀2 ≤ k ≤ K, P(G k |B , G k-1 , X n ) ≥ 1 -ε .
Indeed under the conditions X n , G k-1 and B , the event G k has the probability that two simple random walks started at most 1 apart and run for times

m(k), m (k) ∈ [(c k ± δ k )n] ⊂ [(1 ± δ )c k n]
achieve a standard coupling, which holds for n large with probability no less than 1 -ε by choice of δ . It follows that

P(G K |B , X n ) ≥ 1 -ε -(K -1)ε ≥ 1 -2ε. (6.9)
There remains to consider the contributions of the pairs (s i , r i ) for i ∈ L \ L 0 and of s i for i ∈ L. Note that as the values of α i 's have been sampled (which guaranteed the independence of S

B α = #L + α / ∈ 4ρ 9 ± δ α n ∪ #L - α / ∈ 4ρ 9 ± δ α n ∪ #L 0 / ∈ ρ 9 ± δ α n
the "bad" event that the partition L = L + α L - α L 0 is not "generic". We have for any δ > 0 and n large that P(B α ) ≥ 1 -ε.

According to Table 6.2, the laws of

Y α n + and Y α- n conditioned by B α , X n , L + α , L - α are 1 2 δ 1 + 1 2 δ -1 * #L + α and 1 2 δ 0 + 1 4 δ 1 + 1 4 δ -1 * #L - α respectively. The law of X α+ n + X α- n + X 0 n is 1 3 δ 0 + 1 3 δ 1 + 1 3 δ -1 * #L .
the local time at x (both the set and its cardinal are called local time by a slight abuse). Conditioned on the local time, the state of the lamp at x is given by:

f n (x) = t∈Loc(x,n)
α t , where α t are i.i.d. uniform in Z/2Z.

Let us denote R n := {x ∈ Z : Loc(x, n) > 0} the range of the random walk projected to the integers. The entropy of X n is given by

H(X n ) = E|R n | + O(log n) (7.1)
because to describe X n we need to provide the lamp configuration on the range and the position (which has only logarithmic entropy). Note that we use logarithm in base 2. It is well-known that E|R n | √ n. Moreover, by gaussian decay, the expected size of range is homogeneous in the sense that for n large, one has

E1 A |R n |/E|R n | ≤ f (P(A)) for some function f (ε) -→ ε→0 0.
Now consider a refreshed sample Y ρ n = r 1 . . . r n = (g n , y n ). Again conditioning by the trajectory projected onto the integers, it appears that the conditional entropy satisfies

H(Y ρ n |X n ) ≥ E|R ref n (Y ρ n )|, (7.2) where R ref n (Y ρ n ) := {x ∈ R n (Y ρ n ) : ∃t ∈ Loc(x, n
), r t = s t was refreshed}, because for x in this set of refreshed lamps, the value g n (x) is independent of the sample X n . Moreover, for a given x in the range of Y ρ n , the probability that the lamp is not refreshed is precisely (1 -ρ) Loc(x,n) , so our conditional entropy is related to the distribution of local time. The Ray-Knight theorem guarantees that

P # x ∈ R n : Loc(x, n) ≤ δ √ n ≤ δ √ n -→ δ→0 1.
So for any ε > 0, there exists an δ > 0 such that the event

A δ := # x ∈ R n (Y ρ n ) : Loc(x, n) ≥ δ √ n ≥ (1 -ε) |R n (Y ρ n )| has probability P(A δ ) ≥ 1 -ε.
In this set each lamp is refreshed with probability at least 1 -(1ρ) δ √ n ≥ 1 -ε, provided n is large enough, so:

P |R ref n (Y ρ n )| ≥ (1 -2ε) # x ∈ R n (Y ρ n ) : Loc(x, n) ≥ δ √ n -→ n→∞ 1.
It follows that conditioned on A δ we have for n large:

P |R ref n (Y ρ n )| ≥ (1 -3ε) |R n (Y ρ n )| |A δ ≥ 1 -ε. Denote B the event that |R ref n (Y ρ n )| ≥ (1 -3ε) |R n (Y ρ n )|
, we finally have P(B) ≥ 1 -2ε for n large. We can compute:

E|R ref n | = E1 B |R ref n | + E1 B |R ref n | ≥ (1 -3ε)E1 B |R n | ≥ (1 -3ε)(1 -f (2ε))E|R n |.
Together with (7.1) and (7.2), this implies entropy noise sensitivity.

The distance between two elements (f, x) and (g, y) is the minimal number of steps for the lighter to start from position x, switch all lamps at positions t with f (t) = g(t) and go to position y. In particular,

Ed(X n , Y ρ n ) ≥ E|R ref n (Y ρ n )| -o( √ n) √ n.
This implies partial noise sensitivity in average word distance. 7.2. A lower bound for permutational wreath products. The ideas in the previous proof can be used in arbitrary permutational wreath products, but it is usually difficult to obtain informations about local times. We give a weaker statement which will be used in the next section.

Given an action of G on S, recall that the inverted orbit of a point x in S under a word w = s 1 . . . s n is the set

O(w) = x, xs -1 1 , xs -1 2 s -1 1 , . . . , xs -1 n . . . s -1 1 .
A switch-walk measure on Λ S G is a measure of the form µ Λ * µ G where µ G is an arbitrary measure on G and µ Λ is an arbitrary measure on the copy of Λ siting over a fixed point o in S, namely Λ = {λδ o : λ ∈ Λ}.

Lemma 7.2. Let Λ be a finite group. A switch-walk random walk on Λ S G satisfies

H(Y ρ n |X n ) ≥ ρH(µ Λ )E |O(X n )|
. By slight abuse of notation, we write on the righthand side O(X n ) where we mean the inverted orbit of the inverse of a sample path (or word) of the random walk and not only its evaluation in the group. Heuristically this lemma is simply a lower bound on the expected number of lamps refreshed. In its own, it does not provide information on noise sensitivity because the righthand side depends on the noise parameter ρ.

Proof : Let X word n = λ 1 δ o s 1 . . . λ n δ o s n denote a sample path of the random walk with evaluation X n = (f n , g n ) in the group Λ S G. The lamp at x takes value

f n (x) = λ 1 δ o (x)λ 2 δ o (xs 1 ) . . . λ n δ o (xs 1 . . . s n ) = t∈Loc(x,n) λ t ,
where Loc(x, n) := {0 ≤ t ≤ n : x.s 1 . . . s t-1 = o} and λ t are independent of law µ Λ . Note that points with positive local time are precisely points on the inverted orbit of X word n . Now to sample Y ρ n , we first sample the locations of refreshed increments, then resample only the µ G factors of the increments. This gives an intermediate word Y word n whose evaluation Y n in the group individually has the same law as X n . Then we refresh the µ Λ factors of the increments. We have :

H(Y ρ n |X n ) ≥ H(Y ρ n |X word n ) ≥ H(Y ρ n |X word n , Y word n ) = H(Y ρ n |Y word n
). The last equality is due to the fact that all the factors in the word X word 7.3. Permutational wreath products of some groups acting on rooted trees. Let T = T d be a rooted tree of degree d. We view it as the graph with vertex set ≥0 X where X = {1, . . . , d} and edges between any two vertices of the form v and vx for x ∈ X. The root is the empty sequence obtained for = 0, and the set X is called the th level. The tree boundary is the set ∂T = X Z + . The group Aut(T ) of (rooted) automorphisms of T is canonically isomorphic to its permutational wreath product with the symmetric group S X over X

Aut(T ) Aut(T ) X S X . (7.3)
This is obtained by identification between T and the subtrees xT rooted at vertices x in the first level. We identify an element and its image under this isomorphism to write g = g| 1 , . . . , g| d σ where g| x ∈ Aut(T ) is called the section at x and σ ∈ S X is the root permutation. The action of g ∈ Aut(T ) on a vertex of the form xu for x ∈ X is given by g.xu = σ.xg| x u. The product rule is gg = g| 1 g| σ -1 (1) , . . . , g| d g| σ -1 (d) σσ . This isomorphism can be iterated to the th level as

Aut(T ) Aut(T ) X S X X • • • X S X → Aut(T ) X S X ,
and in particular, the section of g at any vertex is defined by induction as g| vx = (g| v )| x We refer to [START_REF] Grigorchuk | Just infinite branch groups[END_REF] or [START_REF] Nekrashevych | Self-similar groups[END_REF] for details on the structure of Aut(T ) and wreath product isomorphisms. We consider a finitely generated subgroup G = G(A, H) of Aut(T ) with a generating set of the form A ∪ H where A and H are two subgroups such that • all the elements of A are rooted, i.e. have all their sections of the first level trivial, and A acts transitively on the first level, • all the elements of H have the form h = h| 1 , . . . , h| d σ with sections h| 1 ∈ H and h| x ∈ A for all x ∈ X \ {1} and permutation fixing 1, i.e. σ1 = 1. • let u H and u A denote respectively the uniform measure on H and A, we assume moreover that the first section map h → h| 1 pushes u H forward to u H itself, and that the other section maps h → h| x for x ∈ X \ {1} push u H forward to u A (this together with transitivity of the A-action on X implies in particular that the image of G under the section map g → g| v is G itself, and this for any vertex v). Recall that the first Grigorchuk group is the group acting on a binary rooted tree generated by four elements recursively defined by a = e, e (12), b = c, a , c = d, a and d = b, e . It satisfies this set of hypotheses by putting A = {e, a} and H = {e, b, c, d}. Other classical exemples covered by our hypotheses are the various Grigorchuk groups [START_REF] Grigorchuk | Degrees of growth of finitely generated groups and the theory of invariant means[END_REF][START_REF] Grigorchuk | On the growth degrees of p-groups and torsion-free groups[END_REF], as well as generalisations in [START_REF] Bartholdi | On the word and period growth of some groups of tree automorphisms[END_REF], and mother automata groups of degree 0 introduced in [START_REF] Bartholdi | On amenability of automata groups[END_REF].

We now consider some specific permutational wreath products Λ S G of a group G = G(A, H) with a finite group Λ over the set S = G.1 ∞ ⊂ ∂T , which is the orbit of the boundary point 1 ∞ under the action of G. This group is generated by A ∪ H ∪ Λ where we identify Λ with the subgroup {λδ 1 ∞ : λ ∈ Λ} where λδ 1 ∞ (x) takes value λ at x = 1 ∞ and e elsewhere. Under identifications of the tree boundaries ∂T = x∈X ∂xT , the isomorphism (7.3) extends to the action on the boundary and we obtain an embedding

Λ S G(A, H) → (Λ S G(A, H)) X A.
Notice that under this embedding λδ 1 ∞ = λδ 1 ∞ , e, . . . , e . Moreover it is immediately checked that H and Λ commute. For such groups, we have: Theorem 7.3. Let G = G(A, H) be as above and let Λ be a finite group. The random walk (Λ S G, u ΛH * u A ) is partially entropy noise sensitive.

The measure u ΛH * u A = u Λ * u HA was called "switch and walk" in the statement of Theorem 1.3. This theorem applies for instance to extensions of the Grigorchuk groups introduced by Bartholdi and Erschler, and which can have prescribed growth, see [START_REF] Bartholdi | Growth of permutational extensions[END_REF]; [START_REF] Brieussel | Growth behaviors in the range e r α[END_REF]; [START_REF] Bartholdi | Groups of given intermediate word growth[END_REF]. For simplicity we have decided to restrict ourselves to the case of tree of constant degree, but this hypothesis is unnecessary and the arguments of the proof below apply to rooted trees with bounded degree. Such generalisations provide interesting groups with prescribed entropy when Λ is finite and prescribed speed when Λ = Z, see [START_REF] Brieussel | Behaviors of entropy on finitely generated groups[END_REF]; [START_REF] Amir | Speed exponents of random walks on groups[END_REF].

Proof : For these groups, Amir and Virág (2017, Inequality (9) and Corollary 24) have shown that the entropy of the random walk satisfies

cE |O(X n )| ≤ H(X n ) ≤ CE |O(X n )| (7.4)
where O(X n ) is the inverted orbit of 1 ∞ and the constants c, C depend only on the degree of the tree.

We will also use Brieussel (2013, Proposition 3.8) that the size of the inverted orbit is the sum of that of the sections |O(

X n )| = d x=1 |O(X n | x )|.
By induction, we deduce that for any level

|O(X n )| = v∈X |O(X n | v )|. (7.5)
Let us first understand a section X n | x of the first level. By Brieussel (2013, Lemma 4.1), for each 1 ≤ x ≤ d, the random word on the section at x has the form

X n | x = b x 1 a x 1 b x 2 . . . b x s a x s
where the factors a x r are uniform in A and the factors b x r are uniform in ΛH. These factors are all independent and their number s follows a binomial law B(n, d-1 d 2 ). In particular, the u ΛH * u A random walk induces (slowed down) u ΛH * u A random walks on the sections.

More precisely, if we denote an increment of X n by s i = b i a i with a i uniform in A and b i = λ i δ 1 ∞ h i , a i2 , . . . , a id 0 π i uniform in ΛH, then each factor b x j of the section X n | x is a product of exactly k factors of the form λ i δ 1 ∞ h i with probability 1 d . This is so because for each i the independent factor a i resamples which section will receive the increment in ΛH (the unique section at 1.X -1 i-1 ), while the d -1 other sections will receive an increment in A. (Note that this is not true for the last factor of X n | x because of time truncation.)

We will now consider the refreshed sample Y ρ n . As in the proof of Lemma 7.2, we consider the word Y word ) is bounded below by the expected number of sites in S where the lamps will be refreshed. The key point is that the refreshing parameter ρ increases under taking sections.

Let us denote an increment of Y word n by s i = b i a i , where the factor a i is uniform in A and b i = λ i δ 1 ∞ h i , a i2 , . . . , a id 0 π i is uniform in ΛH. By the above discussion, each factor λ x j of the section Y word

ρ 1 = ∞ k=1 (1 -(1 -ρ) k ) 1 d k d -1 d = 1 - 1 -ρ 1 + ρ d-1 > ρ.
By induction, we deduce that for any initial ρ > 0, there exists a level at which the refreshing parameter of u Λ -factors is ρ ≥ Using the partition (7.5) and inequalities (7.4), we conclude that

H(Y ρ n |X n ) ≥ H(Y ρ n |Y word n ) ≥ v∈X ρ H(u Λ )E|O(X n | v )| ≥ 1 2 H(u λ )E|O(X n )| ≥ c 2 H(u Λ )H(X n ).
The choice of measure is heavily used in the proof to get similar random walks at the sections.

Remark 7.4. It would be interesting to have a similar result for the groups G(A, H) themselves rather than such permutational product extensions, for instance for the first Grigorchuk group. However it is difficult to describe precisely the effect of noise on the µ HA part. Indeed, not only does this resample the increments in one section but it also shuffles the increments between different sections of a given level. Heuristically, this means that the effect of noise in the sections is even stronger than simply "increasing the parameter", as was used in the proof above. We should also mention that the precise asymptotic behaviour of the entropy of (even simple) random walks on the first Grigorchuk group is still unknown.

Perspectives and questions

As mentioned in the introduction, our observations on noise sensitivity lead us to believe that the only obstructions to noise sensitivity are homomorphisms onto Z and non-Liouville property, whence Question 1.5 and Conjectures 1.6 and 1.7. We record here some questions and tasks for further study of noise sensitivity of groups.

1. Find more examples of 1 -noise sensitive groups.

• Clarify which virtually abelian (or more generally nilpotent) groups are 1 -noise sensitive, and for which measures. • Is the wreath product of a finite group with the dihedral group 1 -noise sensitive for some measure? If yes, it would provide an example with exponential growth. • Study noise sensitivity phenomena in other Liouville groups, such as degree 0 automata groups [START_REF] Amir | The Liouville property for groups acting on rooted trees[END_REF], degree 1 mother automata groups [START_REF] Amir | Amenability of linear-activity automaton groups[END_REF] or simple groups Matte Bon (2014); [START_REF] Nekrashevych | Palindromic subshifts and simple periodic groups of intermediate growth[END_REF].

• Find examples of strongly 1 -noise sensitive groups, i.e. noise sensitive with respect to any (finitely supported generating) probability measure. Possibly, this would be the case for any torsion or simple Liouville group. We expect this property to hold for the first Grigorchuk group. 2. Noise sensitivity could also be studied quantitatively.

• The choice of refreshing parameter ρ to be constant is arbitrary and it is natural to consider a parameter ρ(n) depending on the length n. There should be a threshold over which the noised random walk resembles an independent sample. Our definitions of noise sensitivity simply require that this threshold is tending to 0.

A lower bound is given by entropy consideration: the entropy of the noise should be no less than that of the independent sample: ρ(n)nH(µ) ≥ H(µ n ). However this is not enough in general (e.g. Z is not 1 -noise sensitive).

• Does partial 1 -noise sensitivity (∃c > 0, ∀ρ ∈ (0, 1), lim inf π ρ n -µ 2 n 1 ≤ 2 -c) imply Liouville property? 3. About entropy noise sensitivity:

• it is likely that the proof of Theorem 7.1 could be improved to show that when G is entropy noise sensitive, then G Z and G Z 2 are entropy noise sensitive as well. It would be a consequence of Conjecture 1.7. By Proposition 4.3, this is no longer true for wreath products with Z d for d ≥ 3 as they are non-Liouville. • Is it true that partial entropy noise sensitivity is equivalent to entropy noise sensitivity? 4. About the relationship between notions of noise sensitivity:

• Is it true that 1 -noise sensitivity implies entropy noise sensitivity?

• Is it true that large scale noise sensitivity implies noise sensitivity in average word distance?

• Are there random walks on groups not satisfying the homogeneity assumptions of Definitions 3.1 and 3.4? 5. About average distance noise sensitivity.

• Abelian groups are not (even partially) noise sensitive in average distance for any measure.

Are there other groups with this property ? • Is it possible that lim inf Ed G (Xn,Y ρ n ) Ed G (Xn,X n ) > 1?

  ) ), the locations L + α and L - α are determined already. For some δ α > 0, let us denote

n

  agree with the factors of Y word m except those that will be resampled according to µ Λ independently to obtain Y ρ n . For x in S, the lamp at x is refreshed from Y word n to Y ρ n with probability 1 -(1 -ρ) Loc(x,n) , which is ≥ ρ as soon as x has positive local time, i.e. is in the inverted orbit of Y word n . It follows that H(Y ρ n |Y word n ) ≥ ρH(µ Λ )E|O(Y word n )| = ρH(µ Λ )E O(X word n) .

  each factor a x j is a product of exactly k factors a ij with probability d-1 d k 1

n

  obtained by resampling the locations of the refreshments and the µ G = u H * u A part of the refreshed samples (but not yet the u Λ part). The conditioned entropy H(Y ρ n |Y word n

  n | x is a product of exactly k factors of the form λ i with probability 1 d k d-1 d . Such a product is refreshed with probability 1 -(1 -ρ) k (always, except if no factor is refreshed). It follows that in the word Y word n | x , the probability to refresh a u Λ -factor is

1 2 .

 2 Let v belong to level , the average number of points of O(Y word n | v ) ⊂ ∂vT where the lamps are refreshed is, as in the proof of Lemma 7.2, at least ρ E|O(Y word n | v )| = ρ E|O(X n | v )|.

Acknowledgements

We thank anonymous referees for useful comments. We also thank Gidi Amir and Ryokichi Tanaka for interesting discussions regarding noise sensitivity. We are especially grateful to Gidi Amir and an anonymous referee for pointing out an error in a previous version, and contribution to repair it.

Second Author has been partially supported by grant ANR 22-CE40-0004 GoFR. .

1139

Note that G

We apply Lemma 6.8 with |σ| ≤ 1, and obtain, provided δ α is small enough and n large,

Combined with (6.9), we get

Integrating over the condition X n , we get

Observe that in the proof above the parity issue between X n and Y ρ n can only be solved using the final "lazy"

Wreath products

Let G and Λ be two groups. Assume G acts transitively on a set S. The permutational wreath product of G and Λ over S is the semi-direct product

Its elements are pairs (f, g) where f : S → Λ is finitely supported and g belongs to G. The action of G on finitely supported functions is by translations gf (•) = f (•g). Given an arbitrary point o in S, a natural generating set is the union of elements (id, g) for g in some generating set of G together with elements (λδ o , id) for λ in some generating set of Λ where λδ o (x) = λ if x = o and λδ o (x) = id otherwise.

When S = G is acted upon by the right regular representation, we recover the (usual) wreath product and we simply denote it by Λ G.

7.1. The lamplighter group. The lamplighter group is the wreath product Z/2Z Z. Its elements are pairs (f, t) where t is an integer and f : Z → Z/2Z is a finitely supported function. As the action is by shift on Z, the product is

One can think of t as a position of a lighter and f as a space of configurations of lamps on or off. The group is generated by (0, ±1), which correspond to moves of the lighter, and (1δ 0 , 0), where 1δ 0 (x) takes value 1 for x = 0 and value 0 otherwise, which corresponds to switching on or off the lamp at the lighter's position. Let µ 1 be equidistributed on {(0, 0), (1δ 0 , 0)} and µ 2 be equidistributed on (0, ±1), then the measure µ := µ 1 * µ 2 * µ 1 is called the "switch-walk-switch" measure.

Theorem 7.1. The lamplighter group with switch-walk-switch measure is entropy noise sensitive and partially noise sensitive in average word distance.

This group is not 1 -noise sensitive by Corollary 5.4.

Proof : Let X n = s 1 . . . s n = (f n , x n ) denote a sample. The projection x n to the integers is a simple random walk. We denote Loc(x, n) := {0 ≤ t ≤ n : x t = x}