George Deligiannidis

Sébastien Gouëzel
email: sebastien.gouezel@univ-nantes.fr

Zemer Kosloff
email: zemer.kosloff@mail.huji.ac.il

S Ébastien

AND Gou Ëzel

The boundary of the range of a random walk and the Følner property

The range process Rn of a random walk is the collection of sites visited by the random walk up to time n. In this paper we deal with the question of whether the range process of a random walk or the range process of a cocycle over an ergodic transformation is almost surely a Følner sequence and show the following results: (a) The size of the inner boundary |∂Rn| of the range of recurrent aperiodic random walks on Z 2 with finite variance and aperiodic random walks in Z in the standard domain of attraction of the Cauchy distribution, divided by n/ log 2 (n), converges to a constant almost surely. (b) We establish a formula for the Følner asymptotic of transient cocycles over an ergodic probability preserving transformation and use it to show that for admissible transient random walks on finitely generated groups, the range is never a Følner sequence unless the walk is a skip-free random walk on Z. (c) For strongly aperiodic random walks in the domain of attraction of symmetric α-stable distributions with 1 < α ≤ 2, we prove a sharp polynomial upper bound for the decay at infinity of |∂Rn|/|Rn|. This last result shows that the range process of these random walks is almost surely a Følner sequence.

Introduction and main results

Let G be a countable group with identity element id G , ξ 1 , ξ 2 , . . . , be i.i.d. G-valued random variables and define the random walk (S n ) n , where S 0 := id G and

S n = ξ 1 • ξ 2 • . . . • ξ n for n ≥ 1.
The range of the random walk, denoted R n := {S 1 , . . . , S n }, is the random subset of G which consists of the sites visited by the random walk up to time n. The case where G = Z d will serve as a motivating and recurring example in this paper; as this group is Abelian we will denote the random walk in this case by S n = n i=1 ξ i . The range is a natural object to study and understanding its size and shape is of great interest for a variety of models in probability theory such as random walk in random scenery; see for example [START_REF] Aaronson | Relative complexity of random walks in random sceneries[END_REF][START_REF] Deligiannidis | Relative complexity of random walks in random scenery in the absence of a weak invariance principle for the local times[END_REF] where the size of the range is shown to determine the leading term of the asymptotic growth rate of the information arising from the scenery. The size of the range and its fluctuations have been extensively treated in the literature starting with the seminal paper [START_REF] Dvoretzky | Some problems on random walk in space[END_REF] where the authors obtained strong laws in the case of the simple random walk on Z 2 , see also [START_REF] Erdös | Some problems concerning the structure of random walk paths[END_REF] and [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]. A central limit theorem for the range was obtained in [START_REF] Jain | The range of random walk[END_REF], whereas the case of random walks with stable increments was treated in [START_REF] Gall | The range of stable random walks[END_REF].

More recently, the focus has shifted towards more involved objects, still related to the range. For example [START_REF] Benjamini | Entropy of random walk range[END_REF] studies the entropy of the range, [START_REF] Asselah | Capacity of the range of random walk on Z 4[END_REF][START_REF] Asselah | Capacity of the range of random walk on Z d[END_REF] its capacity, [START_REF] Vysotsky | Limit theorems for random walks that avoid bounded sets, with applications to the largest gap problem[END_REF] the largest gap problem in the range [START_REF] Vysotsky | Limit theorems for random walks that avoid bounded sets, with applications to the largest gap problem[END_REF]; finally [START_REF] Asselah | Boundary of the range of transient random walk[END_REF] and [START_REF] Okada | The inner boundary of random walk range[END_REF] study the boundary of the range, henceforth denoted by ∂R n , that is the sites in the range with at least one neighbour not visited by the random walk. Apart from its intrinsic interest, the motivation for studying the range and its relatives often stems from their relevance in more intricate models; the capacity of the range is of interest in random interlacements (see [START_REF] Sznitman | Vacant set of random interlacements and percolation[END_REF]), whereas the range itself is relevant in the study of random walks in random scenery.

The main focus of this paper is on asymptotic size of the boundary of the range and its relation to the Følner property of the range. We first present our results in the case of recurrent walks.

The research of Z.K. was partially supported by ISF grant No. 1570/17.

1.1. Recurrent walks in Z and Z 2 . The first and last authors first studied the Følner property of the range in [START_REF] Deligiannidis | Relative complexity of random walks in random scenery in the absence of a weak invariance principle for the local times[END_REF], where in the case of the simple random walk on Z 2 , it was shown that the range is almost surely a Følner sequence, that is almost surely

lim n→∞ |R n (R n + x)| |R n | = 0, for all x ∈ Z d , (1)
where for two subsets A, B ⊂ Z d , we write A B for the symmetric difference A B := (A ∪ B) \ (A ∩ B).

One can easily see that the Følner property captures the asymptotic relation between the size of the range |R n | and that of its boundary |∂R n | defined by

∂R n := x ∈ R n : ∃y ∈ Z d \ R n , |x -y| = 1 .
(

) 2
Indeed let S d denote the usual generators of Z d , that is S d := {±e i : 1 ≤ i ≤ d}, where e i are the standard unit basis vectors. For v ∈ Z d , we also define the v-boundary of the range as

∂ v R n := R n \ R n + v .
Using the above notation, the boundary ∂R n can also be written in the form

∂R n = v∈S d R n \ (R n + v) = v∈S d ∂ v R n .
From the above it is clear that for any v ∈ S d

|∂ v R n | ≤ |∂R n | ≤ v∈S d |∂ v R n |. (3)
Notice that a similar relation also holds for any countable, finitely generated group G, with S d replaced by the generators of G.

In addition, for any a, b ∈ Z d it can be easily shown that

|∂ a R n \∂ b R n | ≤ |∂ a-b R n |, |∂ a+b R n | ≤ |∂ b R n | + |∂ a R n |.
In particular (for countable finitely generated groups) the Følner property is equivalent to |∂R n |/|R n | → 0 as n → ∞. The Følner property is important in ergodic theory and information theory as it implies for example that the partial sums of any G-indexed random field along (F n ) satisfies the mean ergodic theorem [START_REF] Cohen | On the quenched functional CLT in 2d random sceneries, examples[END_REF] and the Shannon-McMillan-Breiman Theorem [START_REF] Kieffer | A generalized Shannon-McMillan theorem for the action of an amenable group on a probability space[END_REF][START_REF] Lindenstrauss | Pointwise theorems for amenable groups[END_REF].

A rate, at least in expectation, is given by [START_REF] Benjamini | Entropy of random walk range[END_REF], who proved for the simple random walk on Z 2 , that E |∂R n | ∼ Cn/ log 2 (n), whereas [START_REF] Okada | The inner boundary of random walk range[END_REF] proved that

π 2 2 ≤ lim n→∞ (log n) 2 n E |∂R n | ≤ 2π 2 .
We strengthen the results mentioned above by obtaining a strong law of large numbers for the boundary |∂R n | of a recurrent random walk in Z 2 , with finite second moments, or of a random walk in Z in the domain of attraction of the symmetric Cauchy law. Before introducing our first main result we give a precise statement of our assumptions.

Let ξ, ξ 1 , ξ 2 , • • • be i.i.d. Z d -valued random variables satisfying one of the following: (A1) d = 2 and there exists a nonsingular covariance matrix Σ ∈ M 2×2 (R) such that for all t ∈ [-π, π] 2 , φ(t) = E (exp(i t, ξ )) = 1 -Σt, t + o |t| 2 ;

(A2) d = 1 and there exists γ > 0 such that for t ∈ [-π, π],

φ(t) = E (exp(itξ)) = 1 -γ|t| + o(|t|).
It is worth mentioning under (A1) the random variables ξ i ∈ Z 2 have zero mean and finite second moments and therefore S n / √ n converges to a Gaussian random vector in R 2 . For example Simple Random Walk in Z 2 satisfies (A1). On the other hand, random walk satisfying assumption (A2) are in the domain of attraction of the symmetric Cauchy distribution, that is if S n := X 1 + • • • + X n , then S n /n → Z, where Z is a real random variable with characteristic function E exp(itZ) = exp (-|t|) We will always assume that the random walk is aperiodic, namely that there is no proper subgroup of Z d containing the support of ξ 1 . By [START_REF] Spitzer | Principles of random walk[END_REF]Theorem 7.1] this is equivalent to requiring that φ(t) = 1 for t ∈ [-π, π] d if and only if t = 0. Notice that when ξ i ∈ Z 2 has finite second moments, aperiodicity implies that the covariance matrix Σ in (A2) is non-singular.

Our first main result is the following.

Theorem 1.1. Let ξ 1 , ξ 2 , ..., ξ n , .. be i.i.d. Z d -valued aperiodic random variables satisfying Assumption (A1) or Assumption (A2). Then for every nonzero v ∈ Z d , there exist constants C v , C > 0 such that almost surely,

lim n→∞ log 2 (n) n |∂ v R n | = C v , lim n→∞ log 2 (n) n |∂R n | = C.
In addition

E(|∂ v R n |) ∼ Cvn log 2 (n) and E(|∂R n |) ∼ Cn log 2 (n) as n → ∞.
In the cases covered by Theorem 1.1 the random walks are recurrent, since Re [1-φ(t)] -1 dt = +∞, see [START_REF] Spitzer | Principles of random walk[END_REF]II.8.P1]. By [START_REF] Dvoretzky | Some problems on random walk in space[END_REF][START_REF] Jain | The range of random walk[END_REF] and [START_REF] Gall | The range of stable random walks[END_REF] we almost surely have |R n | ∼ dn/ log(n) for some d > 0; thus for all nonzero v ∈ Z 2 (or Z in the Cauchy case), there exists a C > 0 such that almost surely for n large enough,

C -1 1 log(n) ≤ |R n (R n + v)| |R n | ≤ C 1 log(n) ,
providing a sharp quantitative version of the Følner property for these random walks.

We complete our study of recurrent random walks, by considering Z-valued random walks in the domain of attraction of the symmetric, α-stable distribution with 1 < α ≤ 2. In these cases Le Gall and Rosen showed the range when scaled appropriately converges in distribution to a nontrivial random variable, namely the Lebesgue measure of the set W α ([0, 1]) := {W α (t) : 0 ≤ t ≤ 1}, where W α is the symmetric, α-stable Lévy process [START_REF] Gall | The range of stable random walks[END_REF]. Theorem 1.2. Let S n be a recurrent, aperiodic random walk on Z in the domain of attraction of a nondegenerate, symmetric, α-stable distribution with 1 < α ≤ 2. Then for all > 0, almost surely

|∂R n | |R n | = o n 1 α -1+ .
For α = 2 the quantitative upper bound of Theorem 1.2 is optimal in the polynomial term as can be deduced from the case of the simple random walk on Z, see Remark 4.3. Theorem 1.2 shows that for this class of random walks, the range process is almost surely a Følner sequence. This in turn can be used, for example, to greatly simplify the calculation of the upper bound of the relative complexity of the scenery in [START_REF] Aaronson | Relative complexity of random walks in random sceneries[END_REF], which is quite technical and is based on dyadic partitions, as Kieffer's Shannon-McMillan-Breiman formula directly applies to the sequence of sets (R n ) n .

1.2. Transient walks. Kaimanovich in a private communication asked which groups admit random walks whose range satisfies the almost sure Følner property. Most groups only carry transient random walks. Indeed, the only finitely generated groups on which there are recurrent random walks are the groups which are virtually cyclic or virtually Z 2 , see [START_REF] Woess | Random walks on infinite graphs and groups[END_REF]Theorem 3.24] meaning that there exists H a finite index subgroup of G which is isomorphic to {0}, Z or Z 2 . As for transient random walks the range grows linearly, Kaimanovich's question is naturally linked to the asymptotic size of the boundary of the range of transient random walks; see the discussion in Section 1.1.

Kesten, Spitzer and Whitman's showed that for all random walks,

|R n | n → P (S n = 0, for all n ≥ 1) ,
almost surely, where clearly the limit is positive for transient random walks, see [34, p. 38]. In the case of transient random walks on Z d with d ≥ 1, Okada showed in [START_REF] Okada | The inner boundary of random walk range[END_REF] that if X 1 , X

|∂R n | n = P ∀k ∈ N, S k = 0 ∩ ∃y ∈ {±e i ; 1 ≤ i ≤ d} , ∀k ∈ Z, S k = y ,
where {S -n ; n ≥ 0} is an independent copy of {-S n ; n ≥ 0}. We take a more general viewpoint and consider random walks on groups. Let G be a discrete group, {S n : n ≥ 0} be a G-valued random walk and R n := {S 1 , . . . , S n }. We first show that

lim n→∞ |R n (R n g)| |R n | = c(g), a.s. for all g ∈ G, (4)
where c(g) is given explicitly in terms of return probabilities and is thus closely related with the Green function G(g) = ∞ n=0 P (S n = g). In particular, Proposition 5.4 shows that if the Green function of a random walk vanishes at infinity then its range is almost surely not a Følner sequence.

Let us say that a random walk is admissible if the walk starting from the origin can reach any point with positive probability. A function f : G → R satisfies lim g→∞ f (g) = 0 if for all > 0, we have |f (g)| < for all but finitely many elements of G. We then establish the following. Theorem 1.3. Let p be an admissible probability measure on a finitely generated group G. Assume that p defines a transient random walk, and that G is not virtually cyclic. Then the Green function G(g) tends to 0 when g tends to infinity.

The condition that G is not virtually cyclic is necessary for the theorem: in Z, the Green function of a non-centered random walk with finite first moment does not tend to 0 at infinity, by the renewal theorem (and this statement can be extended to virtually cyclic groups).

It is worth noting that stronger, quantitative results, are available if one restricts the class of groups under consideration, see [START_REF] Woess | Random walks on infinite graphs and groups[END_REF]. For instance, when G is non-amenable the probabilities p n (id G , x) vanish exponentially fast, uniformly in x, from which the result follows readily. On amenable groups, for symmetric walks with finite support or more generally a second moment, one can sometimes use isoperimetric techniques to obtain much stronger results, specifying the rate of decay of p n (id G , x) and of the Green function at infinity. However, in general, there is no hope to get a quantitative version of Theorem 1.3 as we have made no moment assumption; it suffices to consider p such that ξ 1 is at distance 2 2 n of id G with probability 1/n 2 -then the Green function decays at most like 1/ log log d(id G , x). Moreover, surprisingly few tools apply in all classes of groups, regardless of their geometry.

After completing our proof, we learned that part of the statement of Theorem 1.3, namely if G is not virtually Z 2 , can also be deduced from results of Coulhon on isoperimetric inequalities (see [START_REF] Blachère | Asymptotic entropy and Green speed for random walks on countable groups[END_REF]Proposition 3.1]). We nevertheless decided to keep our argument for this case also since it is shorter and more elementary.

There is a simple class of transient random walks for which R n is a Følner sequence. Let X 1 , X 2 , . . . be a Z valued i.i.d sequence with finite first moment, positive expectation, and

P (X 1 > 1) = 0. Let S n = n k=1 X k . Then for almost all ω ∈ Ω, {R n } ∞ n=1 is an eventually monotone sequence of growing intervals with |R n | → ∞ as n → ∞.
Consequently the range process is almost surely a Følner sequence, and |∂R n | remains almost surely bounded. A similar statement holds for walks with S n → -∞ as n → ∞ and P (X 1 < -1) = 0. We say that these walks are the skip-free walks on Z.

With Theorem 1.3 at hand together with a specific study of virtually cyclic groups, we show the following. Theorem 1.4. Let S n be a transient admissible random walk on a finitely generated group G. If it is not a skip-free random walk on Z, then almost surely {R n } ∞ n=1 is not a Følner sequence. In particular, for all d ≥ 3, the range of all random walks on Z d is almost surely not a Følner sequence. This answers the question of Kaimanovich in full generality for all transient random walks on finitely generated groups. We obtain in particular that for transient random walks, either |∂R n | is eventually bounded, or it grows linearly, with no intermediate behavior.

The remainder of the paper is structured as follows. In Section 2 we introduce the necessary notation, collect some preliminary results and set the setting for proving the main results. Also in Section 2 we extend the results of [START_REF] Okada | The inner boundary of random walk range[END_REF] to transient co-cycles in discrete groups. The added generality of considering co-cycles is not strictly necessary, but it comes at no additional technical complexity and we think is of independent interest. The proofs of the main results, along with the relevant definitions and more precise statements, are given in Sections 3, 4 and 5 respectively. The Appendix contains some auxiliary results.

Preliminary results

As mentioned in the introduction we will present the results of this Section in the context of group-valued co-cycles. The abstraction to co-cycles is not strictly necessary for the rest of the paper but it does not add to the complexity of the paper and we think is of independent interest.

Let T be an invertible bi-measurable, ergodic, measure preserving transformation of a probability space (Ω, B, P), meaning that P • T -1 = P. In this case we will refer to (Ω, B, P, T ) as a probability preserving transformation. The transformation is ergodic if for all A ∈ B, T -1 A = A implies that P(A) = 0 or P(Ω \ A) = 0. In this section we will make use of the pointwise ergodic theorem: if a measurable f : Ω → R is P integrable and T is ergodic, then for P almost every ω ∈ Ω,

lim n→∞ n k=0 f • T k (ω) n = lim n→∞ n k=1 f • T -k (ω) n = E P (f ).
Let (G, ×) be a countable discrete group and denote by id G and m G the identity element and the Haar measure of G respectively. A G-valued cocycle is a function F : Z × Ω → G which satisfies the cocycle identity: for all m, n ∈ Z and ω ∈ Ω,

F (n + m, ω) = F (m, ω) × F (n, T m ω).

Any measurable function

f : Ω → G determines a G-valued cocycle F via F f (n, ω) =        f (ω) × f • T (ω) × • • • × f • T n-1 (ω) n ∈ N id G n = 0 f • T -1 (ω) -1 × • • • × (f • T -n (ω)) -1 n ∈ Z -.
In fact the above representation is general; any G-valued cocycle F is of the form F f for f defined by f (ω) = F (1, ω). These cocycles appear in the projection to the second coordinate of the skew product map

T f : Ω × G → Ω × G defined by T f (ω, g) = (T ω, gf (ω)). Note that T f preserves the σ-finite measure P × m G . A cocycle F is recurrent if almost surely N (ω) := # {n ∈ N : F (n, ω) = id G } = ∞ and transient if N (ω) < ∞ almost surely.
We would like to point out that there is no general necessary and sufficient criteria for recurrence of cocycles and that it follows from Herman's (unpublished notes) and [START_REF] Golodets | Locally compact groups appearing as ranges of cocycles of ergodic Z-actions[END_REF][START_REF] Aaronson | On Herman's theorem for ergodic, amenable group extensions of endomorphisms[END_REF] that all amenable groups admit a recurrent cocycle. As the class of amenable groups includes all Abelian groups as well as some groups of exponential growth the latter class is much more diverse than the class of groups of polynomial growth at most 2. We conclude that there are many groups which admit a recurrent cocycle and all their random walks are transient. The papers [START_REF] Atkinson | Recurrence of co-cycles and random walks[END_REF][START_REF] Schmidt | On recurrence[END_REF][START_REF] Schmidt | On joint recurrence[END_REF][START_REF] Conze | Sur un critère de récurrence en dimension 2 pour les marches stationnaires, applications[END_REF] provide some sufficient or necessary criteria for recurrence of cocycles. Let R n (ω) := {F (k, ω); 1 ≤ k ≤ n} be the range, or trace, of the co-cycle up to time n. When no confusion is possible we will write R n for R n (ω). For a finite subset A ⊂ G, we write |A| for its cardinality.

The next proposition was proved in Spitzer [34, pp. 38-40]1 2 for random walks in Z d and the proof of Proposition 2.1 below follows its lines. The case of Random walks on Z d can be recovered by taking Ω = (Z d ) Z , P is a product measure (distribution of an i.i.d. sequence), T is the Bernoulli shift (ergodic) and f (ω) = ω 0 , where ω

= (• • • , ω -1 , ω 0 , ω 1 , • • • ).
Proposition 2.1 (pp. 38-40 [34]). Let (Ω, B, P, T ) be an ergodic, probability-preserving transformation, G a countable group and F : Z × Ω → G a cocycle. Then for P-almost every ω,

lim n→∞ |R n (ω)| n = P (ω ∈ Ω; ∀n ∈ N, F (n, ω) = id G ) .
Proof. Define

A n = ω ∈ Ω : ∀k ∈ [1, n] ∩ N, F (k, ω ) = id G and A = A ∞ .
Counting each z ∈ R n according to the last time it has been visited in [1, n] ∩ N, it follows that

|R n (ω)| = n k=1 [∀k<j≤n,F (j,ω) =F (k,ω)] = n k=1 [∀0<j≤n-k,F (j,T k ω) =id G]
and for all n ∈ N and N < n

n k=1 A • T k ≤ |R n | = n k=1 A n-k • T k ≤ N + n-N k=1 A N • T k .
By the pointwise ergodic theorem, dividing all sides of the inequality by n, one has that for all N ∈ N, for almost every ω ∈ Ω,

P(A) ≤ lim n→∞ |R n (ω)| n ≤ lim n→∞ |R n (ω)| n ≤ P (A N ) .
Noting that A N ↓ A as N → ∞ and thus P (A N ) ----→

c := P (ω ∈ Ω : ∀n ∈ N, F (n, ω) = id G ) > 0.
To see this let l : Ω → N ∪ 0 be defined as

l(ω) := sup {n ∈ N ∪ {0} : F (n, ω) = id G } .
We need to show that P(l = 0) > 0. Letting B N = {ω ∈ Ω; l = N }, the transience of F implies that there exists N ∈ N ∪ {0} such that P (B N ) > 0. For all ω ∈ B N and j ∈ N,

id G = F (N + j, ω) = F (N, ω) × F j, T N ω = F j, T N ω .
The latter implies that T N B N ⊂ {ω ∈ Ω : l = 0} and since T preserves P we have P(l = 0) > 0.

2.1. The asymptotic size of the boundary of transient cocycles. [START_REF] Benjamini | Entropy of random walk range[END_REF] and [START_REF] Okada | The inner boundary of random walk range[END_REF] studied the asymptotic size of the boundary of a random walk in Z d . In the case of transient random walks on Z d , Okada obtained a strong law of the boundary of the range [START_REF] Okada | The inner boundary of random walk range[END_REF]. The following is a similar result for transient cocycles on arbitrary countable groups. The proof follows closely that of [START_REF] Okada | The inner boundary of random walk range[END_REF]Theorem 2.1]. Note that the proof [30, Theorem 2.1] contains a small issue since the shift operator as defined in the beginning of [30, Section 3.1] is measure-preserving with respect to an infinite measure. This however can be easily fixed by using instead the setup mentioned just before Proposition 2.1.

Proposition 2.3. Let (Ω, B, P, T ) be an ergodic probability preserving transformation, G a countable group and F : Z × Ω → G a cocyle. Then for all g ∈ G, for P-almost every ω ∈ Ω,

lim n→∞ |R n (ω) \ (R n (ω)g)| n = P ω ∈ Ω; ∀n ∈ N, F (n, ω) = id G , ∀n ∈ Z, F (n, ω) = g -1 .
Proof. Let g ∈ G and ω ∈ Ω. By definition, z ∈ R n (ω) \ (R n (ω)g) if and only if there exists 1 ≤ k ≤ n such that for all 1 ≤ j ≤ n,

F (j, ω)g = z = F (k, ω).
By considering the maximal k ≤ n for which

F (k, ω) = z, it holds that |R n (ω) \ (R n (ω)g)| = n k=1 Bn(k)
where

B n (k) = ω ∈ Ω; ∀j ∈ [1, n] ∩ N, F (j, ω) = F (k, ω)g -1 , ∀k < j ≤ n, F (j, ω) = F (k, ω) .
As for all k, j ∈ Z ,

F (k, ω) -1 F (j, ω) = F (j -k, T k ω), for all k ∈ {1, . . . , n}, B n (k) = T -k ω ∈ Ω : ∀j ∈ [-k, n -k] ∩ Z, F (j, ω) = g -1 , ∀j ∈ [1, n -k] ∩ N, F (j, ω) = id G .
This implies that for all N < n/2,

n k=1 C • T k ≤ |R n \ (R n g)| ≤ 2N + n-N k=N +1 C N • T k ,
where

C N := ω ∈ Ω; ∀j ∈ [-N, N ] ∩ Z, F (j, ω) = g -1 , ∀j ∈ [1, N ] ∩ N, F (j, ω) = id G and C = C ∞ = ∩ N C N .
The conclusion follows from the ergodic theorem as in the proof of Proposition 2.1.

The next Corollary follows easily from a combination of Propositions 2.1, 2.3 and Corollary 2.2.

Corollary 2.4. Let (Ω, B, P, T ) be an ergodic probability-preserving transformation, G a countable group and

F : Z × Ω → G a cocycle. If F is transient then for all g ∈ G, |R n \ (R n g)| |R n | a.s. ---→ n→∞ P ∀k ∈ Z, F (k, •) = g -1 ∀k ∈ N, F (k, •) = id G .

The Følner property.

A sequence {K n } n∈N of subsets of G is a right Følner sequence in G if for all n ∈ N, K n is a nonempty finite set and for all g ∈ G, |K n (K n g)| |K n | ---→ n→∞ 0.
The existence of Følner sequences is equivalent to amenability of the group (existence of a right invariant mean on G). In [START_REF] Deligiannidis | Relative complexity of random walks in random scenery in the absence of a weak invariance principle for the local times[END_REF], it was shown that the range of the symmetric random walk in Z 2 is almost surely a Følner sequence. Kaimanovich, in a private communication, asked which random walks on general countable groups have almost surely Følner ranges and Dolgopyat suggested to generalise this question to which cocycles have almost surely Følner ranges. The following is a partial advance on Dolgopyat's question for transient co-cycles as it establishes a relatively simple criterion for checking the Følner property. This criterion will be used afterwards to give a complete answer to Kaimanovich's question.

Proposition 2.5. Let (Ω, B, P, T ) be an ergodic probability preserving transformation, G a countable group and

F : Z × Ω → G a cocycle. If F is transient then for all g ∈ G, almost surely, lim n→∞ |R n R n g| |R n | = Φ(g) + Φ g -1 ,
where Φ(g

) := P ( ∀n ∈ Z, F (n, •) = g| ∀k ∈ N, F (k, •) = id G ).
Proof. It is easy to see, by multiplying by g -1 , that for all n ∈ N,

|R n g \ R n | = R n \ R n g -1 . Since (R n (R n g)) = (R n \ (R n g)) ((R n g) \ R n )
, the result follows from Corollary 2.4.

Proof of Theorem 1.1

In [START_REF] Benjamini | Entropy of random walk range[END_REF] it was shown that in the case of the symmetric random walk on Z 2 , E |∂R n | is proportional to the entropy of the range (at time n) and it is of order constant times n/ log 2 (n). [START_REF] Okada | The inner boundary of random walk range[END_REF] has shown that 2 -1 π 2 ≤ C ≤ 2π 2 . The previous Theorem is a law of large numbers type result for a more general class of random walks which includes random walks in the normal domain of attraction of a symmetric Cauchy distribution. It also gives a more precise estimate on the almost sure Følner property of the range of such random walks; see [START_REF] Deligiannidis | Relative complexity of random walks in random scenery in the absence of a weak invariance principle for the local times[END_REF] for some consequences of the Følner property of the range in the model of random walks in random sceneries. The proof goes by first establishing an upper bound for the variance of |∂R n | which gives convergence in probability. After that we use a method from [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF] which improves the asymptotics of the rate of convergence in probability, thus enabling us to use the Borel-Cantelli lemma for showing convergence almost surely.

Recall that for v ∈ Z d , the v-boundary of the range is defined as

∂ v R n = R n \ R n + v , whereas for V ⊂ Z d , we write ∂ V R n := ∩ v∈V ∂ v R n . For d = 1, 2, write S d := {±e i : 1 ≤ i ≤ d},
where e i are the usual generators of Z d . The boundary ∂R n can also be written in the form

∂R n = v∈S d R n \ (R n + v) = v∈S d ∂ v R n .
(

) 5
To prove the statement in Theorem 1.1 for ∂R n , we need first the statement for ∂ v R n and in fact a more general statement for ∂ V R n , where V ⊂ Z d . The proof of the statement for ∂R n will then follow from the inclusion-exclusion principle.

3.1. Auxiliary results. We now state and prove a number of auxiliary results that will be used in the proof of Theorem 1.1, that we could not find in the literature. Proposition 3.1. Under the assumptions of Theorem 1.1, for all j ∈ Z d \ {0} there exist c j , d j > 0 such that

P (∀1 ≤ k ≤ n, S k / ∈ {0, j}) ∼ c j log(n)
as n → ∞.

and

P (∀1 ≤ k ≤ n, S k = j) ∼ d j log(n)
as n → ∞.

Remark 3.2. Proposition 3.1 in the case of symmetric random walks on Z 2 with finite variance was (essentially) treated in [START_REF] Okada | The inner boundary of random walk range[END_REF].

Proof. The proof is a simple application of [START_REF] Kesten | Ratio theorems for random walks[END_REF]Theorem 4a]. This theorem states that for any aperiodic random walk in Z d , W ⊂ Z d a finite subset, and any x ∈ Z d we have

lim n→∞ P x (S k / ∈ W, k = 1, . . . , n) P 0 (S k = 0, k = 1, . . . , n) = gW (x), (6)
where in the cases of interest to us, by [START_REF] Kesten | Ratio theorems for random walks[END_REF]Eq.(

1.16)], for x, y ∈ Z d gW (x, y) := [x=y] + ∞ n=1 P x (S n = y, S k / ∈ W, 1 ≤ k ≤ n -1) , gW (x) = lim |y|→∞ gW (x, y). ( 7
)
Under assumptions (A1) or (A2), it follows from the local limit theorem that

n j=0 P(S j = 0) ∼ c log n. ( 8
)
Using this asymptotics, a standard argument, see for example [START_REF] Dvoretzky | Some problems on random walk in space[END_REF] and [24, Lemma 2.3], shows that there exists a constant γ d > 0, depending on the random walk, such that

P 0 {S k = 0, k = 1, . . . , n} ∼ γ d log n . ( 9
)
When W = {0, j}, from [26, Eq.(5.17) and (5.18)] we have that

g{0,j} (j) = a(j) a(j) + a(-j) , g{0,j} (0) = a(-j) a(j) + a(-j) ,
where

a(j) = ∞ n=0 P 0 (S n = 0) -P j (S n = 0) = 1 (2π) d [-π,π] d 1 -exp(ijt) 1 -φ(t) dt.
Under our assumptions, we have a(x) > 0 for all x = 0, by [START_REF] Spitzer | Principles of random walk[END_REF]Proposition 11.7]

P x [S n = y, S j / ∈ O, 1 ≤ j ≤ n -1] ≤ C n log 2 (n) . Proof. Let Q n O (x, y) := P x [S n = y, S j / ∈ O, 1 ≤ j ≤ n -1]
. Assume first that (A1) holds, i.e., d = 1, and that the walk is strongly aperiodic, which is equivalent to |φ(t)| < 1 for all t ∈ (-π, π) d \ {0}. For aperiodic random walks, this amounts to the condition that the greatest common divisor of return times to the origin is 1. For instance, the simple random walk is aperiodic, but not strongly aperiodic.

By strong aperiodicity of the walk condition (6.6) in [START_REF] Kesten | Ratio theorems for random walks[END_REF] is satisfied. By [25, Theorems 8 and 9] we have

lim n→∞ Q n O (x, y) πγ n log(n) 2 = 1,
which implies the result. Under (A2), still with strong aperiodicity, the estimate u,v∈O

Q n O (u, v) ∼ 2πdet(Σ) 1/2 n log(n) 2 ,
follows from [25, Theorem 9] and [START_REF] Jain | The range of random walk[END_REF]Theorem 4.1]. Then

Q n O (x, y) ∼ 2πdet(Σ) 1/2 n log(n) 2 gO (x)g -O (-y),
follows from the above and [25, Theorem 6a]. Indeed, although [START_REF] Kesten | Ratio theorems for random walks[END_REF]Theorem 9] is stated only for one-dimensional walks in the domain of attraction of a symmetric stable law, as explained in the proof the result remains true for any recurrent random walk satisfying [START_REF] Kesten | Ratio theorems for random walks[END_REF]Equation (11.1)]. This has been established under (A2) for strongly aperiodic random walks in [START_REF] Jain | The range of random walk[END_REF]Theorem 4.1]. Under (A1) or (A2), but with strong aperiodicity, we have proved the result of the lemma. We claim that it still holds if one weakens strong aperiodicity to aperiodicity, but a little extra work is needed. Let { Sj } j≥0 be a lazy version {S j } j≥0 . In particular, if S j = ξ 1 + • • • + ξ j , we let Sj = ξ1 + • • • + ξj , where ξj = B j ξ j where (B j ) ∞ j=1 are i.i.d. random variables, independent of the random walk, with P{B j = 1} = ρ ∈ (0, 1) and P{B j = 0} = 1 -ρ. It can be easily checked that { Sj } j≥0 is then strongly aperiodic and therefore that there exists C > 0 such that for all n ∈ N,

Qn O (x, y) := P x Sn = y, Sj / ∈ O, 1 ≤ j ≤ n -1 ≤ C n log(n) 2 . ( 10
)
In addition let T 0 := 0, T n := inf{n > T n-1 : ξn = 0}, n ≥ 1. It is then clear that for all j ≥ 1, T j -T j-1 are i.i.d. geometrically distributed on the positive integers. With this notation, we can embed a path of {S j } j≥0 into a path of { Sj } j≥0 by letting S j = ST j for j ≥ 0. Up to a time-change, the paths of {S j } and { Sj } coincide and thus

Q n O (x, y) = P x [S n = y, S j / ∈ O, 1 ≤ j ≤ n -1] = P x STn = y, S j / ∈ O, 1 ≤ j ≤ T n -1 = ∞ k=n P x Sk = y, S j / ∈ O, 1 ≤ j ≤ k -1 P(T n = k) ≤ (10) C ∞ k=n P(T n = k) k log(k) 2 ≤ C n log(n) 2 ∞ k=n P(T n = k) ≤ C n log(n) 2 .
As Z d is an Abelian group, in this case we consider instead a bi-infinite i.i.d. sequence {X i } i∈Z and write for n ∈ N,

S (-) n = - -1 k=-n X k .
In what follows we will make use of the fact that for k < n and v ∈ Z d , for all ω ∈ Ω,

S k (ω) = S n (ω) + v iff S (-) n-k (T n (ω)) = v iff S n-k T k (ω) = -v. Proposition 3.4.
Under the assumptions of Theorem 1.1, there exists a constant C > 0 such that

E (|∂R n |) ∼ Cn log 2 (n) , as n → ∞. ( 11
)
In addition, there exists M > 0 such that

Var (|∂R n |) M n 2 log log(n) log 5 (n) as n → ∞. ( 12
)
Proof. It follows easily from the equality

∂R n = v∈S d ∂ v R n in (5) that for any v ∈ S d we have |∂ v R n | ≤ |∂R n | ≤ v∈S d |∂ v R n |. (13)
Using the inclusion-exclusion principle and enumerating the elements of S d as v 1 , . . . , v 2d we have

|∂R n | = V ⊂S d (-1) |V |+1 |∂ V R n | , ( 14
)
recalling that for a collection, V := {v 1 , . . . , v l } say, of distinct vectors in Z d , we have that

∂ V R n := v∈V ∂ v R n = R n ∩ v∈V (R n + v) c
whence we can write as in the proof of Proposition 2.3

|∂ V R n | = n k=1 A k,V (k) (ω) B k,V (n-k) (ω) (15)
where

A 0,V (L) = ω ∈ Ω : ∀0 < l < L, S (-) l / ∈ V , A k,V (L) = T -k A 0,V (L),
and

B 0,V (L) = {ω ∈ Ω : ∀0 < l < L, S l / ∈ V ∪ {0}} , B k,V (L) = T -k B 0,V (L).
To see why notice that

A k,V (k) ∩ B k,V (n -k) = {ω ∈ Ω : ∀l ∈ [1, n], S k / ∈ S l + V, ∀m ∈ [k + 1, n], S m = S k } .
Let us first consider the case V = {v}. Then one has

|∂ v R n | (ω) = n k=1 A k (k) (ω) B k (n-k) (ω),
where

A k (k) := A k,{v} (k), B k (n -k) := B k,{v} (n -k).
By the Markov property for the random walk, for all 1

≤ k ≤ n, A k (k) and B k (n -k) are independent, thus E (|∂ v R n |) = n k=1 P (A k (k)) P (B k (n -k)) = n k=1 P ∀1 ≤ l ≤ k, S (-) l = v P ∀1 ≤ l ≤ n -k, S l / ∈ {0, v} = n-2 k=2 c v d v log(k) log(n -k) (1 + o(1)),
as n → ∞, where c v , d v > 0 by Proposition 3.1. An easy calculation, using the fact that log is slowly varying, shows that

n-2 k=2 1 log(k) log(n -k) = n-n/ log 2 n k= n/ log 2 n 1 log(k) log(n -k) + O n (log n) 3 = n log(n) 2 (1 + o(1)) + O n (log n) 3 ,
where we write x for the integer part of x.

Assume now |V | > 1. For any finite set W , the proof of Proposition 3.1 and in particular (6) imply that, as n → ∞

P (∀1 ≤ k ≤ n, S k / ∈ W ) = gW (0)γ d log(n) + o log(n) -1 as n → ∞, (16)
with γ d and gW (0) as defined in ( 9) and ( 7) respectively. Therefore similar arguments show that for any V ⊂ S d we have that

E |∂ V R n | ∼ γ 2 d gV (0)g V ∪{0} (0) n log 2 (n) , ( 17
)
and when gV (0)g V ∪{0} (0) = 0,

E |∂ V R n | = o n log 2 (n) .
Going back to ∂R n , we thus have that

lim n→∞ log(n) 2 n E |∂R n | = V ⊆S d (-1) |V |+1 γ 2 d gV (0)g V ∪{0} (0) ≥ max v∈V c {v} d {v} > 0 ( 18
)
where the last two inequalities follow from (13) and Proposition 3.1. This proves [START_REF] Chen | Moderate and small deviations for the ranges of one-dimensional random walks[END_REF]. Note that this equation gives a semi-explicit formula for the constant in the asymptotics of E |∂R n | in [START_REF] Chen | Moderate and small deviations for the ranges of one-dimensional random walks[END_REF]. We do not know any simpler formula for this constant ( [START_REF] Benjamini | Entropy of random walk range[END_REF] only provides upper and lower bounds, but no exact formula).

Variance. For the second part, from [START_REF] Conze | Sur un critère de récurrence en dimension 2 pour les marches stationnaires, applications[END_REF] we have that

Var (|∂R n |) = Var   V ⊆S d |∂ V R n |   ≤ C V ⊆S d Var [|∂ V R n |] .
Similarly to the proof of [START_REF] Chen | Moderate and small deviations for the ranges of one-dimensional random walks[END_REF], we first work out in detail the case V = {v}, for v ∈ S d arbitrary.

First notice that

E |∂ v R n | 2 = E n k=1 A k (k) B k (n-k) + 2 1≤k<m≤n E A k (k) B k (n-k) Am(m) Bm(n-m) .
The first term is equal to

E (|∂ v R n |). For the second term, notice that for 1 ≤ k < m ≤ n, B k (n-k) Am(m) ≤ B k ( (m-k)/2 ) Am( (m-k)/2 ) , ( 19
)
since for any k, m, B k (•), A m (•) are decreasing sequences of sets. To keep notation concise, for any integers l, k we will denote P(A k (l)) by ψ(l) and P(B k (l)) by θ(l), where we can drop the dependence on

k since P • T -1 = P. Since for 1 ≤ k ≤ m ≤ n the events A k (k), B k ( (m -k)/2 ) , A m ( (m -k)/2 ) , B m (n -m),
are independent, we have

E A k (k) B k (n-k) Am(m) Bm(n-m) ≤ ψ(k)θ m -k 2 ψ m -k 2 θ(n -m).
This shows that for k < m,

ι(k, m) := E A k (k) B k (n-k) Am(m) Bm(n-m) -E A k (k) B k (n-k) E Am(m) Bm(n-m)
is bounded from above by

ψ(k)θ(n -m) ψ m -k 2 θ m -k 2 -θ(n -k) + θ(n -k) ψ m -k 2 -ψ(m)
Denote by

D(n) := (k, m) ∈ [1, n] 2 : k, n -m > √ n and m -k ≥ n log 5 (n) .
Since for n large enough

log(n) -5 log log(n) -log(2) ≥ log(n) 2 , it follows that for all (k, m) ∈ D(n), ψ m -k 2 ∼ c v log((m -k)/2) ≤ c v log(n) -5 log log(n) -log(2) ≤ 2c v log(n) , ( 20
)
and

θ m -k 2 ∼ d v log((m -k)/2) ≤ 2d v log(n) . ( 21
)
with c v , d v as in Proposition 3.1. Similarly, for all (k, m) ∈ D(n) and n large enough we have that

θ m -k 2 -θ(n -k) = n-k-1 j= m-k 2 (θ(j) -θ(j + 1)) = n-k-1 j= m-k 2 P 0 [S j+1 ∈ {0, v}, S l / ∈ {0, v}, ∀1 ≤ l ≤ j] = n-k-1 j= m-k 2   w∈{0,v} P 0 [S j+1 = w, S l / ∈ {0, v}, 1 ≤ l ≤ j]   .
By Lemma 3.3, the term in the sum is bounded by C/(j log 2 (j)). Thus, since (m

-k)/2 → ∞ when n → ∞, θ m -k 2 -θ(n -k) ≤ C n-k-1 j= m-k 2 1 j log(j) 2 n-k s= m-k 2 ds s log(s) 2 1 log((m -k)/2) - 1 log(n -k) ≤ 1 log n -5 log log n -log 2 - 1 log n ≤ C log log(n) log 2 (n) , ( 22
)
and similarly

ψ m -k 2 -ψ(m) C log log(n) log 2 (n) . ( 23
) since for (k, m) ∈ D(n), it holds that n/log 5 (n) ≤ m ≤ n.
Combining ( 20), ( 21), ( 22) and ( 23), we obtain a global constant M > 0 such that for large n, for all (k, m)

∈ D(n) ι(k, m) M log log(n) log 3 (n) 1 log(n -m) 1 log(k) ≤ 4M log log(n) log 5 (n) . ( 24
)
Since ι(k, m) ≤ 1 for all k, m, we have

1≤k<m≤n ι(k, m) ≤ # (k, l) ∈ [1, n] 2 \ D(n) : k < l + (k,m)∈D(n) ι(k, m) ≤ 2n 3/2 + n 2 log 5 (n) + M n 2 log log(n) log 5 (n) .
This together with [START_REF] Chen | Moderate and small deviations for the ranges of one-dimensional random walks[END_REF] implies for any v ∈ S d

Var (|∂ v R n |) M n 2 log log(n) log 5 (n) as n → ∞.
Notice that for general V , we can essentially repeat the same proof using [START_REF] Cornfeld | of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF] and ψ V (l) := 20), [START_REF] Griffin | Approximate local limit theorems for laws outside domains of attraction[END_REF] along with [START_REF] Deligiannidis | Relative complexity of random walks in random scenery in the absence of a weak invariance principle for the local times[END_REF], whereas the bounds ( 22) and ( 23) also follow from Lemma 3.3 which holds for general V . This completes the proof.

P(A k,V (l)), θ V (l) := P(B k,V (l)) in place of ψ(l), θ(l). In particular notice that ψ V (n), θ V (n) ≤ C/ log(n) follows from (
Corollary 3.5. Under the assumptions of Theorem 1.1, there exists a constant C > 0 such that

lim n→∞ |∂R n | n/ log 2 (n) = C, in probability.
Proof. It follows from Proposition 3.4 that there exists M > 0 such that,

Var(|∂R n |) ≤ M E (∂R n ) 2 log log(n) log(n) .
By Markov's inequality,

P |∂R n | -E (|∂R n |) > E (|∂R n |) ≤ M log log(n) 2 log(n) ---→ n→∞ 0, ( 25
)
whence

|∂R n |/ E |∂R n | → 1 in probability.
In particular, from [START_REF] Chen | Moderate and small deviations for the ranges of one-dimensional random walks[END_REF], there exists C > 0 such that log 2 (n)|E(|∂R n |)/n → C, and thus by elementary arguments

log 2 (n) n |∂R n | ---→ n→∞ C in probability. (26)
In order to prove Theorem 1.1 we would like to improve the convergence in probability result to almost sure convergence. The gap of order log log(n)/ log(n) in the decay of these probabilities is enough to guarantee almost sure convergence of |∂R N k | for N k = exp (n a ) with a > 1. By a different method looking at

Z n = |∂R n | E (|∂R n |) -1, one can show almost sure convergence of Z N k to 0 where N k is of the form [exp(n a )] with a > 1/2. This is since for a > 1/2, ∞ k=1 E |Z N k | 2 < ∞.
Unfortunately as |∂R n | is not necessarily monotone, this subsequence is too thin in order to interpolate the almost sure convergence from the subsequence to almost sure convergence along the whole sequence. To that end we use a method from [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]. Definition 1. (i) Given δ > 0, the sequence of random variables {X n ; n ≥ 0} satisfies property A(δ) if for all 0 > 0 there exists C = C( 0 , δ) > 0 such that for all n ≥ 2 and ≥ 0 ,

P (X n > (1 + )E (X n )) ≤ C 2 log δ (n)
.

(ii) The sequence of random variables {X n ; n ≥ 0} satisfies property D(δ) if for all > 0, [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]] Let V ⊂ S d . For all δ > 0, if |∂ V R n | satisfies property A(δ) then it satisfies property A(4δ/3).

P (X n < (1 -)E (X n )) = O 1 log δ (n) Theorem A. [Theorem 4.2 in

Theorem B.

[Bound (1.9) in [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]] Under the assumptions of Theorem 1.1, for all V ⊂ Z d , |∂ V R n | satisfies property D(δ) for all δ > 0.

Remark 3.6. It is worth saying a few words about the fascinating method by Flatto [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF] that produces Theorems A, B. Our intuition of why it works is the following. First notice that if we decompose the random walk path into blocks, the range/boundary of the full path can then be compared with the union of the corresponding objects of the blocks after correcting for pair-wise interactions. The first key ingredient is the fact that these interactions are weak, therefore the enhanced bounds guaranteed by Flatto's method can be seen as a form of concentration. The second key ingredient is slow variation of the original bound which allows one to control the effect of the interactions between the blocks and makes this approach possible.

It follows from [START_REF] Kesten | Ratio theorems for random walks[END_REF] that for all δ ∈ (0, 1), the sequence |∂R n | satisfies properties A(δ) and D.

Corollary 3.7. Let V ⊂ S d . For all δ > 0, the sequence |∂ V R n | satisfies properties A(δ) and D(δ). Consequently, taking δ = 5, for all ε > 0 there exists C = C(ε) such that for all n ≥ 2,

P |∂ V R n | -E (|∂ V R n |) > εE (|∂ V R n |) ≤ C ε 2 log 5 (n) . ( 27
)
The proof of Theorems A and B is similar to the proof of [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]Thm. 4.2], hence it is postponed to the appendix. We note that the proof of Theorem B is easier for each individual term

|∂ V R n | separately then for |∂R n | which is a weighted sum of {|∂ V R n | : V ⊂ S d }.
Proof of Thm. 1.1. Notice that if we manage prove that log 2 (n)|∂R n |/n → C almost surely, then the fact that C > 0 follows from Corollary 3.5. In addition, similarly to the proof of Corollary 3.5 it suffices to prove that for any V ⊂ S d we have

log 2 (n) n |∂ V R n | a.s. ---→ n→∞ C V .
By [START_REF] Dvoretzky | Some problems on random walk in space[END_REF] it further suffices to show that

Z n := |∂ V R n | E (|∂ V R n |) -1 a.s.
---→ n→∞ 0.

Let > 0 and write N k := exp 4 √ k . By Corollary 3.7 there exists C > 0 such that for all n ≥ 2,

P (Z N k > ) ≤ C 2 log 5 (N k ) ≤ C k 5/4 .
It follows from the Borel-Cantelli lemma that for almost every w ∈ Ω,

lim sup k→∞ Z N k ≤ .
As Z n ≥ 0 and is arbitrary it follows that for almost every w ∈ Ω,

lim n→∞ Z N k = 0. Now for a general n ∈ N there exists a unique m = m(n) ∈ N such that N m ≤ n < N m+1 . Since e x -1 ≤ 2x for all 0 ≤ x ≤ 1 and for all m large 4 √ m + 1 -4 √ m ≤ 1/3m -3/4 , it follows that for all large m, N m+1 -N m ≤ exp( 4 √ m + 1) -exp( 4 √ m + 1) + 2 = exp 4 √ m exp 4 √ m + 1 -4 √ m -1 + 2 ≤ m -3/4 N m . ( 28
)
In particular, N m+1 /N m → 1. By [START_REF] Dvoretzky | Some problems on random walk in space[END_REF],

E(|∂ V R n |) ∼ Cn/(log 2 (n)) is regularly varying. Therefore, since N m ≤ n ≤ N m+1 , E(|∂ V R n |)/E(|∂ V R Nm |) → 1. ( 29
)
From the trivial bound

|∂ V R n | -2dm ≤ |∂ V R(n + m)| ≤ |∂ V R n | + 2dm
for all m large enough and N m ≤ n ≤ N m+1 , we have using ( 28)

|∂ V R n | -|∂ V R Nm | E(|∂ V R Nm |) ≤ 2d(N m+1 -N m ) E(|∂ V R Nm |) ≤ 2dm -3/4 N m CN m / log 2 (N m ) m 1/2 m 3/4 → 0. Since |∂ V R Nm |/E(|∂ V R Nm |) tends almost surely to 1, we obtain that |∂ V R n |/E(|∂ V R Nm |) also tends to 1. Together with (29), this gives |∂ V R n |/E(|∂ V R n |) → 1 almost
surely as required. It then follows from [START_REF] Dvoretzky | Some problems on random walk in space[END_REF] that for all V ⊂ S d , there exists C V ≥ 0 such that almost surely,

lim n→∞ log 2 (n) n |∂ V R n | = C V ,
and consequently,

log 2 (n) n |∂R n | = V ⊂S d log 2 (n) n |∂ V R n | ---→ n→∞ C = V ⊂S d C V > 0,
almost surely as required.

Proof of Theorem 1.2

Let {X n } ∞ n=-∞ be as sequence of i.i.d., centered, Z-valued random variables, and define the two-sided random walk {S n } n∈Z as follows, S 0 = 0, and for n ≥ 1 let

S n = X 1 + • • • + X n and S (-) n = -X -1 -• • • -X -n .
We assume that {S n } n is aperiodic in the sense of Section 3 and that the random variables {X i } i belong to the domain of attraction of a non-degenerate, symmetric, α-stable distribution with 1 < α ≤ 2. This implies that the X i are centered, and there exists a positive, slowly varying (at ∞) function L : R + → R + such that,

Y n := S n n 1 α L(n) d ---→ n→∞ Z α ,
where Z α is a real random variable with characteristic function E(e itZα ) = e -|t| α . By Lévy's continuity theorem, writing φ(t) := E(e itX 1 ), we see that for all t > 0,

E e itYn = φ t n 1 α L(n) n ---→ n→∞ e -|t| α .
From this and a Tauberian theorem it follows that, see e.g. [22, Theorem 2.6.5],

φ(t) = 1 -|t| α L(1/|t|) [1 + o (1)] , t → 0. ( 30
)
If A ⊂ Z is a finite subset we define

r n (x, A) := P x (S k / ∈ A, 1 ≤ k ≤ n) ,
and write r n := r n (0, {0}).

We will need the following result. . Assume in addition that the corresponding random walk is aperiodic. Then r n is regularly varying of index 1/α -1 as n → ∞; that is there exists another positive slowly varying (at ∞) function M such that, for any x ∈ Z and any finite nonempty A ⊆ Z,

lim n→∞ n 1-1/α M (n)r n (x, A) = C(x, A), ( 31
)
for some constant C(x, A) ≥ 0.

Proof. When lim s→∞ L(s), where L is the first slowly varying function in the statement, exists this result is [START_REF] Kesten | Ratio theorems for random walks[END_REF]Theorem 8]. So we will consider the case where L(•) does not have a limit at infinity. Similarly to the proof of [START_REF] Kesten | Ratio theorems for random walks[END_REF]Theorem 8] we define for λ ∈ [0, 1)

U (λ) := ∞ n=0 λ n P(S n = 0) = 1 2π π -π dt 1 -λφ(t) , R(λ) := ∞ n=0 λ n r n = (1 -λ) -1 U (λ) -1 .
First we will study the asymptotic behaviour of U (λ) as λ → 1. Notice that since |t| α L(1/t) is regularly varying at the origin, by [8, Theorem 1.5.3] there exists a monotone, α-regularly varying function g(t), such that g(t) ∼ C|t| α L(1/t) as t → 0, for some C > 0. Therefore φ(t) = 1 -g(t) [1 + o (1)], as t → 0. Next, we use aperiodicity to concentrate on the behaviour around the origin. In particular for any > 0, there exists a constant C( ) > 0 such that |φ(t)| < 1 -C( ) for all ≤ |t| ≤ π. The main contribution to the asymptotic behavior of U (λ) as λ → 1 will come from the integral over |t| < .

We claim that the function Ũ (δ) :=

0 dt δ + g(t)
is regularly varying of index 1/α -1 when δ → 0+ and that its asymptotic behaviour at 0+ does not depend on . Let us prove this claim.

Since g is α-regularly varying and monotone, its generalised inverse f (u) := g -1 (u) will be monotone and regularly varying of index 1/α, [8, see Theorem 1.5.12]. Letting t = g -1 (z) we have

Ũ (δ) = g( ) z=0 dg -1 (z) δ + z = ∞ z=0 dg -1 (z) δ + z ,
interpreting the integral in the Stieltjes sense, and letting g -1 (s) := g -1 (s) for s < g( ) and g -1 (s) := g -1 (g( )) for s ≥ g( ). With this definition it is clear that g -1 is also monotone and that g -1 (s) ∼ g -1 (s) as s → 0+. In particular its behaviour near the origin is independent of which shows that lim δ→0+ Ũ (δ)/ Ũ (δ) = 1 for all , > 0.

The rest is fairly similar to the proof of [START_REF] Bingham | Regular variation, volume 27 of Encyclopedia of Mathematics and its Applications[END_REF]Theorem 1.7.4]. First notice that

Ũ (δ) = ∞ z=0 dg -1 (z) δ + z = ∞ z=0 ∞ u=0 e -(δ+z)u dg -1 (z)du = ∞ u=0 e -δu ∞ z=0 e -zu dg -1 (z)du = ∞ u=0 e -δu V (u)du,
where

V (u) := ∞ z=0 e -zu dg -1 (z).
By [8, Theorem 1.7.1'], since g -1 (z) is regularly varying of index 1/α at the origin, we have that V (u) is regularly varying of index -1/α as u → ∞. In turn this implies that

W (u) := u 0 V (s)ds,
is regularly varying of index 1 -1/α as u → ∞ and since

Ũ (δ) = ∞ u=0 e -δu V (u)du = ∞ u=0
e -δu W (du), by Karamata's Tauberian theorem [8, 1.7.1] we have that Ũ (δ) is regularly varying of index 1/α -1 as δ → 0 with asymptotic behaviour at 0+ independent of . That is we have shown that there exists a (1/α -1)-regularly varying function Ũ such that for all > 0 we have lim δ→0 Ũ (δ)/ Ũ (δ) = 1.

Having proved the claim, let us now prove the main result. We write

U (λ) = Ũ (1 -λ) π + 1 2π 0 dt 1 -λφ(t) -Ũ (1 -λ) + 1 2π 0 - dt 1 -λφ(t) -Ũ (1 -λ) + 1 2π π>|t|> dt 1 -λφ(t) =: J 1 ( , λ) + J 2 ( , λ) + J 3 ( , λ) + J 4 ( , λ).
We claim that the term J 1 ( , λ) on the right dominates the other ones when λ tends to 1. First, it dominates the last one as Ũ (1 -λ) tends to infinity while the last term remains bounded. The other two terms are similar, so let us handle the first one. We write the difference as

J 2 ( , λ) = 0 dt 1 -λφ(t) -Ũ (1 -λ) = 0 1 1 -λφ(t) - 1 1 -λ + g(t) dt = 0 g(t) -λ(1 -φ(t)) (1 -λφ(t))(1 -λ + g(t)) dt.
By choice of g we can write g(t) = [1 -φ(t)][1 + o(1)] as t → 0+ and thus

g(t) -λ(1 -φ(t)) = [1 -φ(t)](1 -λ + o(1)).
In particular for 0 < t < we can write

|g(t) -λ(1 -φ(t))| ≤ |1 -φ(t)|(1 -λ + η( )),
for some positive function η(•) such that η( ) → 0 as → 0+. Therefore

|J 2 ( , λ)| ≤ 0 [1 -λ + η( )]|1 -φ(t)| |1 -λφ(t)| |1 -λ + g(t)| dt ≤ [1 -λ + η( )] 0 dt |1 -λ + g(t)| = [1 -λ + η( )] Ũ (1 -λ).
We can similarly bound the other term

J 3 ( , λ) ≤ [1 -λ + η( )] Ũ (1 -λ).
Therefore we have for i = 2, 3 that lim sup

λ→1 2|J i ( , λ)| |J 1 ( , λ)| ≤ η( ),
and since we have shown above that lim δ→0 Ũ (δ)/ Ũ (δ) = 1 we also have that lim sup

λ→1 |J i ( , λ)| Ũ (1 -λ) ≤ η( ),
Overall what we have just shown is that for some (1/α -1) regularly varying function Ũ we have

lim sup λ→1 U (λ) -1 π Ũ (1 -λ) Ũ (1 -λ) = lim sup λ→1 U (λ) Ũ (1 -λ) - 1 π ≤ η( ).
Since > 0 is arbitrary and η( ) → 0 with → 0 this proves that Remark 4.2. The following alternative approach using a local limit theorem is possible. Firstly, by [START_REF] Griffin | Approximate local limit theorems for laws outside domains of attraction[END_REF],

lim λ→1 U (λ) Ũ (1 -λ) = 1 π , whence it follows that U (λ) is regularly varying of index 1/α -1. Thus R(λ) ∼ C(1 - λ) -1/α M (1/(1 -λ)),
|P (S n = m) -P (S n = 0)| = O 1 a 2 n , as n → ∞ ( 32
)
where m ∈ Z and a n is a 1/α regularly varying sequence. Then a similar argument as in [START_REF] Dvoretzky | Some problems on random walk in space[END_REF] shows that

r n (m) := P (S k = m for all 1 ≤ k < n) ∼ r n (0) as n → ∞. ( 33
)
Remark 4.3. This theorem, in the case of i.i.d. random variables with E (X 1 ) = 0 and E X 2 1 = D < ∞ gives the rate o(n p ) for every p < 1 2 . We claim that this is the optimal rate in the polynomial exponent. Indeed, for the simple random walk on Z, R n is an interval and thus |∂R n | = 2. By Theorem 3 in [START_REF] Chen | Moderate and small deviations for the ranges of one-dimensional random walks[END_REF],

lim sup n→∞ √ n |∂R n | |R n | = lim sup n→∞ 2 √ n |R n | = ∞.
Before proceeding with the proof of Theorem 1.2, we need a number of auxiliary results.

Proposition 4.4. Let S n be an aperiodic random walk on Z in the domain of attraction of a nondegenerate, symmetric, α-stable distribution with 1 < α ≤ 2, then for any > 0, k ∈ N and x ∈ Z \ {0} there exists M > 0 such that

E |R n \ (R n -x))| k ≤ M n k( 2 α -1+ ) .
Proof. Let > 0 and j ∈ Z \ {0}. In the course of the proof C will denote a global positive constant whose value can change (increase) from line to line. We have the bound

|R n \ (R n -x)| ≤ n j=1 An(j) • T j where A n (m) = {w ∈ Ω : S j = x, ∀j ∈ [-m, n -m]} = D - x (m) ∩ D + x (n -m)
, where for y ∈ Z and n ≥ 0 we define

D - y (n) := {ω ∈ Ω : S (-) j = y, j ∈ [1, n]}, D + y (n) := {ω ∈ Ω : S j = y, j ∈ [1, n]}. Note that D -
x and D + x are independent, thus

P (A n (m)) = P D - x (m) P D + x (n -m) .
As Z α is symmetric, X 1 is in the domain of attraction of Z α if and only if -X 1 is in the domain of attraction of Z α . This together with Lemma 4.1 implies that there exist positive, slowly varying functions L + , L -and constants possibly depending on x such that

P D ± x (n) ≤ C(x)L ± (n) n 1-1/α , for n ≥ 1.
We will now show that for all k ∈ N there exists C > 0 such that,

E |R n \ (R n -x))| k ≤ C n k( 2 α -1+ ) + 5k 2 E |R n \ (R n -x)| k-1 .
The latter inequality proves the proposition by a simple induction argument. Writing

∆ k (n) := (m 1 , m 2 , .., m k ) ∈ {1, . . . , n} k : ∀1 < l ≤ k, m l -m l-1 ≥ 3 , and Λ k (n) := (m 1 , m 2 , .., m k ) ∈ {1, . . . , n} k : ∃1 < l < l ≤ k, |m l -m l | ≤ 2 , Then |R n \ (R n -x))| k ≤ k! (m 1 ,...,m k )∈∆ k (n) k l=1 An(m l ) • T m l + k! Λ k (n) k l=1 An(m l ) • T m l
For every (m 1 , ..., m k ) ∈ Λ k (n) there exists a minimal 1 ≤ l < k such that there exists a minimal l > l with |m l -m l | ≤ 2. Since for all 1 ≤ l < k

k l=1 An(m l ) • T m l ≤ l∈{1,..k}\{l} An(m l ) • T m l ,
and, (m j ) j∈{1,...,k}\{l} : (m j ) k j=1 ∈ Λ k (N ) ⊂ {1, . . . , n} k-1 , and there are 5 possible values for m l given m l ∈ {1, . . . , n}, we can see that

E   Λ k (n) k l=1 An(m l ) • T m l   ≤ 5 k 2 E   n m 1 ,...,m k-1 =1 k-1 l=1 An(m l ) • T m l   = 5 k 2 E |R n \ (R n -x))| k-1 .
It remains to bound the other term. For (m 1 , ..., m k ) ∈ ∆ k (n), letting q 1 = m 1 , q k+1 = n -m k and for 2 ≤ j ≤ k, q j = (m j -m j-1 )/2 , where x denotes the integer part of x, we deduce the inequality

k l=1 An(m l ) • T m l ≤ D - x (m 1 ) • T m 1 k l=2 D + x (q l ) • T m l-1 D - x (q l ) • T m l D + x (q k+1 ) • T m k Figure 1.
by replacing the restriction that S j + x = S m l for j ∈ [1, n] by the weaker one that S j + x = S m l for j ∈ [m l-1 + q l , m l + q l+1 ]; see Figure 1 where the random walk started at the marked point is constrained to not visit x for the time indicated by the arrows. The bound above is essentially a product of events that depend on non-overlapping sequences of the random variables {X j } j∈Z and therefore by independence we have that

E k l=1 An(m l ) • T m l ≤ P D - x (q 1 ) k l=2 P D + x (q l ) P D - x (q l ) P D + x (q k+1 ) ≤ C(x) k+1 l=2 L -(q l-1 ) (q l-1 ) 1-1/α L + (q l ) (q l ) 1-1/α ,
where we write C(x) for a generic positive constant depending on x. In particular since L ± (•) are slowly varying, for any > 0 we can find a positive constant C > 0 such that L ± (n) ≤ Cn and thus

E k l=1 An(m l ) • T m l ≤ C(x) k+1 l=2 C (q l-1 q l ) 1-1/α- = C(x) [q 1 q k+1 ] 1/α-1+ k l=2 (q l ) 2/α-2+2 .
Therefore,

E   ∆ k (n) k l=1 An(m l ) • T m l   ≤ C(x) q 1 ,...,q k+1 [q 1 q k+1 ] 1 α -1+ k l=2 q 2 α -2+2 l .
The sum is restricted to the values of q i that can be produced by the above process. They satisfy

q 1 + 2q 2 + • • • + 2q k + q k+1 ≤ n and q 1 + 2q 2 + • • • + 2q k + q k+1 ≥ n -k,
because of the integer parts in the definition of q j . We have that

n-k≤q 1 +...+q k+1 ≤n [q 1 q k+1 ] 1 α -1+ k l=2 q 2 α -2+2 l = k l=1 q 1 +...+q k+1 =n-l [q 1 q k+1 ] 1 α -1+ k l=2 q 2 α -2+2 l ≤ k q 1 +...+q k+1 =n [q 1 q k+1 ] 1 α -1+ k l=2 q 2 α -2+2 l ≤ Ckn ρ
by Lemma 4.5 below, since 1/α -1 + > -1, 2/α -2 + 2 > -1 for small enough , where

ρ = k + 2 • 1 α -1 + + (k -1) • 2 α -2 + 2 = k • 2 α -1 + 2 .
The result follows with = 2 .

Lemma 4.5. Let k ∈ Z, k > 1, and suppose that α 1 , . . . , α k > -1. Then

q 1 +•••+q k =n q 1 ,...,q k ≥0 k l=1 q α l l ≤ Cn (k-1)+ k l=1 α l .
Proof of Lemma 4.5. We will proceed by induction on k. Let k = 2 and notice that

q 1 +q 2 =n q α 1 1 q α 2 2 = n k=1 k α 1 (n -k) α 2 = n 1+α 1 +α 2 n k=1 k n α 1 1 - k n α 2 1 n ≤ Cn 1+α 1 +α 2 1 x=0 x α 1 (1 -x) α 2 dx ≤ Cβ(α 1 , α 2 )n 1+α 1 +α 2 ,
where β (α 1 , α 2 ) is the value of the β-function at (α 1 , α 2 ). Suppose now that the result holds for all integers ≤ k and notice that

q 1 +•••+q k+1 =n k+1 l=1 q α l l = n m=1 m α k+1 q 1 +•••+q k =n-m k+1 l=1 q α l l ≤ C n m=1 m α k+1 (n -m) k-1+α 1 +•••+α k ≤ Cn k+α 1 +•••+α k +α k+1 ,
where the last two inequalities follow from the inductive hypothesis for j = k and j = 2 respectively.

Proposition 4.6. Let S n be an aperiodic random walk on Z in the domain of attraction of a nondegenerate, symmetric, α-stable distribution with 1 < α ≤ 2. Then for all > 0, almost surely

lim n→∞ |R n | n 1 α - = ∞.
Proof. Let > 0. Le Gall and Rosen have shown in [START_REF] Gall | The range of stable random walks[END_REF] that there exists a 1/α-regularly varying sequence a n such that

|R n | a n dist. ---→ n→∞ Leb R (W α [0, 1]) , ( 34
)
where W α [0, 1] is the range of the symmetric α-stable Lévy motion up to time 1. It is well known, see for example [START_REF] Boylan | Local times for a class of Markoff processes[END_REF], that the occupation measure of a one-dimensional α-stable processes, for α > 1, defined by

µ(A) := 1 0 A • W α (s)ds,
is almost surely absolutely continuous with respect to Lebesgue measure 3 . As µ(W α [0, 1]) = 1 this implies that

P Leb R (W α [0, 1]) > 0 = 1. ( 35
)
Since a n is 1/α-regularly varying, setting t n := n κ , where κ > 0, we have that a tn is κ/α-regularly varying. Let κ = 1 -α /2, so that κ/α > 1/α -. Then for n large enough we have a tn > n 1/α-. Decompose the interval [0, n] ∩ Z into sub-intervals [jt n , (j + 1)t n ], j = 0, 1, .., n/t n of length t n , plus perhaps a remainder interval which will be ignored. Writing R(n, m) = {S n+1 , .., S m }, for δ > 0 and all n large enough we have that 3 Equivalently, almost surely possesses a continuous local time x → Lα (1, x) and therefore

|R n | ≥ max j∈ 1,.., n tn |R (jt n , (j + 1)t n )| ,
P |R n | < δn 1 α - ≤ P max j∈{1,.., n tn } |R (jt n , (j + 1)t n )| < δa tn ≤ P (|R tn | < δa tn ) n tn .
By [START_REF] Sznitman | Vacant set of random interlacements and percolation[END_REF] we can choose δ > 0 small enough so that P (Leb R (W α [0, 1]) < δ) < 1 and by [START_REF] Spitzer | Principles of random walk[END_REF] we can choose N 0 large enough so that for all n ≥ N 0 we have

P (|R tn | < δa tn ) ≤ ρ < 1.
Therefore for all n > N 0 , from the definition of t n and the above it follows that

P |R n | < δn 1 α - ≤ ρ n tn .
Since n/t n ∼ n κ where κ = α/2, we have that

n≥1 P |R n | < δn 1 α - ≤ n≥1 ρ n tn < ∞,
and thus from the Borel-Cantelli Lemma we have that almost surely

lim n→∞ |R n | n 1 α - ≥ δ.
As > 0 is arbitrary the conclusion follows.

Finally, we are now able to complete the proof of Theorem 1.2.

Proof of Theorem 1.2. Fix δ > 0. By Proposition 4.6, it remains to show that

lim n→∞ |∂R n | n 2 α -1+δ = 0. ( 36
)
First note that

|∂R n | ≤ |R n \ (R n -1)| + |R n \ (R n + 1)| = V n (1) + V n (2).
Let i ∈ {1, 2}. By Proposition 4.4 for any > 0 and k ∈ N there exists M > 0 such that for all n ∈ N and i ∈ {1, 2},

E V n (i) n 2 α -1+δ k ≤ M n k( -δ) .
Therefore, choosing < δ, there exist k ∈ N and M > 0 such that for all n ∈ N and i ∈ {1, 2},

E V n (i) n 2 α -1+δ k ≤ M n -2 .
A standard use of Markov's inequality and the Borel Cantelli Lemma shows that for any δ > 0 almost surely

lim n→∞ V n (1) n 2 α -1+δ = lim n→∞ V n (2) n 2 α -1+δ = 0. (37)
Therefore we have that almost surely for all δ > 0 small enough

lim n→∞ |∂R n | |R n | n 1 α -1+δ = lim n→∞ |∂R n | /n 2 α -1+δ/2 |R n | /n 1 α -δ/2
= 0, which proves the theorem.

5. Proof of Theorem 1.4

5.1. Følner property and transient random walks. We now turn to an application of Proposition 2.5 in the context of random walks in groups.

Let G be a countable group. Given p a probability measure on G and ξ 1 , ξ 2 , ... an i.i.d. sequence with marginals distributed as p, let S n = ξ 1 • ξ 2 • . . . • ξ n be the corresponding random walk and R n := {S 1 , ..., S n } be its range process. Let us say that a random walk driven by a measure p on the group G is admissible (or irreducible) if the walk starting from the identity can reach any point in the group, i.e. the semigroup generated by the support of p is the whole group. This is a natural irreducibility assumption.

We define the Green function, G : G → [0, ∞], of a transient random walk on G, by

G(g) := E (L(g)) = ∞ n=0 P (S n = g) , (38)
where

L(g) := |{n ∈ N ∪ {0}, S n = g} | : Ω → N ∪ {0}. For g ∈ G define q(g) := P (∀n ∈ N, S n = g) ,
and write q := q (id G ). The next Lemma is well known and we only include its proof for completeness.

Lemma 5.1. If S n is a G-valued transient random walk then for all g ∈ G, G(g) = 1 -q(g) q .
Proof. Let g ∈ G. By the Markov property for the random walk,

P(L(g) = 0) = q(g) P(L(g) = j) = (1 -q(g))(1 -q) j-1 q, j ≥ 1. and thus E(L(g)) = q(g) • 0 + (1 -q(g)) ∞ j=1 j(1 -q) j-1 q = (1 -q(g)) E L(0) = 1 -q(g) q .
The ergodic theoretic model of the random walk is the following skew product transformation. Let Ω := G Z , P = p ⊗G the product measure on Ω with marginals distributed as p and T : Ω → Ω the full shift defined by (T ω) n = ω n+1 . The dynamical system, G Z , B, p ⊗G , T is a stationary Bernoulli shift, hence ergodic, see for example [15, p. 180]. Writing m G for the Haar measure of G, and f : Ω → G, f (ω) := ω(0), the skew product transformation

T f : Ω × G → Ω × G satisfies π G (T n f ) d = S n ,
here π G (ω, h) = h is the projection to the G coordinate. The advantage of working with the skew product is that the cocycle identity indicates what is the relevant random walk in inverse time. In this case, write for n ∈ Z,

S (-) n = S (-) n (ω) := F (-n, ω) = ω(-1) -1 ω(-2) -1 • • • ω(-n) -1 . ( 39
)
Corollary 2.4 gives the following extension of Okada's result.

Corollary 5.2. Let G be a discrete countable group and p a probability measure on G and ξ 1 , ξ 2 , ... an i.i.d. sequence with marginal p. Then for any g = id G , almost everywhere

lim n→∞ |R n (R n • g)| |R n | = P ∀n ∈ N, S (-) n = g P ( ∀n ∈ N, S n = g| ∀n ∈ N, S n = id G ) + P ∀n ∈ N, S (-) n = g -1 P ∀n ∈ N, S n = g -1 ∀n ∈ N, S n = id G .
Proof. This is a direct consequence of Corollary 2.4 and the fact that {S n } ∞ n=1 and {S

(-) n } ∞ n=1 are independent.
Remark 5.3. In the case where G is Abelian, S (-) n d = (S n ) -1 and thus for all g ∈ G,

P ∀n ∈ N, S n = g -1 = P ∀n ∈ N, S (-) n = g .
The statement of Corollary 5.2 can be simplified in this case. Note that for a general group (S (-) n ) -1 is a (multiplication from the) left random walk and S n is a (multiplication from the) right random walk and their distribution as processes may no longer coincide.

Our next result links the Følner property of a transient G-valued random walk, with the decay of its Green function at infinity. Proposition 5.4. Let S n be a G valued transient random walk and suppose there exists a sequence

{g n } ∞ n=1 ⊂ G such that lim n→∞ max(G (g n ) , G (-) (g n )) = 0,
where G (-) denotes the Green function of

S (-) n , defined in (39). Then {R n } ∞ n=1 is almost surely not a Følner sequence. Furthermore if g ∈ G is of infinite order in G and lim n→∞ max(G (g n ) , G (-) (g n )) = 0, then lim n→∞ |R n (R n g)| |R n | > 0 a.e. Proof. It follows from Lemma 5.1 that G (g n ) ---→ n→∞ 0 implies that q (g n ) ---→ n→∞ 1.
Letting

A n := {∀k ∈ N, S k = g n } , B := {∀k ∈ N, S k = id G } ,
we have that P(A n ) = q(g n ) → 1 and P(B) = q, whence it easily follows that

lim n→∞ P ( ∀k ∈ N, S k = g n | ∀k ∈ N, S k = id G ) = lim n→∞ P (A n ∩ B) P(B) = 1.
A similar reasoning shows that G (-) (g n ) ---→ n→∞ 0 implies that

lim n→∞ P ∀k ∈ N, S (-) k = g n = 1.
By this

lim n→∞ P ∀k ∈ N, S (-) k = g n P ( ∀k ∈ N, S k = g n | ∀k ∈ N, S k = id G ) = 1,
and an application of Corollary 5.2 shows that for all large n ∈ N, almost surely

lim k→∞ |R k (R k • g n )| |R k | > 1 2 .
We conclude that almost surely the range is not a Følner sequence.

In order to show the second part let g be of infinite order. Consequently, g n ---→ n→∞ ∞ and there exists n ∈ N such that almost everywhere,

lim k→∞ |R k (R k • g n )| |R k | > 1 2 . ( 40
)
By the triangle inequality for cardinality of symmetric differences of sets, for all k ∈ N,

|R k (R k • g n )| ≤ |R k (R k • g)| + n j=2 R k g j-1 R k • g j = |R k (R k • g)| + n j=2 (R k (R k • g)) g j-1 = n |R k (R k • g)| ,
since for all h ∈ G and A ⊂ G, |Ah| = |A|. We conclude that for all k ∈ N,

|R k (R k • g n )| |R k | ≤ n |R k (R k • g)| |R k | Taking limits as k → ∞ we see that almost everywhere, n • lim k→∞ |R k (R k g)| |R k | ≥ lim k→∞ |R k (R k g n )| |R k | > 1 2 ,
where the last inequality is (40). This concludes the proof of the second part.

(R n + 1)| / |R n |) > 0.
It remains to treat the case when E (|X 1 |) < ∞. If E(X 1 ) = 0, it follows from the Chung Fuchs Theorem [START_REF] Chung | On the distribution of values of sums of random variables[END_REF] that the walk is recurrent, which we exclude. Therefore, by the strong law of large numbers, either lim n→∞ S n = ∞ almost surely or lim n→∞ S n = -∞ almost surely according to whether E(X 1 ) > 0 or E (X 1 ) < 0. It remains to show that if S n → ∞ almost surely and P (X 1 > 1) > 0 then the range process is almost surely not a Følner sequence, the opposite case being similar. Now if the random walk is transient and and S n → ∞ almost surely then4 P (∀n ∈ N, S n > 0) > 0. Since P (X 1 > 1) > 0, there exists Z j > 1 such that P (X 1 = j) > 0. Therefore, P (∀n ∈ N, S n > 1) ≥ P (X 1 = j and ∀2 ≤ n ∈ N, S n -X 1 > 0) = P (X 1 = j) P (∀n ∈ N, S n > 0) , by the Markov property of S n .

It follows that P (∀n ∈ N, S n > 1) > 0 and

P ( ∀n ∈ N, S n = 1| ∀n ∈ N, S n = 0) ≥ P (X 1 = j) P (∀n ∈ N, S n > 0) P (∀n ∈ N, S n = 0) > 0.
As the distributions of S We have shown that

P ∀n ∈ N, S (-) n = 1 P ( ∀n ∈ N, S n = 1| ∀n ∈ N, S n = 0) > 0.
By Corollary 5. [34, P8, page 287]. Since G(g) ≤ G π (π(g)), it follows that the Green function of S n also decays at infinity, since π has finite kernel. Then Proposition 5.4 shows that R n is not a Følner sequence. If X π 1 has a first moment, then E(X π 1 ) has to be nonzero by [START_REF] Chung | On the distribution of values of sums of random variables[END_REF] since the walk S π n is transient. In this case, by the strong law of large numbers, the probability that S π n = 0 for all n ∈ Z \ {0} is positive, as in the proof of Proposition 5.6. Since we are assuming G = Z, the kernel F is nontrivial. Therefore, we may choose g ∈ F \ {id G }. With positive probability, we have S n = g for all n ∈ Z\{0}, as this follows from the fact that S π n = 0 = π(g) for the projected random walk. Then Corollary 5.2 yields that |R n (R n • g)| /|R n | converges to a positive limit, and therefore R n is not Følner.

Consider now the case where π(G) = Z Z/2. The dihedral group Z Z/2 is made of two copies of Z that we denote by Z and Z × {ρ} where ρ is the nontrivial element of Z/2, acting on Z by sign reversal. Decomposing p π as a sum of two measures on these two copies of Z, we write p π = αp 1 + (1 -α)ρ * p 2 for some probability measures p 1 , p 2 on Z and some α ∈ [0, 1) (the value α = 1 being excluded as the walk is admissible, so it can not remain stuck in Z). Let pi be the reversed measure, given by pi (n) = p i (-n). The first return of the random walk S π n to Z is distributed according to the measure

p = αp 1 + (1 -α) 2 ∞ k=0 α k (p 2 * p * k 1 * p2 ),
where the k-th term corresponds to trajectories of the random walk jumping to the second copy of Z, making k steps there, and then coming back. Here, * denotes the convolution of measures, i.e., µ 1 * µ 2 is the distribution of the sum of two independent random variables distributed respectively as µ 1 and µ 2 . The presence of the reversed measures is coming from the action of ρ that reverses signs. If p 1 or p 2 has an infinite moment, then so does the measure p . Therefore, the Green function associated to p tends to zero at infinity on Z, by [34, P8, page 287]. Since, for points in Z, it coincides with the Green function of the random walk S π n , it follows that G π (g) also tends to zero at infinity along Z. As G(g) ≤ G π (π(g)), we get a sequence tending to infinity in G along which G(g n ) and G (-) (g n ) tend to 0. By Proposition 5.4, R n is almost surely not a Følner sequence.

Assume now that both p 1 and p 2 have a finite moment. Then so does p . Moreover, the expectation of a variable distributed according to p is given by

αE(p 1 ) + (1 -α) 2 ∞ k=0 α k (E(p 2 ) + kE(p 1 ) + E(p 2 )). As E(p i ) = -E(p i ), this reduces to αE(p 1 ) + (1 -α) 2 ∞ k=0 α k (E(p 2 ) -kE(p 1 ) -E(p 2 )) = E(p 1 ) α -(1 -α) 2 ∞ k=0 kα k = 0.
Therefore, by [START_REF] Chung | On the distribution of values of sums of random variables[END_REF], the random walk associated to p is recurrent. Then so is S π n . This is a contradiction, concluding the proof.

5.3.

Green functions vanish at infinity. The proof of Theorem 1.4 will essentially follow from Proposition 5.4 and the results of Subsection 5.2, once we establish the decay of the Green function of any admissible transient random walks on non-virtually cyclic groups. This is the main goal of this section.

As in Section 5.1 we consider a probability measure p on a group G, and let S n = ξ 1 • • • ξ n be the corresponding random walk, where ξ i are i.i.d. random variables distributed as p. When this random walk is transient, the Green function G(g) of the walk is defined as in [START_REF] Woess | Random walks on infinite graphs and groups[END_REF], by G(g) = ∞ n=0 p n (id G , g), where p n (id G , g) = P (S n = g). More generally, let G(g, h) = G(g -1 h). This is the average time that the walk starting from g spends at h.

The main result of this section is a proof of Theorem 1.3, asserting that if G is not virtually cyclic (i.e., there is no finite index subgroup which is isomorphic to Z) then the Green function G(g) tends to 0 when g tends to infinity. By this, we mean that for any > 0 there are only finitely many points g with G(g) ≥ , so this notion does not depend of the choice of a distance on the group.

In the proof, we will have to separate the case where G is virtually Z 2 . Let us start with this case.

Lemma 5.8. Assume that G is virtually Z 2 , and that the admissible probability measure p on G defines a transient random walk. Then its Green function tends to 0 at infinity. Proof. Assume first that G = Z 2 . Then the convergence to 0 at infinity of the Green function is [34, 24.P.5], as p is admissible and therefore aperiodic.

Assume now that G has a finite index subgroup H which is isomorphic to Z 2 . Replacing H with the intersection of its (finitely many) conjugates, one can even assume that H is normal in G. The measure p induces a measure on the group G/H, which defines a recurrent walk as G/H is finite. In particular, almost every trajectory of the random walk returns to H. The distribution of this first return is an admissible probability measure p H on H, to which one can apply the previous result: its Green function tends to 0 at infinity. Moreover, the Green functions of p and p H coincide on H as the trajectories of the random walk associated to p H can be obtained from the trajectories of the random walk for p by restricting to the times where the walk is in H. It follows that G(g) tends to 0 when g tends to infinity along H. By Harnack's inequality [38, 25.1], there exists a constant C such that, for all g 1 , g 2 ∈ G, one has G(g 1 ) ≤ C d(g 1 ,g 2 ) G(g 2 ). This inequality is also easy to prove directly, by concatenating a path from id G to g 1 with a path γ from g 1 to g 2 to obtain G(g 2 ) ≥ G(g 1 )p γ , where p γ is the probability to follow γ. Thanks to admissibility, one can choose such a path γ with p γ ≥ c d(g 1 ,g 2 ) for some c > 0, proving Harnack's inequality.

As H has finite index in G, every point of G is within uniformly bounded distance of H. Therefore, the convergence to 0 of the Green function along H extends to the whole group.

To prove Theorem 1.3, we can therefore assume that G is virtually neither Z or Z 2 . Then all admissible random walks on G, including the simple random walk, are transient, by [START_REF] Woess | Random walks on infinite graphs and groups[END_REF]Theorem 3.24]. For symmetric walks (i.e., such that p(g -1 ) = p(g)), the decay of the Green function at infinity is easy, as shown in the next lemma. The main point of the argument will be to deduce this also for non-symmetric walks by a comparison argument explained below. Lemma 5.9. Assume that a symmetric random walk on a group G is transient. Then its Green function tends to 0 at infinity. Proof. Let p n (g, h) denote the probability that the walk starting at g is at position h at time n. Then it is a standard fact that p 2n (id G , g) is maximal for g = id G . This is proved using Cauchy-Schwarz inequality and the symmetry of the walk as follows:

p 2n (id G , g) = h p n (id G , h)p n (h, g) ≤ h p n (id G , h) 2 1/2 h p n (h, g) 2 1/2 = h p n (id G , h)p n (h, id G ) 1/2 h p n (g, h)p n (h, g) 1/2 = p 2n (id G , id G ) 1/2 p 2n (g, g) 1/2 = p 2n (id G , id G ).
Conditioning on the position of the walk at time 1, one also gets p 2n+1 (id G , g) ≤ p 2n (id G , id G ). Therefore, for any g and any N ,

∞ n=2N p n (id G , g) ≤ 2 ∞ n=2N p n (id G , id G ).
The right hand side is the tail of the converging series n p n (id G , id G ) = G(id G ). If N is large enough, it is bounded by an arbitrarily small constant . For each n < 2N , the measure p n (id G , •) is a probability measure on G. Hence, there are only finitely many points g for which p n (id G , g) > /(2N ). Summing over n ≤ 2N , it follows that for all but finitely many points one has n<2N p n (id G , g) ≤ , and therefore G(g) = n p n (id G , g) ≤ 2 for all but finitely many points.

The next lemma is the main step of the proof of Theorem 1.3.

f (g)G(g, h)f (h) ≤ c -1 g,h∈G f (g)G S (g, h)f (h). (41)
Let F (g, h) be the probability to reach h starting from g. By Lemma 5.1, we have F (g, h) = qG(g, h) for a fixed q > 0, independent of g and h.

Let Ω = G N be the space of all possible trajectories, endowed with the probability measure P corresponding to the distribution of the random walk given by p starting from id G . A cylinder set is a set of the form

[g 0 , . . . , g n ] = {ω ∈ Ω | ω 0 = g 0 , • • • , ω n = g n } ⊆ Ω.
Assume by contradiction that G(g) does not tend to 0 at infinity. Then one can find > 0 and an infinite set I ⊆ G on which F (id G , g) = qG(g) > . Let M > 0 be large enough (how large will be specified at the end of the argument). We define a sequence h n of elements of I as follows.

• First, take h 0 = id G . Let also T 0 = [id G ] ⊆ Ω be the set of all trajectories starting from id G , and R 0 = {id G }. • Then, take an h 1 ∈ I at distance at least M of h 0 . As the probability to reach h 1 starting from id G is > by definition of I, one can find (by throwing away very long trajectories or very unlikely trajectories in finite time) a finite number of cylinder sets starting at id G and ending at h 1 with total probability > . Denote this set of trajectories by T 1 , with P(T 1 ) > . Let R 1 be the set of points that trajectories in T 1 reach before h 1 . As T 1 is a finite union of cylinders, R 1 is finite. • Then, take an h 2 ∈ I at distance at least M of h 0 and h 1 . We can also require that it does not belong to R 0 ∪ R 1 , as this set is finite while I is infinite. As above, we can then define a set T 2 which is a finite union of cylinders ending at h 2 with P(T 2 ) > , and R 2 the finite set of points reached by these trajectories before h 2 . • The construction goes on inductively to define h n .

The point of the previous construction is that for i ≤ j we have the inequality P(T i ∩ T j ) ≤ F (h i , h j ).

(42) Indeed, this is clear for i = j. For i < j, note that trajectories in T i ∩ T j reach h i and then h j , in this order as h j / ∈ R i . Therefore, P(T i ∩ T j ) ≤ P(∃n < m, S n = h i and S m = h j ) = F (id G , h i ) • F (h i , h j ) ≤ F (h i , h j ),

where the central equality follows from the Markov property. This proves (42).

Let us now take N large, and apply the inequality (41) to the characteristic function of {h 0 , • • • , h N -1 }. We obtain i,j<N

G(h i , h j ) ≤ c -1 i,j<N G S (h i , h j ). ( 43
)
We will bound the left hand side from below and the right hand side from above to get a contradiction. Thanks to (42), we have

i,j<N G(h i , h j ) ≥ i≤j<N G(h i , h j ) = q -1 i≤j<N F (h i , h j ) ≥ q -1 i≤j<N P(T i ∩ T j ) ≥ q -1 2 i,j<N P(T i ∩ T j ) = q -1 2 i<N 1 T i 2 dP ≥ q -1 2 i<N 1 T i dP 2 = q -1 2 i<N P(T i ) 2 ≥ q -1 2 2 N 2 .
The Green function G S tends to 0 at infinity, by Lemma 5.9. As the distance between h i and h j is at least M for i = j by construction, it follows that G S (h i , h j ) ≤ η(M ) where η tends to 0 with M . We obtain i,j<N

G S (h i , h j ) ≤ i=j G S (h i , h j ) + i =j G S (h i , h j ) ≤ N G S (id G ) + N 2 η(M ).
Combining these two estimates with (43) yields

q -1 2 2 N 2 ≤ c -1 N G S (id G ) + c -1 N 2 η(M ).
We obtain a contradiction by taking M large enough so that c -1 η(M ) < q -1 2 /2, and then letting N tend to infinity.

Proof of Theorem 1.3. The result follows from Lemma 5.8 if G is virtually Z 2 . Hence, we can assume that this is not the case, and therefore that the simple random walk on G is transient by [START_REF] Woess | Random walks on infinite graphs and groups[END_REF]Theorem 3.24]. The Green functions for the probability measures p and (p+δ id G )/2 are related by the identity G (p+δ id G )/2 (g) = 2G p (g), by [START_REF] Woess | Random walks on infinite graphs and groups[END_REF]Lemma 9.2]. Without loss of generality, we can therefore replace p with (p+δ id G )/2 and assume p(id G ) > 0. As p is admissible, it follows that there exists N with p N (id G , s) > 0 for all s in the generating set S. By Lemma 5.10, the Green function associated to p N , denoted by G N , tends to 0 at infinity.

To compute G(g), split the arrival times to g according to their values modulo N . For times of the form i + kN , such arrivals can be realized by following p for i steps, and then p N for k steps. It follows that G(g) = h∈G i<N p i (id G , h)G N (h -1 g).

Let > 0. Take a finite set F ⊂ G such that h / ∈F i<N p i (id G , h) < . Then G(g) ≤ h∈F i<N

p i (id G , h)G N (h -1 g) + G N L ∞ .
When g tends to infinity, the first term tends to 0 as this is a finite sum and G N tends to 0 at infinity. For large enough g, we get G(g) ≤ 2 G N L ∞ .

We are now ready to complete the proof of Theorem 1.4.

Proof of Theorem 1.4. For groups which are not virtually Z, the result follows directly from Proposition 5.4 and Theorem 1.3 showing that the Green functions G and G (-) tend to 0 at infinity. Groups which are virtually Z but not Z are handled in Proposition 5.7. Finally, the case of Z is done in Proposition 5.6. as n → ∞.

For n ∈ N we will write N = N (n) = log δ/3 (n) . For 1 ≤ i ≤ N , write n i = ni/N and divide the range R n into N -blocks, X n,i := S n i-1 +1 , S n i-1 +2 , . . . , S n i , 1 ≤ i ≤ N.

As before

∂ v X n,i := X n,i \ {X n,i + v} , ∂X n,i = v∈E d ∂ v X n,i .
Clearly

|∂R n | ≤ N i=1
|∂X n,i |.

Let ≥ 0 and set A i := ω ∈ Ω : |∂X n,i | ≥ 1 + 2 κn N log 2 (n) and

B i := ω ∈ Ω : |∂X n,i | ≥ 1 + N 2 κn N log 2 (n) ,
for 1 ≤ i ≤ N . Then a simple combinatorial argument (see equation (4.9) in [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]) gives,

|∂R n | > (1 + ) κn log 2 (n) ⊂   1≤i<j≤N A i ∩ A j   ∪ N i=1 B i ( 44
)
First we estimate P (A i ), P (B i ) from above. Writing

m i = m i (n) = n i -n i-1 for 1 ≤ i ≤ N , |∂X n,i | is equal in distribution to |∂R (m i )|. In addition, lim n→∞ m i / log 2 (m i ) n/(N log 2 (n)) = 1
uniformly in 1 ≤ i ≤ N . In addition, by [START_REF] Chen | Moderate and small deviations for the ranges of one-dimensional random walks[END_REF], since m i → ∞ as n → ∞,

lim n→∞ E (|∂R(m i )|) κm i / log 2 (m i ) = 1.
Consequently there exists n = n( 0 ), such that for all > 0 and n > n,

A i ⊂ |∂X n,i | ≥ 1 + 3 κm i log 2 (m i ) ⊂ |∂X n,i | ≥ 1 + 4 E (|∂R(m i )|) . ( 45
)
We deduce that for all > 0 , n > n and 1 ≤ i ≤ N ,

P
P (B i ) ≤ 32C( 0 /4, δ) 2 N log 4δ/3 (n) . ( 47
)
Since for 1 ≤ i < j ≤ N , the events A i and A j are independent it follows from (44), ( 46 as n → ∞. It follows that there exists C( 0 , 4δ/3) such that for all ≥ 0 and n ≥ 2

P (|∂R n | > (1 + )E (|∂R n |)) ≤ C( 0 , 4δ/3) 2 log 4δ/3 (n) .
As 0 is arbitrary this concludes the proof of Theorem A.

Proof of Theorem B. The proof essentially follows Sections 5,6 in [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF], which is quite lengthy and technical. Rather than reproducing the full argument we opt instead to point out the necessary modifications for the statements of the relevant results in [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF] to apply to the objects of interest in our case. Divide the random walk path S = {S j ; 1 ≤ j ≤ n} into N = [n/L] + 1 blocks of size L = [n/ log log n], where [x] denotes the integer part of x. We will write S (i) for the i-th block and R n . Finally the object T ij must be replaced by T i,j := x ∈ ∂ V R (i) n : R (j) n ∩ (x + (V ∪ {0})) = ∅ .

1. 2 . 1 .

 21 Notation. Given two sequences (a n ) n and (b n ) n of positive numbers we will write a n ∼ b n if lim n→∞ an bn = 1 and a n b n if there exists C > 0 such that for all n ∈ N, a n ≤ Cb n . For x ∈ R, x ∈ Z denotes the lower floor function of x.

Lemma 4 . 1 .

 41 Let {X i } i∈Z be i.i.d. Z-valued random variables with characteristic function φ satisfying (30) for a positive slowly varying function L and α ∈ (1, 2)

  and since r n is monotone it follows that r n ∼ cn 1/α-1 M (n) for some constants c, C > 0 and a positive, regularly varying function M , by[8, Corollary 1.7.3]. Having established this, (31) follows from [26, Theorem 4a].

= 1 =

 1 S n } ∞ n=1 are the sameP ∀n ∈ N, S (-) n P (∀n ∈ N, S n = -1) ≥ P (∀n ∈ N, S n > 0) > 0.

Lemma 5 . 10 .

 510 Consider a finitely generated group G, with a finite symmetric generating set S. Assume that the simple random walk on G (driven by the uniform measure on S) is transient. Let c > 0. Consider a probability measure p on G with p(s) ≥ c for all s ∈ S. Then its Green function tends to 0 at infinity. When the simple random walk is transient, all the admissible random walks on G are transient, by [38, Theorem 3.24]. Hence, under the assumptions of the lemma, the Green function associating to p is finite, and it makes sense to ask if it tends to zero at infinity. Proof. The proof will rely on a classical comparison lemma, making it possible to relate general random walks to symmetric ones. Denote by G the Green function associated to p, and by G S the Green function associated to the simple random walk. Under the assumptions of the lemma, [36, Proposition, Page 251] ensures that for any nonnegative square-integrable function f on G, g,h∈G

  Appendix A. Flatto's inequality enhancement procedure Proof of Theorem A. Assume that A(δ) holds for |∂R n |. Fix 0 > 0 and denote by κ > 0 the unique constant, see Proposition 3.4, so that E (|∂R n |) ∼ κn log 2 (n)

2 +

 2 ) and (47) that for all > 0 and n > n,P (|∂R n | > (1 + )E (|∂R n |)) ≤ 1≤i<j≤N P(A i )P(A j ) + 32C( 0 /4, δ) 1 2 log 4δ/3 (n)

k

  : k = 0, L -1}, with S (i) k = S iL+k for k = 0, . . . , L -1.One may follow[START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF] Section 6] replacing the objectsT p n by |∂ V R n |, T i by ∂ V R (i)

  [START_REF] Aaronson | On Herman's theorem for ergodic, amenable group extensions of endomorphisms[END_REF]

  Transient random walks on virtually cyclic groups. Let us show that the skip-free random walks (defined just before Theorem 1.4) are the only transient Z-valued random walks with almost surely Følner range. Let S n = n k=1 X k be a transient Z-valued random walk. If {R n } ∞ n=1 is almost surely a Følner sequence then S n is a skip-free random walk. Proof. If E (|X 1 |) = ∞ then by [34, P8, page 287] the Green function of S n and S

	Corollary 5.5. Let G be a torsion free countable group. Let S n be a G valued transient random
	walk for which the Green function tends to 0 at infinity. For all g ∈ G \ {id}, there exists
	c(g) > 0 such that
	c(g) = lim n→∞	|R n (R n g)| |R n |	a.e.
	5.2. Proposition 5.6. (-) n	decays at
	infinity. By Corollary 5.5, lim n→∞ (|R n

  2, lim n→∞ (|R n (R n + 1)| / |R n |) > 0 almost surely and {R n } ∞ n=1 is almost surely not a Følner sequence. Let us show that, on groups which are virtually Z but not Z, there is no transient walk for which the range is Følner. Let S n be a transient random walk on a group which is virtually Z, but not isomorphic to Z. Then the range {R n } ∞ n=1 is almost surely not a Følner sequence. Proof. By [33, Theorem 5.12], there is a surjective morphism π from G to either Z or the infinite dihedral group Z Z/2, with finite kernel F . Since the kernel is finite, the image under π of the transient random walk on G is still a transient random walk in the image group. We will treat separately the two cases. Assume first that π(G) = Z. Let p denote the measure on G driving the random walk S n , and p π its image in Z driving the image random walk S π n . Write G, resp. G π for the Green function of S n , resp. S π n . If X π 1 has no first moment, then the Green function of S π n decays at infinity, by

	Proposition 5.7.

  (A i ) ≤ P |∂X n,i | > 1 + 4 E (|∂R(m i )|) = P |∂R(m i )| > 1 + 4 E (|∂R(m i )|) , by property A(δ)Finally, as log δ (m i ) ∼ log δ (n) as n → ∞, we can enlarge n such that for all > 0 , and n > n,To bound P(B i ) from above notice that by similar considerations as in (45), for all > 0 and n > n,B i ⊂ |∂X n,i | ≥ 1 + N 4 E (|∂R(m i )|) , consequently for all 1 ≤ i ≤ N, P (B i ) ≤ P |∂R m i | ≥ 1 +

	≤	16C ( 0 /4, δ) 2 log δ (m i )	.
		P (A i ) ≤	32C ( 0 /4, δ) 2 log δ (n)	≤	32C ( 0 /4, δ) 0 log δ (n)	(46)
				N 4	E (|∂R m i |) ≤	16C ( 0 /4, δ)

2

N 2 log δ (m i ) . Now as N ∼ log δ/3 (n) as n → ∞, by enlarging n if needed, we can assume that for all n > n uniformly on 1 ≤ i ≤ N and > 0 ,

Although it is stated for Z d , it holds for general countable groups as pointed out by Flatto[START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF].

Spitzer attributes the proof to an unpublished manuscript with Kesten and Whitman.

See the proof of Corollary 2.2 where it shown that P(l = 0) > 0.

With this definition we have

and given the analogous version of [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]Theorems 5.1,5.2] one can proceed verbatim as in [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]Section 6].

We will now briefly explain how one can adapt the proof of [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]Theorems 5.1] for the T i,j written above. This is possible by replacing the events A(i, j; µ, µ; x) defined therein by the events

For a collection of distinct positive integers i 1 , . . . , i 2m , 1 ≤ µ 1 , . . . , µ 2m ≤ L and x 1 , . . . , x m ∈ Z 2 let σ be the unique permutation of {1, . . . , 2m} such that letting

where the events

are independent since they depend on disjoint blocks of random variables. The calculations then are similar to [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF], subject to routine modifications to [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]Lemma 5.1]. Indeed, writing s k = (j k+1 -j k ) L + ν -ν, and using [START_REF] Flatto | The multiple range of two-dimensional recurrent walk[END_REF]Lemma 5.1], it is straightforward to prove that there exists C > 0 such that for all 1

e.g. proving (5.1) of Flatto. Since j k+1 > j k then,