Adrien Boulanger

Pierre Mathieu

AND Cagri Sert
email: cagri.sert@math.uzh.ch

Alessandro Sisto
email: sisto@math.ethz.ch

LARGE DEVIATIONS FOR RANDOM WALKS ON HYPERBOLIC SPACES

Let Γ be a countable group acting on a geodesic hyperbolic metric space X and µ a probability measure on Γ whose support generates a non-elementary semigroup. Under the assumption that µ has a finite exponential moment, we establish large deviations results for the distance and the translation length of a random walk with driving measure µ. One of the consequences of our results confirms a special case of a conjecture regarding large deviations of spectral radii of random matrix products.

The rate of escape of the random walk is defined as the limit (1.1) l := lim n→∞ E(d(z n , z 0 )) n .

(The existence of the limit follows from sub-additivity.) It follows from Kingman's subadditive ergodic theorem that l is also the P almost sure limit of the ratio d(z n , z 0 )/n.

This article addresses the question of large deviations with respect to this last convergence: we are looking for estimates of the probability that the distance d(z n , z 0 )/n deviates from l by an error of order 1, either from below or from above, and similarly for the translation length τ (γ n )/n (see below for definitions). More precisely, we investigate the case where the space X is geodesic and hyperbolic and the measure µ is non-elementary.

A probability measure µ on Γ is said to be non-elementary when its support generates a semigroup which contains two independent loxodromic elements; see Subsection 3.3. Note we do not assume that X is proper.

This setting has recently attracted a lot of attention as it encompasses several natural actions such as Gromov hyperbolic groups acting on their Cayley graphs, rank-one semisimple groups acting on their symmetric spaces or Bruhat-Tits buildings, mapping class groups of surfaces acting on their curve complexes, relatively hyperbolic groups acting on their conned off spaces, the Cremona group acting on the Picard-Manin hyperbolic space... We refer to the introduction of [MT18a, Section 1.2] for more details and references on the topic.

In [START_REF] Maher | Random walks on weakly hyperbolic groups[END_REF], [START_REF] Sunderland | Linear progress with exponential decay in weakly hyperbolic groups[END_REF] and [START_REF] Maher | Random walks, wpd actions, and the cremona group[END_REF], the authors investigate the escape rate of random walks driven by non-elementary measures. They show in particular that it is positive in this setting. Their approach focus on the boundary theory; they also manage to identify the Poisson boundary of the random walk with the Gromov boundary on the underlying hyperbolic space under the assumption that the action is WPD. In [START_REF] Mathieu | Deviation inequalities for random walks[END_REF] a different approach was proposed based on deviation inequalities (and thus without any reference to boundary theory). Under the assumption that the action is acylindrical, the authors manage to prove a central limit theorem for the rate of escape on the group itself.

To formulate our results on large deviations of random walks on X, recall that a sequence (Z n ) n∈N of real-valued random variables is said to satisfy a large deviation principle, abbreviated LDP from now on, if there exists a lower-semicontinuous function, called the rate function, I : R -→ [0, ∞] such that for every measurable subset R of R, we have

-inf I(α) α∈int(R) ≤ lim inf n→∞ 1 n log P(Z n ∈ R) ≤ lim sup n→∞ 1 n log P(Z n ∈ R) ≤ -inf I(α) α∈R
where, int(R) denotes the interior and R the closure of R. Our first main theorem is the following.

Theorem 1.2. Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, µ a non-elementary probability measure on Γ with a finite exponential moment and z 0 ∈ X. Then the sequence of random variables ( 1 n d(z 0 , z n )) n∈N satisfies a large deviation principle with a proper convex rate function I : R → [0, ∞] which vanishes only at l. Note first that the rate function I does not depend on z 0 since the group acts by isometries: for two different starting points z 0 and z 0 , we have

|d(γ n • z 0 , z 0 ) -d(γ n • z 0 , z 0 )| ≤ 2 d(z 0 , z 0 ) .
Below, we list some more remarks on this result: Remark 1.3. 1. By convexity of I, the set D I = {α ∈ [0, ∞) | I(α) < ∞}, called the effective support of I, is an interval and I is continuous on D I . By Theorem 1.2, this in turn implies that for every subset J of D I satisfying int(J) = J (e.g. any interval with non-empty interior), the limit lim n→∞ 1 n log P( 1 n d(γ n z 0 , z 0 ) ∈ J) exists and is equal to max α∈J -I(α) (see Theorem 1.5 for more on D I ).

Since we also have decay estimates, the assumption that µ has a finite exponential moment is sharp for what concerns the uniqueness of zero of I, see Subsection 3.1.

To the best of our knowledge, exponential decay in large deviations and LDP's had not been studied in the context of Theorem 1.2 so far. Even in the special case where Γ is hyperbolic, Theorem 1.2 seems new. The most similar setting for which such a large deviation principle holds is for Lyapunov exponents associated to random products of matrices. We refer to the introduction of the third author's PhD thesis [START_REF] Sert | Joint Spectrum and Large Deviation Principles for Random Products of Matrices[END_REF] and the references therein for more details. In particular, in that setting, the proof of exponential decay in large deviations (corresponding to uniqueness of the zero of I) goes back to Le Page [?].

When Γ is hyperbolic and µ has a finite support, a possible alternative approach to prove that the rate function I has unique zero, would be to exploit the spectral gap property of the image of the random walk on the boundary of the group. We refer to [Gou17, end of page 4]. For a surface group with the standard presentation and a driving measure with a finite exponential moment, large deviation estimates follow from the regeneration structure introduced in [START_REF] Haïssinsky | Renewal theory for random walks on surface groups[END_REF].

Another important geometric notion of size associated to an isometry γ acting on a hyperbolic space (X, d) is its translation length defined as

τ (γ) := inf x∈X d(x, γ • x) .
This quantity has the advantage not to depend on a base point and is a conjugacy invariant. On the other hand, it is perhaps harder to study than d(x, g • x) since it is not sub-additive. For example, the lack of sub-additivity prevents one to readily get a convergence as in (1.1). On the other hand, it is known that for a non-elementary probability measure with bounded support, the averages 1 n τ (γ n ) and 1 n d(z n , z 0 ) behave similarly from the perspective of law of large numbers. Namely, they converge almost surely to the same constant l (see e.g. [START_REF] Maher | Random walks, wpd actions, and the cremona group[END_REF]Theorem 4.1]).

Let us now come to our second main theorem. We say that a set B ⊂ Isom(X) is bounded if sup

g∈B d(x, g • x) < ∞ ,
is bounded for some x ∈ X (equivalently any). A probability measure µ on Isom(X) is said to have bounded support if its support is a bounded set. Our second main result reads Theorem 1.4. Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, µ a non-elementary probability measure on Γ of bounded support. Then the sequence of random variables ( 1 n τ (γ n )) n∈N satisfies a large deviation principle with the same rate function as the one given by Theorem 1.2. This theorem refines several previous results on the probabilistic behaviour of translation distance, e.g. [START_REF] Maher | Random walks on weakly hyperbolic groups[END_REF]Theorem 1.4]. For example, it implies both the almost sure and the L 1 convergence τ (γ n ) n -→ n→∞ l (this was shown in [START_REF] Maher | Random walks, wpd actions, and the cremona group[END_REF]Theorem 4.1]). In particular, specializing to the setting of the Cremona group, it also yields [MT18b, Theorem 1.2]. Another important consequence is expressed in Corollary 1.7. Namely, it confirms a special case of a conjecture about large deviations of spectral radii of random matrix products.

A common and sometimes more convenient way to express a notion of translation length is given by that of asymptotic translation length or stable length defined as

(γ) = lim n→∞ d(x, γ n • x) n .
The limit exists by sub-additivity and does not depend on x. The difference | (.) -τ (.)| is uniformly bounded on Isom(X) (see [?, Ch.10, Prop. 6.4]). Consequently, the previous theorem applies equally to the random variables 1 n (γ n ) with the same conclusion.

The following subsections detail some direct consequences of the two above theorems and discuss some further properties of the rate function I. A complete description of the results of this article as well as its structure will be carried out in Section 2. The function I may be very degenerate. For example, let Γ := F 2 := A, B be the free group with two generators seen as acting on itself. We make it a metric tree X by considering the word distance associated to the generating system {A, A -1 , B, B -1 } and we mark z 0 as the identity of Γ. Let then µ be the measure µ(A) = µ(B) = 1 2 . In this example the space X is hyperbolic and geodesic. The probability measure µ is supported by the set {A, B} and, as such, has a finite exponential moment and generates a nonelementary semigroup (A, B themselves are independent and loxodromic). In this case one has for all n ∈ N d(z 0 , z n ) = n , so that the function I values 0 at 1 and ∞ otherwise.

For finitely supported probability measure, the function I will be infinite on a neighbourhood of ∞ as well. However, it is easy to see that l min = 0 and l max > l whenever the semigroup generated by µ contains the identity. Indeed, we may accelerate or decelerate the random walk (with an exponential cost) by adjusting the frequency of 'identity elements' in the trajectories using an argument similar to the one used in the proof of [START_REF] Mathieu | Deviation inequalities for random walks[END_REF]Theorem 4.12]. Under more assumptions, one can even be more precise.

The following result gives a geometric characterization of D I only in terms of the support of the probability measure µ. It also relates the effective support with the recently introduced notion of asymptotic joint displacement of a bounded set of isometries of a metric space.

To state this result, we need some terminology. A set B of isometries of a metric space (X, d) is said to be non-arithmetic if there exist n ∈ N and g 1 , g 2 ∈ B n such that (g 1 ) = (g 2 ). As in [?], we shall also call a probability measure non-arithmetic if its support is.

Let B be a bounded subset of Isom(X). The limit as n goes to infinity of sup g∈B n 1 n d(g•x, x) is called the asymptotic joint displacement [?] or joint stable length [?] of B. Similarly, let sub (B) = lim n→∞ inf g∈B n 1 n d(x, g • x) that we call lower asymptotic joint displacement of B. Both limits exist by subadditivity and they do not depend on x.

Theorem 1.5 (Effective support). Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, µ a non-elementary probability measure on Γ. Let I be the rate function given by Theorem 1.2.

(1) The effective support D I of I is an interval with non-empty interior if and only if the probability measure µ is non-arithmetic.

(2) If µ is of bounded support, we have l min = sub (supp(µ)) ;

l max = (supp(µ))) . (3) If supp(µ) is finite, then D I = [ sub (supp(µ)), (supp(µ))].
Remark 1.6. Regarding the second statement in the previous theorem, in Subsection 11.1, we provide examples of probability measures µ of bounded support for which the rate function I explodes at l min and l max .

The notion of asymptotic joint displacement is analogous to the classical notion of joint spectral radius from linear algebra. In this geometric setting, it was recently studied by Oregón-Reyes [?] and Breuillard-Fujiwara [?] who proved the geometric analogues of some of the main results on joint spectral radius. The previous result parallels [?, Theorem 1.7] where the effective support of the rate function of the norms of random matrix products was related to joint spectral radii. 1.2. Consequences for rank-one linear groups. Let us explain a consequence of our main theorem that partially answers a question raised in [?].

A simple linear algebraic group H of rank 1 over a local field k (e.g. SL 2 (R) or SL 2 (Q p )), has a natural, up to finite index, faithful action by isometries on its symmetric space or the associated Bruhat-Tits tree (X, d). The metric space (X, d) is a Gromov hyperbolic space.

One can find a finite dimensional representation of H such that for any x ∈ X and h ∈ H, the displacement functional d(x, h • x) is given by the logarithm of the associated operator norm ||.|| (see e.g. [?, Chapter 6,8] and [?, §6]). Moreover, the asymptotic translation length (h) corresponds to the logarithm of the spectral radius ρ(h) of h, defined by the spectral radius formula ρ(h) = lim n→∞ ||h n || 1 n . In this case, under the assumptions of Theorem 1.2, the existence of a convex rate function for 1 n (d(z n , z 0 )) follows from the main result of [?] (as well as, from Theorem 1.2).

It was conjectured [?, Conjecture 6.2] (see also [?, §5.15]) that if the support of the probability measure µ on H generates a Zariski-dense semigroup (equivalently, if µ is non-elementary), then the sequence 1 n log ρ(γ n ) satisfies a LDP and the rate function coincides with the rate function of the sequence 1 n log ||γ n ||. Under the assumption that the probability measure has finite support, this conjecture follows from Theorem 1.4 for simple rank one groups.

Corollary 1.7. Let H be a simple linear algebraic group of rank one over a local field k endowed with an absolute value |.|. Let µ be a finitely generated probability measure on H whose support generates a Zariski dense semigroup in H. Let ||.|| be an operator norm on a finite dimensional representation V of H as above and I : [0, ∞) → [0, ∞] be the rate function of the LDP of 1 n log ||γ n ||. Then, the sequence 1 n log ρ(γ n ) of random variables satisfies a LDP with rate function I.

The assumption that the support is finite may be replaced by the one that the measure has compact support. The authors decided not to write the article in this generality in order not to burden the proofs.

Detailed presentation of the article

The article is mostly self-contained and proofs only use a combination of elementary geometric and probabilistic arguments. In particular, unlike in [START_REF] Maher | Random walks on weakly hyperbolic groups[END_REF], [START_REF] Maher | Random walks, wpd actions, and the cremona group[END_REF] or in [START_REF] Sunderland | Linear progress with exponential decay in weakly hyperbolic groups[END_REF], we make no use of any boundary whatsoever.

In Section 3 we recall some basics on random walks, large deviation principles and hyperbolic geometry. As we shall see there, the proof of Theorem 1.2 boils down to studying, the exponential decay and the limiting behaviour of the probabilities (2.1)

-ln (P(d(z n , z 0 ) ≥ an)) n for every a ∈ (l, l max ), and

(2.2)

-ln (P(d(z n , z 0 ) ≤ an)) n for every a ∈ (l min , l); where l max is defined as the infimum of a's such that the limsup in (2.1) is finite and similarly for l min . We refer to (2.1) and (2.2) as deviations from above and below, respectively. A thorough investigation of these is the overall objective of Sections 4, 5, 6, 7, 8 and 9.

A very first observation is that a general sub-additivity argument due to Hamana [START_REF] Hamana | Asymptotics of the moment generating function for the range of random walks[END_REF], that we recall in Appendix B, gives an upper-bound on the probability of deviations from above: for any > 0, one has

(2.3) lim inf n→∞ -ln (P(d(z n , z 0 ) -ln ≥ n)) n > 0 .
Inequality (2.3) is very general; it holds for any group acting by isometries on any metric space without any restriction.

Remark 2.4. We observe that the exponential decay of the probability of a deviation from below cannot hold in the same generality as (2.3). In the examples below, we equip a group Γ with any left-invariant metric. We choose z 0 = id to be the identity element in Γ. We assume the rate of escape does not vanish for otherwise it makes no sense to compute deviations from below.

1. Let Γ be an amenable group and µ a symmetric probability measure with positive drift and whose finite support generates Γ (see e.g. [START_REF] Kaimanovich | Random walks on discrete groups: Boundary and entropy[END_REF]). Then, Kesten's theorem implies that the probability P(z n = z 0 ) does not decay exponentially fast:

- 1 n ln P(z n = z 0 ) -→ n→∞ 0.
Therefore deviations from below have a sub-exponential decay.

2. It is also possible to give examples of random walks on non-amenable groups for which deviations from below have a sub-exponential decay. Indeed start with an amenable group Γ and a finitely supported symmetric driving measure μ as in 1. Then let Γ be the direct product of Γ with your preferred non-amenable group, say the free group on two generators F 2 := A, B . Then Γ is non-amenable. We endow Γ with the metric d it inherits from the metric we chose on Γ, say d, and the usual word metric on F 2 that we denote with d (2) . Let µ be the product measure of μ on Γ with the lazy simple random walk driving measure

1 2 δ id + 1 8 (δ A + δ A -1 + δ B + δ B -1
) on F 2 . The two components of the random walk driven by µ, say (z n ), are then a random walk on Γ driven by μ for the first component, say (z n ) and a lazy simple symmetric random walk on F 2 for the second component, say (z (2) n ). The two random walks (z n ) and (z (2) n ) are independent. The rate of escape l of the random walk (z n ) is therefore the sum of the rate of escape of the random walk (z n ) with respect to d, say l, and the rate of escape of the lazy simple random walk (z

(2) n ), say l (2) .
For any real a such that l (2) < a < l = l (2) + l, we have that

P(d(id, z n ) ≤ an) ≥ P(z n = id)P(d (2) (id, z (2)
n ) ≤ an) . As in example 1., the term P(z n = id) has a sub-exponential decay. Since l (2) < a, the second term P(d (2) (id, z

(2) n ) ≤ an) tends to 1. Therefore P(d(id, z n ) ≤ an) has a sub-exponential decay.

Let us come back to the setting of Theorem 1.2. We denote with (y, z) x the Gromov product of y, z ∈ X seen from x:

(y, z) x := 1 2 (d(y, x) + d(z, x) -d(y, z)) .
Our main geometric tool is the existence of a Schottky set as defined in the next Definition 2.5 (Schottky set). Let X be a metric space, z 0 ∈ X and S a finite subset of Isom(X). We say that S is a Schottky set if there is a constant C > 0 such that for any pair y, z ∈ X we have {s ∈ S , (y,

s • z) z0 ≤ C} S ≥ 2 3 .
In Appendix A, we use a variation of the ping-pong lemma to prove that, when X is hyperbolic and geodesic and if the probability measure µ is non-elementary then there exists p ∈ N such that the support of µ * p contains a Schottky set.

We then deal separately with large deviations from above and from below.

As far as deviations from above are concerned, we already mentioned that the fact that a deviation from above has an exponentially small probability follows from Hamana's argument. In Section 4, we explain how the existence of the limit lim -1 n ln P(d(z n , z 0 ) ≥ an) for all a > l follows from a sub-additivity argument. In that argument, in order to compare P(d(z n+m , z 0 ) ≥ a(n + m)) with the product P(d(z n , z 0 ) ≥ an)P(d(z m , z 0 ) ≥ am), following [START_REF] Dal | On the growth of quotients of Kleinian groups[END_REF], we use a Schottky set. We implement this approach using an insertion trick as in [START_REF] Hamana | Large deviations for the range of an integer valued random walk[END_REF].

Let us now discuss deviations from below. It is immediate, again by sub-additivity, that the limit lim -1 n ln P(d(z n , z 0 ) ≤ an) exists for all a < l and defines a convex function; see Section 5. These already establishes the existence of LDP with a convex rate function for the sequence of random variables 1 n d n (see §3.2). Regarding their large deviations, the hardest (and hopefully most interesting) part is to show that the limit is positive.

Our starting point is a clever way to decompose a trajectory of a random walk that was introduced by A. Asselah and B. Schapira [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF] to study large deviations for the range of random walks on Z d . Adapted to our context, it yields the following quite general criterion for deviations from below to be exponentially small. Proposition 2.6. Let Γ be a countable group acting by isometries on a metric space X and µ a probability measure on Γ with a finite exponential moment. If one has

(2.7) lim inf p→∞ sup x∈X E (x, z p ) z0 p = 0 ,
then there is a positive convex function Ψ : ]l min , l[→]0, +∞] such that for all a ∈]l min , l[

(2.8) - ln P d(z n , z 0 ) ≤ an n -→ n→∞ Ψ(a) .
Proposition 2.6 is proved in Section 5. Note that, in Proposition 2.6, we do not need assume X is hyperbolic or geodesic.

Remark 2.9. The above proposition can be more generally stated for defective adapted cocycles as defined in [START_REF] Mathieu | Deviation inequalities for random walks[END_REF]. However we restrain from doing so in order not to burden this article with many definitions.

As a corollary of the previous proposition, we have the following We start quantifying the rough idea that, given any point x ∈ X, with high probability, the random walk tends to walk away from x. The next Theorem 2.12 plays the central role in the proof of Proposition 2.16. It is proved in Sections 6 and 7.

Theorem 2.12 (walking away uniformly). Let Γ be a countable group acting by isometries on a metric space X, µ a probability measure on Γ with a finite exponential moment and z 0 ∈ X. If the semigroup generated by µ contains a Schottky set and has unbounded orbits, then there is , c 1 , c 2 > 0 such that for any x ∈ X and all n ∈ N we have

P(d(z n , x) -d(z 0 , x) ≤ n) ≤ c 1 e -c2n .
Note that we do not require X to be hyperbolic nor geodesic.

Remark 2.13. In the setting of hyperbolic spaces, the above theorem can be extracted from [START_REF] Sunderland | Linear progress with exponential decay in weakly hyperbolic groups[END_REF] which builds on [START_REF] Maher | Random walks on weakly hyperbolic groups[END_REF] and on ideas of [START_REF] Mathieu | Deviation inequalities for random walks[END_REF]. We however decided to give a short alternative proof to keep the article self-contained and use-of-boundary free. Moreover, the proof proposed here also adapts to the setting of a finite first moment to give an alternative proof of [MT18a, Theorem 1.1, Theorem 1.2], see Subsection 7.1.

Theorem 2.12 in particular implies that the rate of escape does not vanish. More precisely, it implies the following linear progress with exponential tail property.

Definition 2.14 (Linear progress). Let X be a metric space. We say that a random path (z n ), with values in X, has linear progress with exponential tail if there is a constant

> 0 such that lim inf n→∞ -ln (P(d(z n , z 0 ) ≤ n)) n > 0 .
Note that the linear progress with exponential tail property is proved in [START_REF] Maher | Random walks on weakly hyperbolic groups[END_REF] under the extra assumption that µ has finite support.

The last two sections of the paper are devoted to deducing Proposition 2.16 from the walking away uniformly theorem. We shall rely on deviation inequalities. The next Proposition 2.15 is a variant of [MS20, Theorem 11.1]. It is proved in Section 8.

Proposition 2.15 (exponential-tail deviation inequalities). Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, µ a non-elementary probability measure on Γ with a finite exponential moment and z 0 ∈ X. If the random walk has linear progress with exponential tail, there are c 1 , c 2 > 0 such that for all 0 ≤ i ≤ n and all R > 0 one has

P((z n , z 0 ) zi ≥ R) ≤ c 1 e -c2R .
In Section 9, combining Proposition 2.15 and the walking away property from Theorem 2.12, we finally derive exponential bounds on the Gromov product (z n , x) z0 as announced.

Proposition 2.16 (uniform punctual deviations). Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, µ a non-elementary probability measure on Γ with a finite exponential moment and z 0 ∈ X. Then there are constants c 1 , c 2 > 0 such that for all x in X, all n ∈ N and all R > 0 one has

P((z n , x) z0 ≥ R) ≤ c 1 e -c2R .
Integrating with respect to R the bound in Proposition 2.16, one easily checks condition (2.7). The proof of Theorem 1.2 is now complete.

We observe that, taking n to ∞ in Proposition 2.16, we immediately derive bounds on the harmonic measure. We refer to Section 3 for all definitions regarding the next statement.

Corollary 2.17 (harmonic measure). Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, µ a non-elementary probability measure on Γ with a finite exponential moment and z 0 ∈ X. There exists D, C > 0 such that for any ζ ∈ ∂X and any r > 0 the harmonic measure ν on ∂X satisfies

ν(B(ζ, r)) ≤ C r D ,
where B(ζ, r) stands for the ball (with respect to the Gromov metric) on ∂X centred at ζ of radius r.

Harmonic measures were studied in great detail for proper hyperbolic spaces (see for example

[Kif90] [KL90] [BHM11] [BH]
). In particular the Hausdorff dimension of ν can then be computed and its multi-fractal spectrum described as in [START_REF] Tanaka | Dimension of harmonic measures in hyperbolic spaces[END_REF]. If Γ is hyperbolic and µ has a finite support, the inequality in Corollary 2.17 holds when D is replaced by the Hausdorff dimension [START_REF] Blachère | Harmonic measures versus quasiconformal measures for hyperbolic groups[END_REF]. In our context of a more general action, an upper-bound on the harmonic measure of a ball as in Corollary 2.17 is proved in [START_REF] Maher | Exponential decay in the mapping class group[END_REF] but only when µ has a finite support.

Section 10 is dedicated to the proof of Theorem 1.4. The proof uses Theorem 1.2 and can be split in two steps.

In a first part, using the existence of a Schottky set and an insertion trick in a similar way as in Section 4, we show that, given a prescribed speed α ≥ l the event τ (γ n ) ≥ αn is, at the exponential scale, as likely as the event d(z 0 , z n ) ≥ αn.

In the second part, for all prescribed speeds 0 ≤ α < l, we show that the event τ (γ n ) ≤ αn is, at the exponential scale, as likely as d(z 0 , z n ) ≥ αn. This step relies on Proposition 10.8 that uses an argument that finds, among the cyclic permutations of a given trajectory, a word whose displacement is uniformly close to the translation distance, which itself is invariant by cyclic permutation.

Section 11 is devoted to the proof of Theorem 1.5. There, we also record some deterministic consequences of our results and the ingredients that we develop.

For example, the following is a deterministic consequence of the combination of Theorems 1.2, 1.4 and 1.5.

Proposition 2.18. Given a countable, bounded and non-elementary subset B of Isom(X), the sequences of subsets 1 n d(B n • z 0 , z 0 ) and 1 n τ (B n ) of R converge to [ sub (B), (B)] with respect to the Hausdorff metric.

In other words, the sequences 1 n d(B n • z 0 , z 0 ) and 1 n τ (B n ) become more and more dense in the interval [ sub (B), (B)] as n grows. In fact, Theorems 1.2 and 1.4 can be seen as quantitative refinements of this convergence.

The previous proposition parallels the convergence result proven in [?, Theorem 1.3] for the vectors of singular values and moduli of eigenvalues of powers of a set of matrices. The interval [ sub (B), (B)] corresponds to what is called the joint spectrum of B in that article. For other deterministic consequences, see Section 11.

Acknowledgement. The authors are very grateful to A. Asselah et B. Schapira who explained to them the strategy developed in [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF] from which our Section 5 is inspired. They would also like to thank Mathieu Dussaule and Peter Haissinsky for helpful conversations and Nguyen-Bac Dang for his explanations on the Picard-Manin space.

First definitions and preliminary remarks

3.1. Basics on random walks. As a general reference on the topic, we recommend [START_REF] Woess | Random walks on infinite graphs and groups[END_REF]?]. Let Γ be an infinite, countable group and µ be a probability measure on Γ. Let (Ω, P) be a probability space and (ω i ) i∈N : Ω → Γ a sequence of I.I.D. random variables following the law µ. We call such a sequence the increments of the random walks. We then form the sequence of random variables

γ n := ω 1 • ω 2 • ... • ω n .
Let Γ act on a metric space (X, d) with a marked point z 0 ∈ X. The push-forward of the random walk with respect to the orbital map is defined by

Γ → X γ → γ • z 0 .
We denote with

z n := ω 1 • ω 2 • ... • ω n • z 0
the image of the sequence (γ n ). We call (z n ) the positions of the image random walk under the orbital map. We will often use the notation d n := d(z 0 , z n ) for short.

Remark 3.1. Note that the sequence of random variables (z n ) n∈N may not have the Markov property, even though the random walk (γ n ) n∈N is a Markov process.

The triangle inequality gives

d(z 0 , z m+n ) ≤ d(z 0 , z n ) + d(z n , z n+m ) .
If we suppose that µ has a finite first moment (i.e. E(d(z 0 , z 1 )) < ∞) we then get the inequality

E(d(z 0 , z m+n )) ≤ E(d(z 0 , z n )) + E(d(z n , z n+m )) = E(d(z 0 , z n )) + E(d(z 0 , z m )) .
For the last equality, we used the fact that d(z n , z n+m ) and d(z 0 , z m ) have the same law. The sequence (E(d n )) n∈N is therefore sub-additive and Fekete's lemma implies that the following limit exists

l := lim n→∞ E(d n ) n = inf n∈N E(d n ) n .
We call l the rate of escape of the image random walk. Note that Kingman's subadditive ergodic theorem [START_REF] Kingman | The ergodic theory of subadditive stochastic processes[END_REF] (see also [START_REF] Steele | Kingman's subadditive ergodic theorem[END_REF]) implies that the sequence dn n n∈N also P-almost surely converges towards l.

We observe that if one has a large deviations estimates as in Theorem 1.2 , then the measure µ has a finite exponential moment. Indeed the triangle inequality implies that, for any a, α ∈ R, we have

P(d 1 ≥ αn) P(d n-1 ≤ an) ≤ P(d n ≥ (α -a)n) .
In particular, for a > l and α > 2a, the definition of l imposes P(d n-1 ≤ an) → 1 whereas the large deviations estimates from above imply that

n → P(d n ≥ (α -a)n)
has an exponential decrease. Therefore, the sequence (P(d 1 ≥ αn)) n∈N must also decrease exponentially fast.

3.2. Some preliminaries on large deviations theory. Here, we briefly justify that to prove the existence of limits in deviations from below and above is equivalent to the existence of the rate function in the language of large deviations theory. Too keep the reading smooth, we postpone to Appendix C some further basic arguments in large deviations such as the explanation of how to identify the rate function using the limit Laplace generating function of the sequence 1 n d n .

Let Y be a Hausdorff topological space and let F be a σ-algebra on Y . Recall Definition 3.2. A sequence Z n of Y -valued random variables is said to satisfy a large deviation principle (LDP), if there exists a lower-semicontinuous function (called the rate function) I : Y -→ [0, ∞] such that for every measurable subset R of Y , we have

-inf I(α) α∈int(R) ≤ lim inf n→∞ 1 n log P(Z n ∈ R) ≤ lim sup n→∞ 1 n log P(Z n ∈ R) ≤ -inf I(α) α∈R ,
where int(R) denotes the interior and R the closure of R.

We also introduce the notion of exponential tightness which, in our case, is an easy consequence of the finite exponential moment assumption (see Lemma C.1).

Definition 3.3. A sequence Z n of Y -valued random variables is said to be exponentially tight if for every R > 0, there exists a compact set K ⊂ Y such that lim inf n→∞ -1

n log P(Z n ∈ K c ) ≥ R.
We have the following useful general criterion for the existence of a LDP with a proper rate function. For its proof, see [?, Theorem 4.1.11 & Lemma 1.2.18].

Theorem 3.4. Let Y be a topological space endowed with its Borel σ-algebra β Y , and Z n be a sequence of Y -valued exponentially tight random variables. Denote by µ n the distribution of Z n . Let A be a base of open sets for the topology of Y . For each α ∈ Y , define:

I li (α) := sup A∈A α∈A -lim inf n→∞ 1 n log µ n (A) and I ls (α) := sup A∈A α∈A -lim sup n→∞ 1 n log µ n (A)
Suppose that for all α ∈ Y , we have I li (α) = I ls (α). Then, the sequence Z n satisfies a LDP with the proper rate function I given by I(α)

:= I li (α) = I ls (α).
Note that in the setting of Theorem 1.2, the random variables Z n in the previous result are given by 1 n d(z n , z 0 ) and the space Y is [0, ∞). It is not hard to see that with Y ⊆ R, the hypotheses of the criterion provided by the previous theorem boil down to the existence as limits of decay rates of one sided intervals. The following lemma spells out the precise conditions.

Lemma 3.5. In the setting of Theorem 1.2, suppose that 1)(deviations from above) for every a ∈ (l, l max ), we have

(3.6) lim n→∞ -ln (P(d(z n , z 0 ) ≥ an)) n =: Ψ(a) ∈ (0, ∞)
is a convex function of a on ( , l max ) tending to 0 towards l,

2)(deviations from below) for every a ∈ (l min , l), we have

(3.7) lim n→∞ -ln (P(d(z n , z 0 ) ≤ an)) n =: Ψ(a) ∈ (0, ∞)
is a convex function of a on (l min , l), tending to 0 towards l. Then, the sequence 1 n d(z n , z 0 ) satisfies a LDP with the proper convex rate function I : [0, ∞) → [0, ∞] given by the extension of Ψ on [l min , l max ] by continuity to [0, ∞] and I(a) = ∞ for every a / ∈ [l min , l max ].

Proof. It follows from Lemma C.1 that the sequence 1 n d(z n , z 0 ) is exponentially tight. The rest of the proof consists of a tedious verification that the hypotheses of this lemma imply those of Theorem 3.4 (namely that I li (α) = I ls (α) for every α ≥ 0) and the extension of Ψ have the common values of I ls and I li . The details are straightforward and hence omitted for brevity.

Basics on hyperbolicity.

As general references on the topic one can recommend [START_REF] Gromov | Hyperbolic groups[END_REF], [START_REF] Kapovich | Boundaries of hyperbolic groups[END_REF] and [V 05] for the non proper setting. For a general metric space (X, d) we define the Gromov product of x 1 , x 2 with respect to x 0 as

(x 1 , x 2 ) x0 = 1 2 (d(x 0 , x 1 ) + d(x 0 , x 2 ) -d(x 1 , x 2 )) .
Definition 3.8. A metric space (X, d) is said to be Gromov-hyperbolic if there is a constant δ > 0 such that for any four points {x i } 0≤i≤3 we have

(x 1 , x 2 ) x0 ≥ min{(x 3 , x 1 ) x0 , (x 3 , x 2 ) x0 } -δ.
In this article, we will mostly deal with geodesic spaces. Recall that a metric space (X, d) is geodesic if the distance between any two points x, y is given by the length of a rectifiable path whose endpoints are x and y.

The following definition is to explain the terminology involved in the statement of Proposition 2.17. Let X be a hyperbolic metric space and x 0 ∈ X a base point.

Definition 3.9. We define the Gromov boundary, that we denote by ∂X, as the set of all sequences (x n ) n∈N ∈ X N such that lim n,m→∞

(x n , x m ) x0 = ∞ mod out the equivalence relation (x n ) ∼ (y n ) if (x n , y n ) z0 -→ n→∞ ∞.
We denote by [(x n )] the class of such a sequence.

One can easily verify that the construction of ∂X does not depend on the base point x 0 .

Choose

ζ := [(x ζ n )] ∈ ∂X and r > 0 and set B(ζ, r) := {ζ 2 := [(y n )] ∈ ∂X , lim inf n→∞ e -(x ζ n ,yn)x 0 ≤ r} .
We define a topology on ∂X by choosing the above sets as a generating basis of the open sets. The resulting topological space ∂X is metrizable. The sets B(ζ, r) are 'almost' balls of radius r. We refer to [V 05, Section 5] for more details.

Definition 3.10. Let λ, C > 0 and I a sub interval of N. A (λ, C)-quasi-geodesic indexed by I (simply called quasi-geodesic when not ambiguous) is a sequence (x n ) n∈I such that for any n, m ∈ I

λ -1 |n -m| -C ≤ d(x n , x m ) ≤ λ|n -m| + C .
In other words, a quasi-geodesic is a quasi-isometric embedding of I into X.

One can easily verify that quasi-geodesics indexed by N define a unique point in ∂X.

Recall the statement of fundamental Morse lemma.

Lemma 3.11 (Morse lemma). For any λ, C > 0 there is a constant L = L(Λ, C, δ) such that any (λ, C)-quasi-geodesic having the same endpoints are L-close to one another.

The following definitions are to explain the terminology 'non-elementary'.

Definition 3.12. An isometry γ of a hyperbolic space X is called loxodromic if for a point x ∈ X (equivalently any) the sequence (γ n • x) n∈Z is a quasi-geodesic.

In particular, a loxodromic element defines two points in the Gromov boundary γ + and γ -corresponding to the classes of the two quasi-geodesics defined by the future and the past. We say that two loxodromic elements γ 1 , γ 2 are independent if the fours points γ ± 1 , γ ± 2 are distinct. Definition 3.13. A semigroup acting on X by isometries is called non-elementary if it contains two independent loxodromic elements.

Recall a probability measure µ on a group Γ acting by isometries on a hyperbolic space X is said to be non-elementary when its support generates a non-elementary semigroup.

Non-elementary groups have a lot of elements spreading apart points of X. The proof of the following lemma is a variation around the proof of the well known ping-pong lemma. As we could not find any ready-to-use reference in this generality, we inserted a proof in Appendix A.

Proposition 3.14 (Existence of Schottky sets). Let Γ be group acting by isometries on a geodesic hyperbolic space X, z 0 ∈ X and µ a non-elementary probability measure on Γ. Then there is p ∈ N such that supp(µ * p ) contains a Schottky set.

Deviations from above

The goal of this section is to prove that (3.6) holds. In other words, we have the required large deviations estimates from above.

Proposition 4.1. Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, µ a non-elementary probability measure on Γ with a finite exponential moment and z 0 ∈ X. Then there is a non negative convex function Ψ : [0, ∞[→ R + ∪ {∞} which vanishes only on [0, l] such that for any a = l max

-ln P d(z n , z 0 ) ≥ an n -→ n→∞ Ψ(a) .
The part concerning Ψ > 0 on (l, ∞) follows from Hamana's argument taken from [START_REF] Hamana | Asymptotics of the moment generating function for the range of random walks[END_REF]. Namely, we will show in Appendix B that Proposition 4.2. Let X be a metric space and µ a probability measure on Isom(X) with a finite exponential moment. Then for any a > l we have

(4.3) lim inf n→∞ -ln P d(z n , z 0 ) ≥ an n > 0 ,
The proof of Proposition 4.2 only requires sub-additivity, which, for random walks, comes from the triangle inequality and the independence of the increments as shown in Section 3. The rest of this section is devoted to answer the second part of the question: show that the limit defining Ψ exists and that Ψ is convex.

The next proposition gives an almost sub-additivity relation.

Proposition 4.4. There is a constant c > 1 and an integer p ∈ N such that for any x, y in X and n, m > 0 we have

(4.5) P(d m+n+p ≥ x + y -c) ≥ c -1 • P(d m ≥ x) P(d n ≥ y) .
Before proving the above proposition, let us see how to use it to show that the limit defining Ψ exists and is convex.

Proof of (Proposition 4.4 ⇒ Ψ exists and is convex). Throught out the proof, p is fixed as in Proposition 4.4.

To apply Fekete's lemma, we substitute in (4.5), m -p for m and n -p for n to get that for any x, y > 0 and m, n ≥ p:

(4.6) P(d m+n-p ≥ x + y -c) ≥ c -1 • P(d m-p ≥ x) P(d n-p ≥ y)
. We now replace x with am + c and y with an + c in order to get that for all m, n > p

P(d m+n-p ≥ a(m + n) + c) ≥ c -1 • P(d m-p ≥ am + c) P(d n-p ≥ an + c) .
Thus we see that the sequence (-ln c -1 P(d n-p ≥ an + c) ) n≥p is sub-additive. Let us define

ψ n (a) := -ln c -1 P(d n-p ≥ an + c) n .
Fekete's lemma implies that, for all a, (ψ n (a)) n≥p converges; we denote with Ψ(a) the limit.

We now show that Ψ is convex. Indeed, using Inequality (4.6) one gets that, for any a, b > 0 and for any n ≥ p then

ψ 2n a + b 2 ≤ 1 2 (ψ n (a) + ψ n (b)) ,
which shows, letting n → ∞, that Ψ is convex. Note, in particular, that Ψ is continuous on the interval ]0, l max [. We now conclude showing that the sequence (-1 n ln P(d n ≥ an)) n∈N converges to Ψ(a) for a = l max .

We start with the observation that for any > 0 we have for n large enough

P(d n-p ≥ (a -)n + c) ≥ P(d n-p ≥ a(n -p)) ≥ P(d n-p ≥ an + c) , Therefore Ψ(a -) ≤ lim inf - 1 n ln P(d n ≥ an) ≤ lim sup - 1 n ln P(d n ≥ an) ≤ Ψ(a) .
(4.7)

The above inequality implies that if a > l max then Ψ(a) = ∞. In particular, using again the above inequality, if a > l max we get lim inf -

1 n ln P(d n ≥ an) ≥ Ψ l max + a 2 = ∞ = Ψ(a) .
We conclude showing that -1 n ln P(d n ≥ an) converges to Ψ(a) for a ∈]0, l max [. Since Ψ is convex and finite on ]0, l max [ it is in particular continuous. Letting → 0 in (4.7) we get that the sequence (-1 n ln P(d n ≥ an)) n∈N converges to Ψ(a) on ]0, l max [. Note first that the almost sure convergence of n -1 d n to l shows directly that Ψ = 0 on [0, l] (if l = l max ) using that Ψ is convex (in particular continuous).

One is left to show that Proposition 4.4 holds. Our strategy is inspired by the replacement trick proposed in [START_REF] Hamana | A large-deviation result for the range of random walk and for the Wiener sausage[END_REF] and by the use of Proposition 3.14, inspired by [START_REF] Dal | On the growth of quotients of Kleinian groups[END_REF].

Proof of Proposition 4.4. The first remark, made in [START_REF] Hamana | A large-deviation result for the range of random walk and for the Wiener sausage[END_REF], is that a way to construct a path of n + m + p steps is to start with two paths, one of n steps, another one of m steps, and a way to connect them using p steps. Requiring something on the finitely many steps in the middle, corresponding to the p steps, should have finite probability cost. In our case, we shall constrain our p-paths to have endpoints in a Schottky set S.

Recall that Proposition 3.14 implies the existence of a Schottky set S in the support of µ * p for some p. We choose such a p and let C denote the constant from Definition 2.5. We also let

ζ := inf s∈S P(γ p = s) ,
and

S sup := sup s∈S d(z 0 , s • z 0 ). z 0 z n z m z n z n+p z n+m+p s z 0 Figure 1.
On the left, the trajectories of the two random walks from z 0 to z n and from z 0 to z m := γ -1 n+p z m+n+p . On the right the concatenation of them with prescribed increment γ -1 n • γ n+p = s.

By definition of the Gromov product, for all m, n, p > 0 we have

d m+n+p = d n + d(z n , z m+n+p ) -2(z 0 , z n+m+p ) zn .
On the event γ -1 n • γ n+p ∈ S, by the triangle inequality we also have

d(z n , z m+n+p ) ≥ d(z n+p , z m+n+p ) -S sup .
Therefore, on the intersection of the events

γ -1 n • γ n+p ∈ S, d n ≥ x, d(z n , z m+n+p ) ≥ y and (z 0 , z n+m+p ) zn ≤ C we have d m+n+p ≥ x + y -2C -S sup .
Let us set c 2 := 2C + S sup . We get that, for all s ∈ S,

P(d m+n+p ≥ x + y -c 2 ) ≥ P(d n ≥ x, d(z n+p , z n+p+m ) ≥ y, γ -1 n • γ n+p = s, (z 0 , z m+n+p ) zn ≤ C) . Note when γ -1 n • γ n+p = s, then (z 0 , z m+n+p ) zn = (γ -1 n • z 0 , s • γ -1 n+p • z m+n+p ) z0 . Therefore, we have for all s ∈ S P(d m+n+p ≥ x + y -c 2 ) ≥ P(d n ≥ x, d(z n+p , z n+p+m ) ≥ y, γ -1 n • γ n+p = s, (γ -1 n • z 0 , s • γ -1 n+p • z m+n+p ) z0 ≤ C) .
The event γ -1 n • γ n+p = s only depends on the increments n + 1 ... n + p. Therefore it is independent of

d n ≥ x, d(z n+p , z n+p+m ) ≥ y and (γ -1 n • z 0 , s • γ -1 n+p • z m+n+p ) z0 ≤ C). Thus, we have for all s ∈ S P(d m+n+p ≥ x + y -c 2 )) ≥ ζ • P(d n ≥ x, d(z n+p , z n+p+m ) ≥ y, (γ -1 n • z 0 , s • γ -1 n+p • z m+n+p ) z0 ≤ C) . Let A := {d n ≥ x, d(z n+p , z n+p+m ) ≥ y, } .
Averaging with respect to S gives

P(d m+n+p ≥ x + y -c 2 )) ≥ ζ S • s∈S P(A ∩ (γ -1 n • z 0 , s • γ -1 n+p • z m+n+p ) z0 ≤ C) .
Rewriting the right above probabilities as expectations and permuting them with the summation yields

1 S • s∈S P(A ∩ (γ -1 n • z 0 , s • γ -1 n+p • z m+n+p ) z0 ≤ C) = E 1 A • {s ∈ S , (γ -1 n • z 0 , s • γ -1 n+p • z m+n+p ) z0 ≤ C} S .
Because of Proposition 3.14, we always have the following uniform lower bound

{s ∈ S , (γ -1 n • z 0 , s • γ -1 n+p • z m+n+p ) z0 ≤ C} S ≥ 2 3 .
Therefore,

P(d m+n+p ≥ x + y -c 2 )) ≥ 2ζ E(1 A ) 3 = 2ζ P(A) 3 . Recall that A = {d n ≥ x, d(z n+p , z n+p+m ) ≥ y} .
The event d n ≥ x (which depends only on the 1 ... n first increments) being independent of the event d(z n+p , z n+p+m ) ≥ y (which depends only on the n + p + 1 ... n + m + p increments), we have

P(d m+n+p ≥ x + y -c 2 )) ≥ 2ζ 3 • P(d n ≥ x) • P(d(z n+p , z n+p+m ) ≥ y) , ≥ 2ζ 3 • P(d n ≥ x) • P(d m ≥ y) ,
since d m and d(z n+p , z n+p+m ) follow the same law. We conclude setting c := max c 2 , 3 2ζ .

Deviations from below

This section is dedicated to investigating the deviations from below. The strategy of the proof of the following proposition is inspired from [START_REF] Asselah | Moderate deviations for the range of a transient random walk: path concentration[END_REF].

Proposition 5.1. Let Γ be a countable group acting on a metric space X and µ a probability measure with a finite exponential moment on Γ such that

(5.2) lim inf p→∞ sup x∈X E (x, z p ) z0 p = 0 .
Then there is a convex function Ψ : [0, ∞[→ R + ∪ {∞} which vanishes on [l, ∞] only such that for all a = l min (5.3)

-ln P d(z n , z 0 ) ≤ an n -→ n→∞ Ψ(a) .
We shall start by proving that the limit defining the function Ψ exists. This only requires sub-additivity. We will then prove the most difficult part of the proof, namely that Ψ > 0 under the assumption (5.2).

Proof that the limit exists. The proof does not require Assumption (5.2). By the triangle inequality and independence, we have

P(d n+m ≤ a(n + m)) ≥ P(d m ≤ am) P(d n ≤ an) . Therefore the sequence (-ln P(d n ≤ an)) n∈N is sub-additive. Let us define (Ψ n (a)) n∈N :=   -ln P(d n ≤ an) n   n∈N .
Fekete's lemma then gives that the sequence (Ψ n (a)) n∈N converges; we denote the limit with Ψ(a).

To show that Ψ is convex, one has to show that for all pairs (a, b) ∈ R 2 we have

Ψ a + b 2 ≤ Ψ(a) + Ψ(b) 2 .
Using again the triangle inequality we get

P d 2n ≤ a + b 2 • 2n ≥ P(d n ≤ an) P(d n ≤ bn) ,
and then

Ψ 2n a + b 2 ≤ Ψ n (a) + Ψ n (b) 2 .
We conclude by letting n tend to ∞.

Proof that Ψ > 0. We will now use Assumption (5.2).

Let us start by noticing that Proposition 5.1 is invariant under acceleration: given k ∈ N a measure µ with a finite exponential moment satisfies the conclusion of Proposition 5.1 if and only if the measure µ * k satisfies it.

Given a trajectory, we chop it into pieces of size j ∈ N and write the distance between the base point z 0 and the endpoint z n (where n = mj for some integer m) as a summation of I.I.D. random variables and a defect term.

Recall that the Gromov product of two points x, y ∈ Γ seen from z 0 is defined as

(x, y) z0 := 1 2 d(z 0 , x) + d(z 0 , y) -d(x, y) .
In particular, we have for any m, j > 0

2(z 0 , z mj ) z (m-1)j = d(z 0 , z (m-1)j ) + d(z mj , z (m-1)j ) -d(z 0 , z mj ) .
Equivalently,

d mj = d (m-1)j + d(z mj , z (m-1)j ) -2(z 0 , z mj ) z (m-1)j .

By an immediate induction we get

d mj = 1≤i≤m d(z ij , z (i-1)j ) -2 1≤i≤m (z 0 , z ij ) z (i-1)j .
Since the Gromov product is non negative, one has the following set inclusion

{d mj ≤ an} ⊂    1≤i≤m d(z ij , z (i-1)j ) ≤ a + l 2 n       1≤i≤m (z 0 , z ij ) z (i-1)j ≥ l -a 4 n    , which implies that P(d mj ≤ an) ≤ P   1≤i≤m d(z ij , z (i-1)j ) ≤ a + l 2 n   + P   1≤i≤m 2(z 0 , z ij ) z (i-1)j ≥ l -a 2 n   .
(5.4)

We shall see that there exists p such that both the above probabilities go exponentially fast to 0. The argument for the first one only uses classical large deviations estimates for I.I.D. random variables whereas the control of the second one will be handled using Assumption (5.2).

We start with the top probability appearing in (5.4). The random variables (d(z ij , z (i-1)j )) i∈N are I.I.D. and follow the law of d p . Therefore large deviations estimates for I.I.D. random variables with a finite exponential moment imply that

P 1≤i≤m d(z ij , z (i-1)j ) ≤ a+l 2 n
has an exponential decay as soon as

E(dj ) j > a+l 2 .
On the other hand, we already know that

E(dj ) j
converges to l and l > a+l 2 . Thus we conclude that there exists j 0 such that for all j ≥ j 0 , we have lim inf -

1 n ln P   1≤i≤m d(z ij , z (i-1)j ) ≤ a + l 2 n   > 0 .
We now deal with the second probability appearing in (5.4) using Assumption (5.2). Let us set := l-a 4 and let λ > 0. We start with the Chernoff bound

P   2 1≤i≤m (z 0 , z ij ) z (i-1)j ≥ l -a 2 n   ≤ e -λ n • E   exp   λ 1≤i≤m (z 0 , z ij ) z (i-1)j     .
(5.5)

We introduce the random variables

Π m (λ, j) := exp   λ 1≤i≤m (z 0 , z ij ) z (i-1)j   , and note that Π m (λ, j) = Π m-1 (λ, j) • exp λ(z 0 , z mj ) z (m-1)j .
Let us denote with (F i ) i∈N the filtration naturally associated to the random walk. We compute

E (Π m (λ, j)) = E E Π m-1 (λ, j) • exp λ(z 0 , z mj ) z (m-1)j F (m-1)j = E E Π m-1 (λ, j) • exp λ(γ -1 (m-1)j z 0 , γ -1 (m-1)j z mj ) z0 F (m-1)j = E Π m-1 (λ, j) • E exp λ(γ -1 (m-1)j z 0 , γ -1 (m-1)j z mj ) z0 F (m-1)j .
The last equality holds because Π m-1 (λ, j) is measurable with respect to F (m-1)j . Moreover, since γ -1 (m-1)j z mj is independent of F (m-1)j and since γ -1 (m-1)j z mj follows the same law than z j , we have

E (Π m (λ, j)) ≤ E Π m-1 (λ, j) • sup x∈X E exp λ(x, γ -1 (m-1)j z mj ) z0 ≤ E Π m-1 (λ, j) • sup x∈X E exp (λ(x, z j ) z0
) .

An immediate induction yields

E (Π m (λ, j)) ≤ δ(j, λ) m , where δ(j, λ) := sup x∈X E exp (λ(x, z p ) z0 ) .
Therefore,

P   2 1≤i≤m (z 0 , z ij ) z (i-1)j ≥ l -a 2 n   ≤ e -λ n δ(j, λ) m ≤ e -λ n+m ln(δ(j,λ))
≤ e m[ln(δ(j,λ))-λj ] .

We shall prove, using Assumption (5.2), that for all > 0 there exist j ≥ j 0 ∈ N and λ > 0 such that

(5.6) ln(δ(j, λ)) λj ≤ .
This is enough to conclude: we choose := /2 with j and λ such that (5.6) holds. Then

P   2 1≤i≤m (z 0 , z ij ) z (i-1)j ≥ l -a 2 n   ≤ e -λ n δ(j, λ) m ≤ e -n λ 2 ,
does indeed decrease exponentially fast to 0 as n → ∞.

It remains to prove Inequality (5.6).

Note first that for any x ∈ X we have

E exp (λ(x, z j ) z0 ) ≤ 1 + λ E ((x, z j ) z0 ) + λ 2 E ((x, z j ) z0 ) 2 exp (λ(x, z j ) z0 ) , since e x ≤ 1 + x + x 2 e x .
Using the upper bound (x, z j ) z0 ≤ d(z 0 , z j ), we get that

E exp (λ(x, z j ) z0 ) ≤ 1 + λ E ((x, z j ) z0 ) + λ 2 E z0 d 2 j e λdj . Assumption (5.
2) provides us with some j 1 such that, for all j ≥ j 1 , we have

sup x∈X E ((x, z j ) z0 ) ≤ j 2 .
We choose p ≥ max(j 0 , j 1 ). Then, taking the sup on x ∈ X, we get

δ(j, λ) ≤ 1 + λ j 2 + λ 2 E d 2 j e λdj .
We now choose λ = λ(p) small enough such that

λ 2 E d 2 j e λdj ≤ λ j 2 .
Then δ(j, λ) ≤ 1 + λ j , and therefore, since ln(1 + x) ≤ x, ln(δ(j, λ)) ≤ λ j .

Walking away uniformly

Definition 6.1. A sequence of random variables (Z n ) n∈N taking values in a metric space X is said to satisfy the walking away uniformly property if there are constants , α, C > 0 such that for all x ∈ X and for all n

∈ N P (d(Z n , x) -d(z 0 , x) ≤ n) ≤ Ce -αn .
Note that the above definition does not actually depend on the random variables (Z n ) n∈N but only on their laws. We shall use this fact in the proof of the following theorem by exhibiting a special set of random variables which have the desired law.

Theorem 6.2. Let Γ be a countable group acting by isometries on a metric space X and µ a probability measure on Isom(X) with finite exponential moment whose support generates a semigroup which contains a Schottky set and which has unbounded orbits. Then, (the law of ) (z n ) n∈N satisfies the walking away uniformly property.

6.1. Overview of the argument. The proof of the above theorem is quite intricate. Let us start by noticing that Theorem 6.2 is invariant under acceleration: given k ∈ N a measure µ with a finite exponential moment satisfies the conclusion of Theorem 6.2 if and only if the measure µ * k satisfies it. Therefore, since we assumed that µ is non-elementary and up to taking some power of µ, we can suppose that supp(µ) contains a Schottky set as in Proposition 3.14.

We start by showing that the above theorem is also invariant under sampling. More precisely, we will sample the positions (z n ) n∈N along the times when drawing increments in a given set S. We shall then use this sampling with respect to a Schottky set.

To make it precise, we will first exhibit a special family of increments (ω i ) i∈N (following the law µ) using the following random variables.

Let S ⊂ supp(µ) be any finite set and

ζ := min γ∈S µ(γ) > 0 .
Let (η i ) i∈N be independent random variables following the Bernoulli law of parameter ζ.

Let also (V i ) i∈N I.I.D. random variables independent of the η i 's taking values in Γ with (common) distribution

P(V i = γ) := (1 -ζ) -1 µ(γ) -ζ S if γ ∈ S (1 -ζ) -1 µ(γ) if γ / ∈ S
This distribution defines a probability measure on Γ since µ(γ) -ζ S ≥ 0 by definition of ζ and since its total mass is 1 by construction. Note also that the random variables (d(V i • z 0 , z 0 )) i∈N have a finite exponential moment since the measure µ has it (the laws of the d(V i • z 0 , z 0 ) are proportional to µ on all but finitely many γ ∈ Γ).

Let us now introduce the last set of random variables that we will need. Let (S i ) i∈N be I.I.D. random variables uniformly distributed on S independent of all the η i 's and of the V i 's:

P(S i = γ) := ( S) -1 if γ ∈ S 0 if γ / ∈ S .
In total, we are left with three sets of random variables that are all independent from one another. Finally, note that the following defined random variables (also taking values in Γ)

ω i := S i if η i = 1 V i if η i =
0 follow the law of µ. Indeed, by construction of the V i , the S i and the η i , one has

P(ω i = γ) = P(V i = γ)P(η i = 0) + P(η i = 1)P(S i = γ) if γ ∈ S P(V i = γ)P(η i = 0) if γ / ∈ S = µ(γ) .
We endow our new probability space with the filtration (F i ) i∈N corresponding to events which can be expressed using the random variables defined above only with indices ≤ i.

Let p ∈ N fixed. We now define the (S, p)-sampling that we will use through the following sequence of stopping times, defined inductively

τ (1) := inf {k ≥ p , η k = 1} τ (i) := inf {k ≥ p + τ (i -1) , η k = 1} if i > 1 .
The reason why we introduce an extra parameter p will become clear later. Intuitively, we will use this parameter in order to guarantee that the average distance the random walk travels between positions at times τ (i) and τ (i + 1) is large compared to the hyperbolic constant δ and the constant C appearing in Proposition 3.14.

Note that the random variables (τ (i + 1) -τ (i)) i>1 are I.I.D. following the law of τ (1) since the (η k ) k∈N are I.I.D..

The sampling on Γ is defined according to the previously defined stopping time. Namely, it is the random walk whose successive positions are

γ τ (n) = ω 1 • ... • ω τ (n) .
By construction, the random variable γ τ (n) follows the law µ * n τ , where µ τ (γ) := P(ω 1 • ... • ω τ (1) = γ) . Definition 6.3. The corresponding image random walk on X, whose positions are

z τ (n) = γ τ (n) • z 0 , is called the (S, p)-sampling of (z n ) n∈N .
The following proposition guarantees that one can prove Theorem 6.2 for sampled random walk instead of for the initial one. Proposition 6.4. Let µ be a probability measure with a finite exponential moment on a group Γ which acts on a metric space X. Let S ⊂ supp(µ), p > 0 and z 0 ∈ X. The image random walk driven by µ satisfies the walking away uniformly property if and only if its (S, p)-sampling satisfies it too.

In order to keep this subsection as an overview, we postpone the proof of the above Proposition to Subsection 6.3. The proof makes use of the following simpler lemma whose proof is also postponed. Lemma 6.5. Let µ be a probability measure with a finite exponential moment on a group Γ which acts on a metric space X, z 0 ∈ X and τ (1) as above. Then, the random variables d(z τ (1) , z p ), d(z τ (1) , z 0 ) and d(z τ (1)-1 , z p ) have a finite exponential moment.

We will then prove that the (S, p)-sampled random walk satisfies the walking away uniformly property. In order to do so, we shall introduce a last type of random walks. Intuitively, a (S, p)-sampling can be thought as a process in two steps. First, we ignore the first p increments and we do not draw 'bad elements' from S (corresponding to η k = 0) for a random time which follows a geometric law. Secondly, we draw an element uniformly from the set S. We shall make this precise by showing that a (S, p)-sampled random walk can be seen as a random walk whose odd increments correspond to the first step described above and the even ones to the second step, as in the following definition.

Let µ 1 be a probability measure on Γ, (X i ) i∈2N+1 I.I.D. random variables following the law µ 1 and (Y i ) i∈2N I.I.D. random variables uniformly distributed on the set S and independent of the X i s. Definition 6.6. Let (X i ) i∈2N+1 and (Y i ) i∈2N as above. We call (the laws of) the following sequence of random variables a (µ 1 , S)-random walk

z µ1,S n := X 1 • Y 2 • X 3 • ... • X n • z 0 if n is odd X 1 • Y 2 • X 3 • ... • Y n • z 0 if n is even
The following lemma relates the position at time n of a (S, p)-sampled random walk to the position at time 2n of an (µ 1 , S)-random walk.

Lemma 6.7. Let µ be a probability measure on a group Γ which acts on a space X, z 0 ∈ X and (τ (i)) i∈N as above. The sequence of random variables (z τ (n) ) n∈N follows the law of the sequence (z µ1,S 2n ) n∈N with µ 1 (γ)

:= P(ω 1 • ... • ω p • ... • ω τ (1)-1 = γ) .
In particular a (S, p)-sampled random walk satisfies the walking away uniformly property if and only if its associated (µ 1 , S)-random walk satisfies it too.

Proof. We first set the random variables X i and Y i as

Y 2i := ω τ (i) X 2i+1 := ω τ (i)+1 • .... • ω τ (i+1)-1 .
Then, by definition,

z τ (n) = X 1 • Y 2 • X 3 • ... • X 2n-1 • Y 2n • z 0 .
It follows from the independence properties of the random variables X i s, V i 's and η i s that the random variables (X 2i-1 , Y 2i ) i≥1 are I.I.D. Using the fact that, on the set τ (1) = k, we have

Y 2 = S k and X 1 = V 1 •...•V k-1
, it is also easy to see that X 1 and Y 2 are independent.

The next step is to find a criterion on µ 1 which guarantees that if S is a Schottky set then the associated (µ 1 , S)-random walk satisfies the walking away uniformly property. The following Proposition is the key and its proof will occupy Section 7.

Proposition 6.8. For any Schottky set S there is a constant M > 0 such that the following holds. For any probability measure µ 1 with a finite exponential moment and

γ∈Γ µ 1 (γ) d(z 0 , γ • z 0 ) > M,
the (µ 1 , S)-random walk satisfies the walking away uniformly property.

Let us see how to deduce Theorem 6.2 with all the material introduced above. Recall that we fix µ a probability measure on Γ and S a Schottky set contained in the support of µ. Proposition 6.4 implies that it is sufficient to prove the walking away uniformly property for the (S, p)-sampled random walk. Because of Lemma 6.7, we know that the (S, p)-sampled random walk is also a (µ 1 , S)-random walk with

µ 1 (γ) := P(ω 1 • ... • ω p • ... • ω τ (1)-1 = γ) .
It remains to show that the resulting (µ 1 , S)-random walk satisfies the conditions of Proposition 6.8. Note that Lemma 6.5 already asserts that µ 1 has a finite exponential moment.

The following lemma ensures that we can choose p such that the mean

γ∈Γ µ 1 (γ) d(z 0 , γ•z 0 ) exceeds M .
Lemma 6.9. Let Γ be a countable group acting by isometries on a metric space X and µ be a probability measure on Isom(X) whose support generates a semigroup with unbounded orbits and assume that µ has a finite first moment. Then

lim sup p→∞ E(d(z 0 , z τ (1)-1 )) = ∞ .
The following subsections are devoted to the proofs of all the above lemmata, except Proposition 6.8 which will be proven in Section 7.

6.2. Proof of Lemma 6.5. The differences of any two of the three random variables appearing in Lemma 6.5 obviously have a finite exponential moment. It is therefore sufficient to prove Lemma 6.5 for one of them only, say d(z p , z τ (1) ). The proof is a straightforward computation. It only uses that µ has a finite exponential moment together with the fact that τ (1) -p follows a geometric law of parameter 1 -ζ. Given λ > 0 we compute

E e λ d(z τ (1) ,zp) ≤ E   exp   λ p≤i≤τ (1)-1 d(z i , z i+1 )     ≤ k∈N E   exp   λ p≤i≤k-1 d(z i , z i+1 )   τ (1) = k   P(τ (1) = k) ≤ ζ k∈N E   exp   λ p≤i≤k-1 d(z i , z i+1 )   τ (1) = k   (1 -ζ) k-p .
We shall now see that for all > 0 there is λ > 0 such that for every k ∈ N (6.10)

E k := E   exp   λ p≤i≤k-1 d(z i , z i+1 )   τ (1) = k   < (1 + ) k .
It concludes the proof since we can choose such that (1

+ )(1 -ζ) -1 < 1.
Let us check (6.10). The event τ (1) = k is defined as η p = 0, η p+1 = 0, ...., η k = 1. Therefore, by construction of the X i 's, we have

E k = E   exp   λ p≤i≤k-1 d(V i • z 0 , z 0 )   e λd(z0,S k •z0) τ (1) = k   .
But τ (1) is a fonction of the η i 's only and therefore is independent of S k and independent of the (V i ) 1≤i≤k-1 . It yields

E k = E   exp   λ p≤i≤k-1 d(V i • z 0 , z 0 )   e λd(z0,S k •z0)   = E e λd(V1•z0,z0) k-1-p E e λd(z0,S k •z0) ,
since the V i 's are I.I.D. and independent of S k . This concludes the proof since we already saw that d(V i • z 0 , z 0 ) has a finite exponential moment and since S k has finite support.

6.3. Proof of Proposition 6.4. We will prove that: if the random walk (z τ (n) ) n∈N satisfies the walking away uniformly property then (z n ) n∈N satisfies it too. This is the only implication we need in this paper. The proof of the other implication is very similar.

Let , C and α such that for any x ∈ X we have

P d(z τ (n) , x) -d(z 0 , x) ≤ n ≤ Ce -αn .
We set β := E(τ ). We will show that (z βn ) n∈N satisfies the walking away uniformly property, which implies the result using again the invariance under acceleration.

Rewriting d(z 0 , z βn ) as d(z 0 , z βn ) -d(z 0 , z τ (n) ) + d(z 0 , z τ (n) ), we have

d(z βn , x) -d(z 0 , x) ≤ n 2 ⊂ d(z τ (n) , x) -d(z 0 , x) ≤ n ∪ d(x, z τ (n) ) -d(x, z βn ) ≥ n 2 .
And then:

P d(z βn , x) -d(z 0 , x) ≤ n 2 ≤ P d(z τ (n) , x) -d(z 0 , x) ≤ n + P d(x, z τ (n) ) -d(x, z βn ) ≥ n 2 .
Since we assumed that (z τ (n) ) n∈N satisfies the walking away uniformly property we already know that P d(z τ (n) , x) -d(z 0 , x) ≤ n has an exponential decay to 0, uniformly in x.

It remains then to show that

P d(x, z τ (n) ) -d(x, z βn )) ≥
n 2 decreases exponentially fast in n, uniformly in x. We will actually show that for all a > 0 P d(x, z τ (n) ) -d(x, z βn )) ≥ an decreases exponentially fast, uniformly in x. By the triangle inequality we have

i∈{τ (n),βn} d(z i , z i+1 ) ≥ d(z βn , z τ (n) ) ≥ d(x, z τ (n) ) -d(x, z βn ) ,
where, {τ (n), βn} denotes the set natural numbers in the interval bounded by {τ (n), βn}. Therefore

P   i∈{τ (n),βn} d(z i , z i+1 ) ≥ an   ≥ P d(x, z τ (n) ) -d(x, z βn ) ≥ an .
Note that the left hand side does not depend on x anymore. Define Z i := d(z i , z i+1 ). The desired result will follow once we prove that for all a > 0

P   i∈{τ (n),βn} Z i ≥ an  
decreases exponentially. The above summation is a summation of I.I.D. random variables over a random time interval. In order to control it, we shall first control the random time with a large deviations estimate for I.I.D. random variables and conclude by controlling the summation using again a large deviations estimate for I.I.D. random variables Recall that, by construction of the sampling, one has

τ (n) = 1≤i≤n (τ (i + 1) -τ (i)) ,
the (τ (i + 1) -τ (i))'s being I.I.D. distributed as τ (1) (in particular they have a finite exponential moment).

Let α > 0 such that α • E(Z 1 ) ≤ a 4 .
We use the large deviations estimate for τ (n) (which is a summation of I.I.D. random variables with a finite exponential moment): let c 1 , c 2 > 0 such that

P(|τ (n) -βn| ≥ αn) ≤ c 1 e -c2n .
Recall that β is the mean of τ . Therefore,

P   i∈{τ (n),βn} Z i ≥ an   ≤ c 1 e -c2n + P      i∈{τ (n),βn} Z i ≥ an    ∩ {|τ -βn| ≤ αn}   .
Since the Z i 's are non-negative, one has

P      i∈{τ (n),βn} Z i ≥ an    ∩ {|τ -βn| ≤ αn}   ≤ P   (β-α)n≤i≤(β+α)n Z i ≥ an   .
We conclude rewriting the right member of the above inequality as

P   (β-α)n≤i≤(β+α)n (Z i -E(Z i )) ≥ (a -2α • E(Z 1 ))n   .
Recall that we chose α such that a-2α•E(Z 1 ) ≥ a 2 . The Z i 's are I.I.D. with a finite exponential moment. Hence they satisfy large deviations estimates and the above probability decreases exponentially fast. 6.4. Proof of Lemma 6.9. By Lemma 6.5 we know that E(d(z p , z τ (1) )) is finite; besides, by construction of τ , it does not depend on p. Therefore, by the triangle inequality and linearity of the expectation, Lemma 6.9 will follow once we have proved that

lim sup p→∞ E(d(z 0 , z p )) = ∞ .
We start noticing that, for any R > 0, the following stopping time

τ R := inf{k ∈ N , d(z 0 , z k ) ≥ R}
is almost surely finite. Indeed, there is at least one element γ 0 in the semigroup Γ µ generated by supp(µ) such that γ 0 • B(z 0 , R) ∩ B(z 0 , R) = ∅ : recall we assumed that Γ µ has unbounded orbits. Therefore there exists k 0 such that P(γ k0 = γ 0 ) > 0. With probability one, there will be infinitely many times k such that γ -1 k γ k0+k = γ 0 . This last property implies that almost any path eventually leaves the ball of radius R around z 0 .

We conclude the proof of Lemma 6.9 with the following Lemma 6.11. Let µ be a probability measure on a group Γ acting by isometries on a metric space X and z 0 ∈ X. If for any R > 0 the time τ R is almost surely finite, then

lim sup p→∞ E(d(z 0 , z p )) = ∞ .
Proof. We have for any n ∈ N and any R > 0

P(z n / ∈ B(z 0 , R)) ≥ P(τ 2R ≤ n , d(z τ 2R , z n ) ≤ R) ≥ 0≤k≤n P(τ 2R = k , d(z k , z n ) ≤ R) ≥ 0≤k≤n P(τ 2R = k) • P(d(z k , z n ) ≤ R)
since the event τ 2R = k, that only depends on the first k increments of the walk and d(z k , z n ), that only depends on the later increments of the walk, are independent. The random variable d(z k , z n ) follows the same law as d(z 0 , z n-k ). Therefore

P(z n / ∈ B(z 0 , R)) ≥ 0≤k≤n P(τ 2R = k) • P(d(z 0 , z n-k ) ≤ R) ≥ P(τ 2R ≤ n) inf 0≤k≤n P(d(z 0 , z k ) ≤ R) ≥ P(τ 2R ≤ n)(1 -sup 0≤k≤n P(z k / ∈ B(z 0 , R))) .
Let a n := sup 0≤k≤n P(z k / ∈ B(z 0 , R)) ≥ P(z n / ∈ B(z 0 , R)). We have shown that

a n ≥ P(τ 2R ≤ n)(1 -a n ) ,
Recall we are assuming that τ 2R is almost surely finite. Therefore there exists n such that P(τ 2R ≤ n) ≥ 1/2. For such an n, we get

a n ≥ 1 5 .
Therefore there exists 0 ≤ k ≤ n such that

P(z k / ∈ B(z 0 , R)) ≥ 1 5 ,
which implies in particular for the same k that

E(d(z 0 , z k )) ≥ R 5 ,
thus concluding the proof.

7. Proof of Proposition 6.8

We prove the following more precise version of Proposition 6.8.

Proposition 7.1. Let S be a Schottky set and µ 1 be a probability measure with a finite exponential moment such that

γ∈Γ µ 1 (γ) d(z 0 , γ • z 0 ) > 6C + 6S sup
where C is as in Proposition 3.14 and S sup := sup s∈S d(z 0 , s • z 0 ). Then the corresponding (µ 1 , S)-random walk has the walking away uniformly property.

Proof. In order not to burden the notations, we shall denote by (Z n ) n∈N (instead of (z µ1,S n ) n∈N ) the successive positions in X of the (µ 1 , S)-random walk. To simplify a bit the exposition, let us first note that one can suppose the even increments of the walk to be µ 1 -increments and the odd ones to be Schottky increments. Indeed, since we assumed that µ 1 has a finite exponential moment, the walking away uniformly property does not depend on the first increment of the walk. With the notation introduced in Part 6 to define the (µ 1 , S) random walk, we have

Z n = Υ n • z 0 with Υ n := Y 1 • X 2 • ... • X n if n is even Y 1 • X 2 • ... • Y n if n is odd .
We start with the obvious equality

P d(Z 2n , x) -d(z 0 , x) ≤ n = P 0≤i≤n d(Z 2i+2 , x) -d(Z 2i , x) ≤ n .
For any x, y, z ∈ X, we let

B x (z, y) := d(z, x) -d(y, x) , so that 0≤i≤n d(Z 2i+2 , x) -d(Z 2i , x) = 0≤i≤n B x (Z 2i+2 , Z 2i ) := S n (x) . Since d(Z 2i+2 , z 0 ) -d(Z 2i , z 0 ) ≤ d(Z 2i+2 , Z 2i ), the random variable B x (Z 2i+2 , Z 2i
) has a finite exponential moment. Using Markov inequality for a small enough λ > 0, we get that P S n (x) ≤ n ≤ e λ n E e -λSn(x) .

We will be done once we prove that there exist λ > 0 and 0 < δ < 1 (which may depend on λ) such that for all x (7.2) E e -λSn(x) ≤ δ n .

Recall that we denoted by (F n ) n∈N the filtration of Ω with respect to the increments of the walk. Conditioning on F 2n-2 , we have

E e -λSn(x) = E E e -λSn-1(x) • e -λ(Bx(Z2n,Z 2(n-1) )) F (2n-2) = E E e -λSn-1(x) • exp -λB Υ -1 2n-2 x (Υ -1 2(n-1) Z 2n , z 0 ) F (2n-2) since S n-1 (x) is F 2n-2 measurable. Because Υ -1 2n-2 is F 2n-2 measurable and Υ -1 2(n-1) Z 2n is independent of F 2n-2 , we have E exp -λB Υ -1 2n-2 x (Υ -1 2(n-1) Z 2n , z 0 ) F (2n-2) ≤ sup y∈X E exp -λB y (Υ -1 2(n-1) Z 2n , z 0 ) F (2n-2) = sup y∈X E exp (-λB y (Z 2 , z 0 )) F (2n-2) .
We get by an immediate induction that

E e -λSn(x) ≤ δ(λ) n ,
where ,z0) .

δ(λ) := sup y∈X E e -λBy(Z2
We end this proof by showing Lemma 7.3. There is λ > 0 such that sup y∈X E e -λ(By(Z2,z0)) < 1 .

Proof. We denote by A c the complement of a set A. Given y ∈ X, we use the decomposition

B y (Z 2 , z 0 ) = B y (Z 2 , z 0 ) 1 A + B y (Z 2 , z 0 ) 1 A c ,
where A := {(Z 2 , y) z0 ≤ C} and C is the constant given by Proposition 3.14.

Note that on A, since the first increment of the walk is in S, we have

B y (Z 2 , z 0 ) ≥ d(Z 2 , z 0 ) -2C ≥ d(Z 2 , Z 1 ) -2C -d(Z 1 , z 0 ) ≥ d(Z 2 , Z 1 ) -2C -S sup .
On A c we use the trivial lower bound

B y (Z 2 , z 0 ) ≥ -d(Z 2 , z 0 ) ≥ -d(Z 2 , Z 1 ) -S sup .
We thus obtain the inequality e -λBy(Z2,z0) ≤ e -λ(d(Z2,Z1)-2C-Ssup)

1 A + e -λ(-d(Z2,Z1)-Ssup) 1 A c = e λSsup • e -λ(d(Z2,Z1)-2C) 1 A + e λd(Z2,Z1) 1 A c .
Since the distances appearing in the exponentials do not depend on Y 1 but only on X 2 , we have

E e -λBy(Z2,z0) X 2 ≤ e λSsup • e -λ(d(Z2,Z1)-2C) P(A | X 2 ) + e λd(Z2,Z1) P(A c | X 2 ) ≤ e λSsup • e -λ(d(Z2,Z1)-2C) α(X 2 ) + e λd(Z2,Z1) (1 -α(X 2 )) ,
where we set

α(X 2 ) := P(A | X 2 ) = P((Z 2 , y) z0 ≤ C | X 2 ) = {s ∈ S , (s • X 2 • z 0 , y) z0 ≤ C } S ,
using the fact that the first increment is uniformly distributed on S. Because S is a Schottky set, we readily get that

(7.4) α(X 2 ) ≥ 2 3 ,
for all y.

Next, we use the lower bound on E(d(Z 2 , Z 1 )) to argue that, in the upper-bound above, out of the two competing exponentials, the main contribution comes from the term e -λ(d(Z2,Z1)-C) .

Recall the general upper bound, e x ≤ 1 + x + x 2 e |x| and set

R(λ, X 2 ) := λ 2 (d(Z 2 , Z 1 ) + 2C
) 2 e λd(Z2,Z1) .

We then estimate

E e -λBy(Z2,z0) X 2 ≤ e λSsup • α(X 2 ) -λ(d(Z 2 , Z 1 ) -2C) α(X 2 ) + 1 -α(X 2 ) + λd(Z 2 , Z 1 ) (1 -α(X 2 )) + e 2λC R(λ, X 2 ) = e λSsup • 1 -λd(Z 2 , Z 1 ) (2α(X 2 ) -1) + 2λCα(X 2 ) + e 2λC R(λ, X 2 ) ≤ e λSsup • 1 - 1 3 λd(Z 2 , Z 1 ) + 2λC + e 2λC R(λ, X 2 ) .
We used the bound (7.4) and the fact that α(X 2 ) ≤ 1. Taking the expectation in this last inequality and using the lower bound on E(d(Z 2 , Z 1 )), we get that E e -λBy(Z2,z0) ≤ e λSsup 1 -2λS sup + e 2λC E(R(λ, X 2 )) .

Choose λ 0 > 0 such that

C 2 := E (d(Z 1 , Z 2 ) + C) 2 e λ0d(Z1,Z2) < ∞ .
Then, for all λ ≤ λ 0 , E(R(λ, X 2 )) ≤ C 2 λ 2 and we get that

E e -λBy(Z2,z0) ≤ e λSsup 1 -2λS sup + C 2 λ 2 e 2λC .
The right hand side of this last inequality is < 1 for some positive but small enough λ and this completes the proof. 7.1. The finite first moment case. As emphasised in Introduction, one can adapt Sections 6 and 7 to the setting where the measure µ has only a finite first moment to recover that l > 0 in this setting.

The general strategy is entirely the same, in particular the exact same sampling is to be performed. The only things to be modified are the statements of the various lemmas appearing in Subsection 6.1. We will not give all the details since it mainly repeats previously given arguments. Let us however indicate to the reader the changes and the non changes that one should perform to get positivity of the escape rate under a finite first moment.

Under the assumption that µ has a finite first moment, the proof of Proposition 6.4 gives

lim n→∞ 1 n E(d(z βn , z τ (n) )) = 0 ,
which implies in particular that the random walk (z βn ) has positive escape rate if and only if the random walk (z τ (n) ) has positive escape rate.

Lemma 6.5 should be rephrased by replacing every occurrences of 'finite exponential moment' with 'finite first moment'.

Lemmas 6.7 and 6.9 are identical (they do not require a finite exponential moment).

The assumption of Proposition 6.8 is to be modified with the assumption that µ 1 has a finite first moment. Its conclusion should be replaced with 'the (µ 1 , S)-random walk has positive escape rate'. The proof is even simpler in this case. Indeed, using the notations previously used, we start with the same decomposition but with taking the expectation:

E d(Z 2n , x) -d(z 0 , x) = 0≤i≤n E B x (Z 2i+2 , Z 2i ) .
We then skip all the Markov Inequality/conditioning to go directly to the following modified version of Lemma 7.3, which shows that l > 0 by taking z 0 = x in the above identity.

Lemma 7.5. There is c > 0 such that

inf y∈X E (B y (Z 2 , z 0 )) > c .
The proof follows the same lines as in the proof of Lemma 7.3.

Remark 7.6. One could be even more precise and get the following weak walking away uniformly property (compare with [?, Definition 1.4]).

Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, µ an admissible probability measure on Γ with a finite first moment and z 0 ∈ X. Then there is a constant c > 0 such that for all x ∈ X and for all n ∈ N E (d(z n , x) -d(z 0 , x))) ≥ c n .

Deviation inequalities

Recall that the walking away uniformly property, treated in the previous two sections, directly implies linear progress with exponential tail (Definition 2.14). The goal of this section is to show that a random walk which satisfies linear progress with exponential tail also satisfies the following property.

Definition 8.1. [MS20] Let (z n ) n∈N be a random path in a metric space X. We say that (z n ) n∈N satisfies the exponential-tail deviation inequality if there are constants C 1 , C 2 > 0 such that for all 0 ≤ i ≤ n and all R > 0 one has

P((z n , z 0 ) zi ≥ R) ≤ C 1 e -C2R .
We adapt the proof of [MS20, Theorem 11.1] to prove the following Proposition 8.2. Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X and µ a probability measure on Γ with a finite exponential moment. If the random walk has linear progress with exponential tail then it satisfies the exponential-tail deviation inequalities.

Remark 8.3. 1) We note that, unlike Theorem 6.2, the previous proposition assumes, among others, that X is a hyperbolic metric space.

2) In the case where Γ acts acylindrically on a geodesic hyperbolic space, this proposition is already proved in [MS20, Theorem 10.7].

x k1 x k1+1 x k x i+1 x i π ν (x k ) π ν (x k1 ) x k2+1 x k2 π ν (x k2+1 ) ρ ν
Figure 2. The green path represents de geodesic from x k1+1 to x k2 . Because of Items (2) and (3) of Lemma 8.4 their projections on υ must remain close to those of x k1 and x k2+1 . From Item (1) and by construction of N υ (x k ) one of the distance d(π υ (x k1 ), π υ (x k )), d(π υ (x k2+1 ), π υ (x k )) must be at least of the order (k 2 -k 1 )/5. This prevents the red path to enter in at least one of the balls B(π υ (x k1 , ρ) or B(π υ (x k2+1 , ρ), in green in the figure (with ρ = (k 2 -k 1 )/10). This implies that the length of the red path must be exponential in ρ since it avoids a ball through which the geodesic relating its endpoints passes (in green in the Figure ).

Using the triangle inequality we get

P (d(z α , z k ) ≥ R -100δ) ≤ P   α≤i≤k-1 d(z i , z i+1 ) ≥ R -100δ   ≤ P   α≤i≤β-1 d(z i , z i+1 ) ≥ R -100δ   = P   0≤i≤m-1 d(z i , z i+1 ) ≥ R -100δ   .
Taking the Laplace transform and using Markov's inequality we get that, for all λ > 0,

P   0≤i≤m-1 d(z i , z i+1 ) ≥ R -100δ   ≤ e λ(R-100δ) E e λd(z0,z1) m
≤ C e -λR E e λd(z0,z1) c3R .

From this last inequality, provided we choose λ such that E e λd(z0,z1) < ∞ and c 3 small enough, we deduce that

P (z n , z 0 ) z k > R) , k 2 = β , k 1 = α} ≤ Ce -cR
, for some constants C and c. Summing over the possible choices of β and α, we get the Lemma.

The next lemma deals with the remaining case corresponding to k 2 -k 1 ≥ c 1 R and concludes the proof of Proposition 8.2. Lemma 8.6. For any c 1 > 0, there are constants c 5 , c 6 such that we have

P((z n , z 0 ) z k > R , k 2 -k 1 ≥ c 1 R) ≤ c 5 e -c6R .
Proof. We shall prove that, for any m > 0, then

P((z n , z 0 ) z k > R , k 2 -k 1 = m) ≤ c 5 e -c6m .
The lemma follows by summing over all m ≥ c 1 R (with slightly different values for c 5 and c 6 ).

Let us then fix m > 0. In the same way as for the proof of Lemma 8.5 we first fix k 1 = α and k 2 = β with β -α = m and then use the union bound.

Recall that since we assumed that the walk has linear progress with exponential tail one has constants , c 7 , c 8 > 0 such that

P (d(z α , z β ) ≤ m) ≤ c 7 e -c8m .
There are also constants c 9 , c 10 such that

P d(z α , z α+1 ) ≥ d(z α , z β ) 100 ≤ P d(z α , z α+1 ) ≥ m 100 + c 7 e -c8m
≤ c 9 e -c10m , since d(z α , z α+1 ) has a finite exponential moment. A similar bound applies to d(z β , z β+1 ).

It remains to estimate the probability of the event, say A, when

d(z α , z β ) ≤ m, d(z α , z α+1 ) ≤ d(z α , z β )/100 and d(z β , z β+1 ) ≤ d(z α , z β )/100.
According to Lemma 8.4, on A, one has

α≤i≤β d(z i , z i+1 ) ≥ c 2 e c1m .
The probability of the above event is (super)-exponentially small in m = β -α.

Hitting measure

The purpose of this section is to prove the following proposition.

Proposition 9.1. Let Γ be a countable group acting non elementarily and by isometries on a geodesic hyperbolic space X and µ a non-elementary probability measure on Γ. Then, there are constants C, α > 0 such that for any p ∈ N and any x ∈ X, R > 0 we have

P((z p , x) z0 ≥ R) ≤ Ce -αR .
The above proposition implies that Assumption (5.2) holds since it implies that for any

x ∈ X E((z p , x) z0 ) ≤ C α .
Remark 9.2. If we further assume µ is symmetric, then there is an easy way to deduce Proposition 9.1 from Proposition 2.15. Indeed, let us rewrite as follows the square of the quantity we want to bound

P z0 ((z m , x) z0 ≥ R) 2 = P z0 ((z m , x) z0 ≥ R) • P z0 (( z m , x) z0 ≥ R) = P z0 ((z m , x) z0 ≥ R , ( z m , x) z0 ≥ R)
where z m is an independent copy of z m . The hyperbolicity of X implies that, for any four points

(x i ) 0≤i≤3 such that (x 1 , x 2 ) x0 ≥ R and (x 2 , x 3 ) x0 ≥ R then (x 3 , x 1 ) z0 ≥ min(R, R) -δ = R -δ . Therefore P z0 ((z m , x) z0 ≥ R , ( z m , x) z0 ≥ R) ≤ P z0 ((z m , z m ) z0 ≥ R -δ) .
Because we assumed the measure µ symmetric, the random variable (z m , z m ) z0 has the same law as (z 2m , z 0 ) zm . Therefore

P z0 ((z m , z m ) z0 ≥ R -δ) = P z0 ((z 2m , z 0 ) zm ≥ R -δ) .
We conclude the proof using the exponential-tail deviation inequality from Proposition 2.15:

P z0 ((z 2m , z 0 ) zm ≥ R -δ) ≤ c 1 e -c2(R-δ) .
Proof. We will use the walking away property from Theorem 2.12, the linear progress property from Definition 2.14 and exponential-tail deviation inequality from Proposition 2.15.

The geometric key of the proof is

Lemma 9.3. Let z, x, q, y ∈ X. There is R 0 = R 0 (δ) > 0 such that for every R ≥ R 0 if • (x, q) z ≥ R ; • 4R 5 ≤ d(z, y) ≤ R ; • (z, q) y ≤ R 5 , then d(z, x) -d(y, x) ≥ R 10 .
The proof of the above lemma is also illustrated in Figure 3.

Proof. Since d(z, y) ≥ 4R 5 and (z, q) y ≤ R 5 , by expanding (z, q) y , we get that d(q, z)d(q, y) ≥ 2R 5 . Therefore, using once more that d(y, z) ≥ 4R 5 , we obtain (q, y) z ≥ 3R 5 . Using this, the hypothesis (x, q) z ≥ R and (x, y) z ≥ min{(x, q) z , (q, y) z } -δ, we get (x, y) z ≥ 3R 5 -δ. Expanding (x, y) z and using d(z, y) ≤ R, we obtain d(z, x) -d(y, x) ≥ R 5 -2δ and hence d(z, x) -d(y, x) ≥ R 10 for all R large enough.

z q x y ≥ R ≤ R 4R/5 ≤ ≤ R/5
Figure 3. The geodesics from z to q and x fellow-travel for at time at least R.

Let us see how to use Lemma 9.3 (with z = z 0 , x = x, q = z p and with y = z k for some k) to get Proposition 9.1.

Let A R be the event A R := {d(z βR , z 0 ) ≤ R}. The linear progress with exponential tail property implies there exists β, c 1 > 0 such that

P(A R ) ≤ c -1 1 e -c1R .
Using large deviations estimates for I.I.D. random variables we know that there is α, c 2 > 0 such that for 0 ≤ j ≤ αR we have

P   1≤i≤j d(z i , z i+1 ) ≥ R/2   ≤ c -1 2 e -c2R .
In particular, setting B R := {∃i ∈ [0, αR] , d(z i , z 0 ) ≥ R/2} and using the triangle inequality together with the union bound, it gives a constant c 3 > 0 such that P(B R ) ≤ c -1 3 e -c3 . Note that we may choose α so that α ≤ β.

Using that µ has a finite exponential moment and the union bound, we get a constant c 4 > 0 such that, setting

C R := {∃i ∈ [0, βR] , d(z i , z i+1 ) ≥ R/5}, we have P(C R ) ≤ c -1 4 e -c4R .
Finally, using the exponential-tail deviation inequality, the union bound and setting

D R := {∃i ∈ [0, min(βR, p)] , (z p , z i ) z0 ≥ R/5}, we get a constant c 5 > 0 such that P(D R ) ≤ c -1 5 e -c5R .
Note that none of the constants introduced above depends on x.

It now remains to prove that there is a constant c 6 > 0 such that for all p ∈ N we have

P({(z p , x) z0 ≥ R} ∩ A c R ∩ B c R ∩ C c R ∩ D c R ) ≤ c -1 6 e -c6R . Note that a path in A c R ∩ B c R ∩ C c
R is such that all the steps are of length at most R/5; the path remains in B(z 0 , R/2) for the first αR steps but is outside the ball B(z 0 , R) at time min(p, βR). Observe these conditions imply that p ≥ αR. We thus conclude that the event

A c R ∩ B c R ∩ C c R is contained in the set {∃i ∈ [αR, min(p, βR)] , 4R/5 ≤ d(z 0 , z i ) ≤ R} .
Note also that any path in D c R must satisfy that for any 0 ≤ i ≤ min(p, βR), (z p , z 0 ) zi ≤ R/5 .

Therefore, the event

{(z p , x) z0 ≥ R} ∩ A c R ∩ B c R ∩ C c R ∩ D c R is contained in the event {(z p , x) z0 ≥ R}∩ {∃i ∈ [αR, min(p, βR)] such that (4R/5 ≤ d(z 0 , z i ) ≤ R and (z p , z 0 ) zi ≤ R/5)} .
Using the union bound,

P {(z p , x) z0 ≥ R}∩ {∃i ∈ [αR, min(p, βR)] such that (4R/5 ≤ d(z 0 , z i ) ≤ R and (z p , z 0 ) zi ≤ R/5)} ≤ αR≤i≤βR P ((z p , x) z0 ≥ R , 4R/5 ≤ d(z 0 , z i ) ≤ R , (z p , z 0 ) zi ≤ R/5) .
To conclude the proof, we show that there is a constant c 7 independent of p and x such that for for all αR ≤ i ≤ βR we have

P ((z p , x) z0 ≥ R , 4R/5 ≤ d(z 0 , z i ) ≤ R , (z p , z 0 ) zi ≤ R/5) ≤ c -1 7 e -c7R
. Using Lemma 9.3, we get that, for any αR ≤ i ≤ βR, we have

P((z p , x) z0 ≥ R , 4R/5 ≤d(z 0 , z i ) ≤ R , (z p , z 0 ) zi ≤ R/5) ≤ P d(z 0 , x) -d(z i , x) ≥ R 10 ≤ P (d(z 0 , x) -d(z i , x) ≥ 0) .
Using the walking away property, we get a constant c > 0 independent of x such that for every αR ≤ i ≤ βR

P (d(z 0 , x) -d(z i , x) ≥ 0) ≤ c -1 e -ci ≤ c -1 e -cαR .

Large deviation principle for translation distance

This section is devoted to the proof of Theorem 1.4 that we recall here for reader's convenience.

Theorem 10.1. Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, µ a non-elementary probability measure on Γ of bounded support. Then the sequence of random variables ( 1 n τ (γ n )) n∈N satisfies a large deviation principle with the same rate function as the one given by Theorem 1.2.

In order to prove this theorem, we will again make use of the criterion given by Lemma 3.5 based on Theorem 3.4.

As before, we shall distinguish the deviations from above and from below. Let us recall that, by definition, we have for any g ∈ Isom(X) and any x ∈ X

(10.2) τ (g) ≤ d(x, g • x) .
In particular for any α > l and any n ∈ N, we have

P(τ (γ n ) ≥ αn) ≤ P(d n ≥ αn) .
Recall that we denoted d n := d(z 0 , z n ). Then, for any n ∈ N * , we have

-1 n ln P(τ (γ n ) ≥ αn) ≥ -1 n ln P(d n ≥ αn) .
In view of Lemma 3.5, regarding deviations from above (α > l), one is then left to show that for l max = α > l, we have

(10.3) Ψ(α) := lim n→∞ -1 n ln (P(d n ≥ αn)) ≥ lim sup n→∞ -1 n ln (P(τ (γ n ) ≥ αn)) .
The proof of the above inequality will be carried out in Subsection 10.1. It is very close in spirit to the proof of Proposition 4.1 and relies on a Schottky-like argument with insertion trick.

For what concerns deviations from below (α < l), in view of (10.2), for all n ∈ N, we have

P(d n ≤ αn) ≤ P(τ (γ n ) ≤ αn) .
We are then left to prove that for all l min = α < l we have

(10.4) Ψ(α) := lim n→∞ -1 n ln (P(d n ≤ αn)) ≤ lim inf n→∞ -1 n ln (P(τ (γ n ) ≤ αn)) .
The strategy to prove the above inequality is more involved. We shall detail it in Subsection 10.2. The proof is based on a geometric tool whose proof is postponed to Subsection 10.3.

10.1. Comparison from above. The goal of this subsection is to show that (10.3) holds.

It is a consequence of the following Lemma 10.5. There exist a constant c > 0 and an integer p ∈ N such that for any α ∈ R + and > 0, there is an integer n 0 = n 0 ( , α) such that for any n ≥ n 0 we have

c P(d n ≥ (α + )n) ≤ P(τ (γ n+p ) ≥ α(n + p)) .
To see that the inequality given by this lemma implies (10.3), one observes that applying logarithm, dividing by n and taking the limsup, we get that for every α ∈ (l, l max ) and > 0

lim sup n→∞ -1 n ln P(τ (γ n ) ≥ αn) ≤ Ψ(α + ) ,
which gives (10.3) by continuity of Ψ.

The proof of Lemma 10.5 relies on the following geometric ingredient that we will use in combination with Proposition 3.14.

Lemma 10.6. For any x ∈ X and any Schottky set S, there is a constant L > 0 with the property that for every g ∈ Isom(X), there exists s ∈ S such that τ (sg)

≥ d(x, g • x) -L.
Proof. To simplify the notation, let us denote the basepoint by z 0 =: o. It clearly suffices to show the claim for o ∈ X. It is well-known (see e.g. [?, Ch.9, Lemma 2.2]) that for every g ∈ Isom(X), we have show that there exists a constant L > 0 such that for every g ∈ Isom(X), there exists

d(g • o, o) ≥ (g) ≥ d(g • o, o) -2(g • o, g -1 • o) o -
s ∈ S satisfying (sg • o, g -1 s -1 • o) o ≤ L .
Again by triangle inequality and definition of Gromov product, we have Proof of lemma 10.5. We shall use an insertion trick similar to the one employed in Section 4. Using Proposition 3.14, let S be a Schottky set in the semigroup generated by µ and p ∈ N such that S ⊂ µ * p .

|(sg • o, g -1 s -1 • o) o -(sg • o, g -1 • o) o | ≤ S sup
Let s ∈ S, we start by getting a lower bound to the following pivotal quantity.

P(d(z p , z n+p ) ≥ (α + )n , γ p = s) . On the one hand, since γ p = s is independent of d(z p , z n+p ) we have

P(d(z p , z n+p ) ≥ (α + )n, γ p = s) = P(d(z p , z n+p ) ≥ (α + )n) P(γ p = s) = P(d n ≥ (α + )n) µ * p (s) ≥ ζ • P(d n ≥ (α + )n) ,
where ζ := inf s∈S µ * p (s) > 0 since we assumed that S ⊂ supp(µ * p ) and because d n and d(z p , z n+p ) follows the same law.

On the other hand, we have

P(d(z p , z n+p ) ≥ (α + )n, γ p = s) = E(1 {d(zp,zn+p)≥(α+ )n , γp=s}
) . We get then for any s ∈ S and any n ∈ N that

ζ • P(d n ≥ (α + )n) ≤ E(1 {d(zp,zn+p)≥(α+ )n , γp=s} ) .
Averaging over the finite set S yields

ζ • P(d n ≥ (α + )n) ≤ E 1 S s∈S 1 {d(zp,zn+p)≥(α+ )n , γp=s} .
Thanks to Lemma 10.6, we have the deterministic upper bound s∈S 1 {d(zp,zn+p)≥(α+ )n , γp=s} ≤ S 1 {τ (γn+p)+L≥(α+ )n} , and then

ζ • P(d n ≥ (α + )n) ≤ P(τ (γ n+p ) + L ≥ (α + )n) ≤ P(τ (γ n+p ) ≥ α(n + p) -L + n -αp) ≤ P(τ (γ n+p ) ≥ α(n + p)) ,
for n ≥ n 0 with any n 0 such that -L + n 0 -αp > 0 , concluding the proof.

10.2. Comparison from below. The goal of this subsection is to show that (10.4) holds.

We shall actually prove the following stronger bound.

Lemma 10.7. For any α > 0 and any > 0, there is an integer N ∈ N such that for any n ≥ N , we have P(τ (γ n ) ≤ αn) ≤ (n + 1) P(d n ≤ (α + )n) . One easily sees that this lemma implies (10.4). Indeed, taking logarithm, dividing by n and considering the liminf, we get that for α ∈ (l min , l) and all > 0,

lim inf n→∞ -1 n ln P(τ (γ n ) ≤ αn) ≥ Ψ(α + ) .
This gives (10.4) in view of the continuity of Ψ.

The proof of Lemma 10.7 relies on the following geometric result.

Proposition 10.8. For any bounded subset B of Isom(X), for each β > 0 there exists N ≥ 1 so that the following holds. Let b 1 , . . . , b n ∈ B, for some n ≥ N , and let

g i = b 1 . . . b i and r i = b i+1 . . . b n . Then for every r ∈ [τ (g n ), d(z 0 , g n • z 0 )] there exists i so that | d(r i g i • z 0 , z 0 ) -r | ≤ βn.
We postpone the proof of the geometric proposition to Subsection 10.3.

Proof of Lemma 10.7. Let α < l and > 0. We start with rewriting

P(τ (γ n ) ≤ αn) = P(τ (γ n ) ≤ αn , d n ≥ (α + )n) + P(τ (γ n ) ≤ αn , d n < (α + )n) . (10.9)
We shall deal with the above two probabilities separately; for the second one we use the rough upper bound (10.10)

P(τ (γ n ) ≤ αn , d n < (α + )n) ≤ P(d n ≤ (α + )n) .
For the first one, we rely on the use of Proposition 10.8. We fix β := /2 and B := supp(µ) which is bounded by assumption. Let N be large enough so as to get the conclusions of Proposition 10.8. We shall use it with

• b i := ω i , the successive increments of the walk (and accordingly

g i = γ i ) ; • τ (γ n ) ≤ r := (α + /2)n ≤ d n .
Using that proposition, we deduce that for any n ≥ N , we have

{τ (γ n ) ≤ αn , d n ≥ (α + )n} ⊂ ∪ 1≤i≤n {|d(r i γ i • z 0 , z 0 ) -(α + /2)n| ≤ n/2} ⊂ ∪ 1≤i≤n {d(r i γ i • z 0 , z 0 ) ≤ (α + )n} .
Note that the random variables d(z 0 , r i γ i • z 0 ) follows the same law as d n for every i ∈ [1, n] since we assumed the increments to be independent and identically distributed. In particular we get

P(τ (γ n ) ≤ αn , d n ≥ (α + )n) ≤ 1≤i≤n P(d(z 0 , r i γ i • z 0 ) ≤ (α + )n) ≤ n P(d n ≤ (α + )n) .
Therefore, looking backward to (10.10) and (10.9) we get

P(τ (γ n ) ≤ αn) ≤ n P(d n ≤ (α + )n) + P(d n ≤ (α + )n) ≤ (n + 1) P(d n ≤ (α + )n) ,
concluding the proof.

10.3. Proof of Proposition 10.8. We start with some geometric preliminaries. Some of the results in this subsection might be known to experts, but we provide detailed proofs for completeness.

Let (X, d) be a hyperbolic space and let B be an arbitrary bounded subset of Isom(X).

To simplify the notation, let x ∈ X denote the choice of a basepoint.

Remark 10.11. For convenience, in the proofs below we will assume that d(x, b • x) ≤ 1 for each b ∈ B. This can be achieved by rescaling X, and it is readily seen that all the statements hold for X if and only if they hold for a rescaling of X, up to changing the constants.

The following lemma has a more general version where there is no group action involved, and the sequence of the g i • x is replaced by any discrete path with bounded jumps. We prefer to state the lemma in the form in which it will get used.

Lemma 10.12. Let B be a bounded subset of Isom(X). For every > 0 there exist D 0 , N ≥ 1 so that the following holds. Let b 1 , . . . , b n ∈ B, for some n ≥ N , and let

g i = b 1 . . . b i .
Let υ be a subpath of length ≥ n of a geodesic from x to g n • x. Then there exists i with d(

g i • x, υ) ≤ D 0 .
Proof. This can be deduced from [?, Claim 2 within Lemma 2.6], which in our setting says the following. There exist 0 > 0 and D > 0 (independent of x and g n ) so that, given disjoint balls B 1 , . . . , B k of radius D ≥ D centered on υ, any path α from x to g n x that avoids all B i satisfies l(α) ≥ k(1+ 0 ) D . Choose D 0 ≥ D +1 so that (1+ 0 ) D0-1 > 3D 0 / . Also, we let N ≥ 6D 0 / , and check that these choices work. In the setting of the statement, suppose by contradiction that we have d(g i • x, υ) > D 0 for all i. Then we can find at least k ≥ n/(2D 0 ) -1 ≥ n/(3D 0 ) disjoint balls B i of radius D 0 -1 centered on υ so that the path α in X obtained concatenating geodesics from s i x to s i+1 x avoids all B i . The length of α is at most n, so we obtain:

n ≥ n 3D 0 (1 + 0 ) D0-1 > n, a contradiction.
Let δ ≥ 1 be a hyperbolicity constant for X. For g ∈ Isom(X), define

Min(g) := {z ∈ X : d(z, g • z) ≤ τ (g) + 4δ}.
Also, for z ∈ Z, denote by π g (z) a point in Min(g) so that d(z, π g (z)) ≤ d(z, Min(g)) + 1.

(That is, π g is coarsely the closest-point projection to Min(g).) We can and will assume that g • π g (z) = π g (g • z) holds for all g and z.

It is known that Min(g) is quasiconvex (see e.g. [?, Proposition 2.3.3] and [?, Proposition 2.28]), but we will only need the following special case of quasiconvexity, which has a very short proof:

Lemma 10.13. Let g ∈ Isom(X). If y ∈ Min(g), then any point on any geodesic from y to g • y is also contained in Min(g).

Proof. First, observe that given y ∈ X and a geodesic [y, g • y], any z ∈ [y, g • y] has

d(z, g • z) ≤ d(z, g • y) + d(g • y, g • z) = d(z, g • y) + d(y, z) = d(y, g • y).
The desired statement easily follows.

We now show that geodesics from z to g • z pass close to the projection points of the endpoints onto Min(g).

Lemma 10.14. There exists D 1 ≥ 0 so that the following holds. For every g ∈ Isom(X) and z ∈ X, we have that any geodesic υ from z to g • z passes D 1 -close to π g (z) and π g (g • z). Moreover, we have

d(z, g • z) ≥ 2d(z, π g (z)) + τ (g) -D 1 .
Proof. Consider any geodesic υ from z to g • z. We will show that υ passes (4δ + 2)-close to π g (z), the argument for π g (g • z) being similar. We will use 2δ-thinness of a quadrangle with vertices z, π g (z), π g (g • z), g • z.

Suppose by contradiction that υ does not pass (4δ + 2)-close to π g (z). Consider the point z on a geodesic from z to π g (z) at distance 2δ + 2 from π g (z). We observe that z cannot be 2δ-close to any geodesic [π g (z), π g (g • z)], for otherwise there would be a point q on said geodesic, whence on Min(g) by Lemma 10.13, which satisfies d(z, q) < d(z, π g (z)) -1, contradicting the defining property of π g . Also, z cannot be 2δ-close to υ by hypothesis, so z is 2δ-close to g([z, π g (z)]). But then it must be 4δ-close to the point on that geodesic at distance 4δ + 2 from π g (g • z), this point being g • z . We just showed d(z , g • z ) ≤ 4δ, which implies z ∈ Min(g). But d(z, z ) < d(z, π g (z)) -1, contradicting the defining property of π g (z). Now, the fact that υ passes (4δ + 2)-close to π g (z) and π g (g • z) implies the following inequality:

d(z, g • z) ≥ d(z, π g (z)) + d(π g (z), π g (g • z)) + d(π g (g • z), g • z) -4(4δ + 2).
The first and third terms on the right-hand side are both equal to d(z, π g (z)), while the second term is at least τ (g). Therefore, we can conclude by setting D 1 = 4(4δ + 2).

We are now ready to prove Proposition 10.8.

Proof (of Proposition 10.8). First, notice that for r ≥ d(g n • x, x) -n we can just choose i = n, so in the arguments below we assume r ≤ d(g n • x, x) -n.

Set d := (r -τ (g n ))/2, and assume that n is larger than the N from Lemma 10.12 with /4 replacing . We impose further constraints on n later.

Lemma 10.15. If n is sufficiently large, then we can find a subgeodesic υ of length n/4 of a geodesic υ from x to g n x so that any p ∈ υ has • d(p, q) ≤ D 1 + δ for some q on a geodesic from x to π gn (x),

• |d(p, π gn (x)) -d| ≤ n/3.

Proof. We let p 0 be the point along υ so that

d(x, p 0 ) = d(x, π gn (x)) -d -n/4 = d,
and we let υ be the subgeodesic of υ of length n/4 with starting point p 0 . We now check that, for n large enough, this is all well-defined, and that υ has the required property. Let us make the preliminary observation that

d(x, g n • x) ≤ d(x, π gn (x)) + d(π gn (x), π gn (g n x)) + d(π gn (g n x), g n x) ≤ 2d(x, π gn (x)) + τ (g n ) + 4δ.
Observe now that we have

d ≤ (d(x, g n • x) -n -τ (g n ))/2 ≤ d(x, π gn (x)) + 4δ -n/2, implying d ≥ d -4δ + n/4,
(x)) -D 1 = d + d + n/4 -D 1 ≥ d + n/4.
The inequalities we just showed imply that p 0 and υ are well-defined and, furthermore, that υ is a subgeodesic of υ .

Considering a triangle with vertices x, p , π gn (x) and containing υ , we see that any point on υ , whence any point on υ, is (D 1 + δ)-close to a point on a geodesic from x to π gn (x).

In particular, for any p ∈ υ we have

|d(p, π gn (x)) + d(x, p) -d(x, π gn (x)| ≤ 2D 1 + 2δ,
and hence

|d(p, π gn (x)) -d| ≤ |d(x, π gn (x)) -d(x, p) -d| + 2D 1 + 2δ ≤ |d(x, π gn (x)) -d(x, p 0 ) -d -d(p 0 , p)| + 2D 1 + 2δ ≤ | n/4 -d(p 0 , p)| + 2D 1 + 2δ ≤ n/4 + 2D 1 + 2δ.
Provided that n is large enough, this concludes the proof of the claim.

By Lemma 10.12, there exists i so that we have d(g i , p) ≤ D 0 for some p ∈ υ, and by the claim we have d(p, q) ≤ D 1 + δ, whence d(g i • x, q) ≤ D 0 + D 1 + δ, for some q on a geodesic from x to π gn (x). Notice that we can assume that π gn (q) = π gn (x) since d(q, π gn (x)) = d(z, π gn (x)) -d(q, x) ≤ d(x, Min(g n )) + 1 -d(q, x) ≤ d(q, Min(g n )) + 1.

In particular, in view of Lemma 10.14, we have d(q, g n • q) ≥ 2d(q, π gn (x)) + τ (g n ) -D 1 .

We can now compute

d(x, r i g i • x) = d(g i • x, g n g i • x) ≥ d(q, g n • q) -2(D 0 + D 1 + δ) ≥ 2d(q, π gn (x)) + τ (g n ) -3(D 0 + D 1 + δ) . Hence, d(x, r i g i • x) ≥ 2d + τ (g n ) -2 n/3 -5(D 0 + D 1 + δ) = r -2 n/3 -5(D 0 + D 1 + δ).
For n sufficiently large, this last quantity is ≥ r -n.

On the other hand, we also have

d(x, r i g i • x) = d(g i • x, g n g i • x) ≤ d(p, π gn (x)) + d(π gn (x), π gn (g n • x)) + d(g n • p, π gn (g n • x)) + 2D 0 ≤ 2d + 2 n/3 + 2D 1 + τ (g n ) + 4δ + 2D 0 ≤ r + 2 n/3 + 2D 0 + 2D 1 + 4δ.
For n sufficiently large, this last quantity is ≤ r + n, concluding the proof.

Support of the rate function

This section is devoted to the proofs of Theorem 1.5 and some deterministic consequences of our results given by Propositions 2.18, 11.9.

11.1. Proof of Theorem 1.5. Let µ be a non-elementary probability measure on Isom(X) and I : [0, ∞) → [0, ∞] the rate function given by Theorem 1.2. Denote by B the support of µ. Using Proposition 3.14, let p ∈ N such that B p contains a Schottky set S.

1) Suppose that the interval given by the effective support of I has non-empty interior. Taking α < β in the interior of D I , we see that for some δ < 1 2 (β -α) and for every t ∈ N large enough, we have P( 1 t d(z 0 , z t ) ≥ β -δ) ≥ e -tI(β) > 0 and P( 1 t d(z 0 , z t ) ≤ α + δ) ≥ e -tI(α) > 0. So, for every t large enough, there exist elements g 1 (t), g 2 (t) in B t satisfying d(g 1 (t) • z 0 , z 0 ) ≤ t(α + δ) and d(g 2 (t) • z 0 , z 0 ) ≥ t(β -δ). Applying Lemma 10.6 to g 2 (t), we obtain an element g 2 (t) ∈ B p+t with τ (g 2 (t)) ≥ t(β -α) -L. Similarly, multiplying g 1 (t) with the p th -power of a fixed element h in B, we obtain hg 1 (t) ∈ B p+t with τ (hg 1 (t)) ≤ d(hg 1 (t) • z 0 , z 0 ) ≤ t(α + δ) + pd(h • z 0 , z 0 ). Since 2δ < β -α and the difference |τ (.)-(.)| is uniformly bounded, non-arithmeticity follows provided that t is large enough.

For the other direction, since µ is non-elementary and non-arithmetic, it is easy to see that there exists n 0 ∈ N such that the support of µ * n0 contains two hyperbolic elements h, h with disjoint sets of fixed points as well as two elements g, g with distinct translation distances. Let ν be the probability measure given by the restriction of µ * n0 to {g, g , h, h } (here some of the elements can be the same). It follows that ν is non-elementary and satisfies ν ≤ Cµ * n0 for some constant C > 0. It is readily observed that, if we denote by I µ and I ν , the rate functions given by Theorem 1.2 of the random walks, respectively, driven by µ and ν, we have I ν (α) ≥ n 0 I µ ( α n0 ) -log C for every α ≥ 0. Now, as ν has bounded support, the claim will follow from 2. applied to D Iν , since for the support B ν of ν, we clearly have sub (B ν ) < (B ν ).

2) The fact that D I ⊆ [ sub (B), (B)] is plain by definitions of sub (B) and (B). So we only need to prove D I ⊇ ( sub (B), (B)). There is nothing to prove if sub (B) = (B), so suppose (B) > sub (B). First, suppose that l = sub (B) and let α ∈ ( sub (B), (B)) be such that α ≤ l. Then, by definition of sub (B), there exists n 0 ∈ N and g ∈ B n0 such that 1 n0 d(g • z 0 , z 0 ) < α. Clearly, µ * n0 (g) > 0. Using Theorem 1.2, we can now write,

I(α) ≤ -lim sup n→∞ 1 n log P( 1 n d(z n , z 0 ) < α) ≤ -lim inf t→∞ 1 tn 0 log P( 1 tn 0 d(z tn0 , z 0 ) < α) ≤ -lim inf t→∞ 1 tn 0 log P(γ tn0 = g t ) ≤ -lim t→∞ 1 tn 0 log P(γ n0 = g) t = - 1 n 0 log µ * n0 (g) < ∞,
where in the first inequality we used the convexity of I and the fact that α ≤ l, in the second inequality we used the subadditivity of the displacement functional g → d(g •z 0 , z 0 ) and in the third inequality we used the fact that the random walk increments are i.i.d.

Unlike the previous case, the proof of the other case uses the existence of Schottky sets; namely, we will make crucial use of Proposition 4.4.

Suppose that l = (B) and let α, β ∈ ( sub (B), (B)) be such that β > α ≥ l. By definition of (B), for every n ∈ N, there exists g ∈ B n such that 1 n d(gz 0 , z 0 ) ≥ β. Let the constant c > 1 and integer p ∈ N be given by Proposition 4.4. Fix n 0 ∈ N large enough so that (n 0 + p)α < n 0 β -c. By succesive applications of Proposition 4.4, for every integer k ≥ 1, we have (11.1)

P(d kn0+(k-1)p ≥ k(n 0 β -c)) ≥ c -k P(γ n0 = g) k .
Therefore, we have

-I(α) ≥ lim sup n→∞ 1 n log P(d n ≥ nα) ≥ lim sup k→∞ 1 kn 0 + (k -1)p log P(d kn0+(k-1)p ≥ k(n 0 β -c)) ≥ lim sup k→∞ k kn 0 + (k -1)p (log P(γ n0 = g) -log c) > -∞,
where in the first inequality, we used the convexity of I and the fact that α ≥ l, in the second inequality we used the choice of n 0 so as to satisfy (n 0 + p)α < n 0 β -c, in the third inequality we used (11.1) and the last inequality follows since g ∈ B n0 and hence P(γ n0 = g) > 0.

3) If sub (B) = (B), then l = (B) and I( (B)) = 0 so that by 2) of Theorem 1.5, we have D I = { (B)}. Therefore we suppose that sub (B) < (B) and we only need to show that on ( sub (B), (B)), the rate function I is bounded above by -min g∈B log µ(g) < ∞; lower semi-continuity of I then entails that I is bounded above by the same quantity on [ sub (B), (B)] proving the claim. So let α ∈ ( sub (B), (B)). By 2), α ∈ D I and by Theorem 1.2, for any δ > 0, for every small enough r > 0 and large enough n ∈ N, we have

(11.2) 0 < e -n(I(α)+δ) ≤ P(α -r ≤ 1 n d n ≤ α + r) ≤ e -n(I(α)-δ) .
It follows that for every such n ∈ N, there exists g n ∈ B n with 1 n d(z 0 , g n •z 0 ) ∈ [α-r, α+r]. By the i.i.d. property of random walk increments, writing g n as a product h 1 . . . h n with h i ∈ B, it follows that P(γ n = g n ) ≥ (min s∈B µ(s)) n . Plugging this in (11.2), since δ > 0 is arbitrary, we deduce that I(α) ≤ -min s∈B log µ(s), as required.

The following is a consequence of the first part of the proof of 1) above. Indeed, the same proof shows that for a bounded set B, if sub (B) = (B), then B is non-arithmetic. The converse implication being obvious, one gets Corollary 11.3. Given a countable non-elementary and bounded subset B of the isometry group of a hyperbolic space (X, d), the set B is non-arithmetic if and only if sub (B) = (B).

11.2.

Examples of rate function exploding on the boundary. We now construct some examples illustrating in the setting of Theorem 1.5 that when the support of the probability measure is not finite, the rate function of LDP can explode on sub (supp(µ)) or (supp(µ)) or both. In fact, by considering the action of SL 2 (R) on the Poincaré disc D and using the relation Notice also that by elementary plane hyperbolic geometry, for every g ∈ Γ, we have For any probability measure µ on S, the random variables d n = d(z n , z 0 ) satisfies a LDP with some rate function I; this follows from Theorem 1.2 if the support of µ contains a i 's and b i 's (so that µ is non-elementary) and from classical theorem of Cramér if the support contains only a i 's or b i 's. The inequality (11.8) entails by Theorem 3.4 (or using [?, Theorem 4.2.13]) that 1 n τ (γ n ) satisfies a LDP with rate function I too. Now let α k > 0 be such that k≥1 α k = 1 2 and consider µ 1 = 1 2 δ a1 + k≥1 α k δ b k supported on S 1 and µ 2 = 1 2 δ b1 + k≥1 α k δ a k supported on S 2 and µ = 1 2 (µ 1 + µ 2 ) supported on S. Denote by I 1 , I 2 and I the rate functions of the LDP of 1 n d(z n , z 0 ) when the driving probability measure is, respectively, µ 1 , µ 2 and µ. Using Theorem 1.5 and Stirling's formula, it is not hard to deduce from (11.6) that (S 1 ) / ∈ D I1 , and from (11.7) that sub (S 2 ) / ∈ D I2 , and finally, that we have D I = ( sub (S), (S)). Moreover, using (11.5), one sees that D I1 = [ sub (S 1 ), (S 1 )) and D I2 = ( sub (S 2 ), (S 2 )]. 11.3. Deterministic consequences. We finally mention a deterministic consequence of the geometrical ingredients that we develop and also complete the proof of Proposition 2.18. d,C). We note that a stronger (without the non-elementary assumption) form of Proposition 11.9 as well as more general Bochi-type inequalities were recently proven by Oregón-Reyes [?] and by Breuillard-Fujiwara [?]. We provide a short proof for the nonelementary case.

Proof. Assume for a contradiction that we have ∞ (B) < (B). It follows that there exists δ > 0 such that for every n ≥ 1, there exists g n ∈ B n with 1 n d(z 0 , g n • z 0 ) ≥ ∞ (B) + δ. By Proposition 3.14, Lemma 10.6 and the fact that |τ (.) -(.)| is uniformly bounded, we deduce that for every n large enough, there exists f n ∈ F ⊂ B p such that 1 n (f n g n ) ≥ ∞ (B) + δ/2. Since f n g n ∈ B p+n , we deduce that for every n ∈ N large enough, we have (f n g n ) p + n ≥ ∞ (B) + δ 4 .

Lemma A.3. For any λ, C > 0 there is a constant K 0 > 0 such that for any (λ, C)quasi-geodesic (x n ) n∈Z , any m ≤ n ≤ p, and any K ≥ K 0 we have

(A.4) (O K (x m , x n )) c ⊂ O K (x p , x n ) .
Proof. The Morse Lemma gives some L so that for all m ≤ n ≤ p any geodesic from x m to x p passes L-close to x n . In particular, this implies (x m , x p ) xn ≤ L. Lemma A.5. For any λ, C > 0 there is a constant K 0 > 0 such that for any K ≥ K 0 there exists N with the following property. For any (λ, C)-quasi-geodesic (x n ) n∈Z , any m ≤ n ≤ p with m -n ≥ N , and any K ≥ K 0 we have This forces (x p , x) xm ≤ K + δ, that is, x ∈ O K+δ (x p , x m ), as required.

(
We will also need the next lemma to set up the ping-pong table.

Lemma A.7. Let x 0 ∈ X and γ be a loxodromic isometry of X. Then, there exists K 2 > 0 such that for any sufficiently large n > 0 we have

γ 2n O K2 (x 0 , γ -n • x 0 )) c ⊂ O K2 (x 0 , γ n • x 0 ) .
Note that, since γ is an invertible isometry, we also have

γ -2n (O K2 (x 0 , γ n • x 0 )) c ) ⊂ O K2 (x 0 , γ -n • x 0 ) .
Proof. Since, by definition, the sequence (γ n • x 0 ) n∈Z is a quasi-geodesic one deduces from Inclusion (A.6) that

O K (x 0 , γ -n • x 0 ) ⊂ O K+δ (γ n • x 0 , γ -n • x 0 ) ,
where we choose K satisfying both Lemma A.3 and Lemma A.5 and n is sufficiently large. (K only depends on the coefficients (λ, C) of the quasi-geodesic (γ n • x 0 ) n∈Z .) Taking the complementary sets, we get that

(O K+δ (x 0 , γ -n • x 0 )) c ⊂ (O K (γ n • x 0 , γ -n • x 0 )) c .
We set K 2 := K + δ. Now we apply γ 2n to get

γ 2n O K2 (x 0 , γ -n • x 0 )) c ⊂ γ 2n O K (γ n • x 0 , γ -n • x 0 )) c ⊂ O K (γ 3n • x 0 , γ n • x 0 )) c .
We now use (A.4) (applied to the reverse of (γ n • x 0 ) n∈Z ) with 0 ≤ n ≤ 3n to get that

O K (γ 3n • x 0 , γ n • x 0 )) c ⊂ O K (x 0 , γ n • x 0 )
⊂ O K2 (x 0 , γ n • x 0 ) , concluding the proof.

Let γ 1 , γ 2 be any two independent loxodromic isometries both lying in supp(µ * p ) for some p (we can arrange this since non-trivial powers of loxodromic isometries are loxodromic).

Moreover, since we assumed that µ has a finite exponential moment and that the increments are I.I.D, there exists λ 0 > 0 such that for all λ < λ 0 , one has E(e λdn+m ) ≤ E(e λdn ) • E(e λdm ) .

We conclude using the following purely analytical lemma.

Lemma B.1. Let (d n ) n∈N be a sequence of non negative real valued random variables such that

• d 1 has a finite exponential moment;

• there is λ 0 > 0 such that for any 0 ≤ λ < λ 0 and for for any m, n ∈ N one has The range of validity of the above proposition is much wider than for random walks. It could be used in the setting of a sub-additive defective adapted cocycle as defined in [START_REF] Mathieu | Deviation inequalities for random walks[END_REF] for example.

Proof. First observe that the condition E(e λdm+n ) ≤ E(e λdn ) • E(e λdm ) implies that E(d n+m ) ≤ E(d n ) + E(d m ) and therefore that the limit defining l does exist.

Let us introduce the notation Λ n (λ) := ln E(e λdn ) .

Our two assumptions imply that there is λ 0 > 0 such that for all n ∈ N and all λ < λ 0 we have E(e λdn ) < ∞ .

Since E(e λdm+n ) ≤ E(e λdn ) • E(e λdm ), we have Λ n+m (λ) ≤ Λ n (λ) + Λ m (λ), which is to say that the sequence (Λ n (λ)) n∈N is sub-additive. At the cost of slightly reducing the value of λ 0 , one can suppose that E(d n e λ0dn ) < ∞ for all n > 0. Because of the upper bound e x ≤ 1 + x + x 2 e x , we have for all λ < λ 0 .

E(e λdn ) ≤ 1 + λ E(d n ) + λ 2 E(d 2 n e λdn ) ≤ 1 + λ E(d n ) + λ 2 E(d 2 n e λ0dn ) ≤ 1 + λ E(d n ) + λ 2 C n , where C n := E(d 2 n e λ0dn ).

Applying the logarithm, dividing both sides by n gives and using the inequality ln(1+x) ≤ x, we get 1 n ln E(e λdn ) ≤ λ

E(d n ) n + C n λ 2 n .
Therefore, for all n > 0 and for all λ > 0

Λ n (λ) n ≤ λ E(d n ) n + C n λ 2 n .
In particular for all λ < λ 0 and all n ∈ N

Λ(λ) = inf k∈N Λ k (λ) k ≤ λ E(d n ) n + C n λ 2 n .
Letting λ → 0 we deduce that for all n ∈ N lim sup

λ→0 Λ(λ) λ ≤ E(d n ) n .
Finally taking n to ∞ gives lim sup λ→0 Λ(λ) λ ≤ l .

F q calculated by Kesten [?],

3) the drift q-1 q is the unique zero of I, 4) if Λ(λ) denotes the Legendre transform of I given by Λ(λ) = sup α∈R (λα -I(α)), then Λ (0) -( q-1 q ) 2 is the variance appearing in the central limit theorem for the standard random walk on the free group (this fact can be deduced either directly or as in [?, Lemma 5.2]).

Whereas finding an explicit expression for the rate function I in Theorem 1.2 does not seem to be feasible in general, pinning down some of its general properties, paralleling the above ones, is a more tractable challenge. As we showed, the property 3) holds under very general assumptions, and it is not hard to see that the same is true of 2). In turn, the properties 1) and 4) naturally suggest the corresponding open problems. We mention only a few of them:

Question: Is the rate function appearing in Theorem 1.2 strictly convex? Analytic? Do these properties depend on generating set or probability measure?

1. 1 .

 1 Properties of the rate function. A natural question motivated by the previous results concerns the understanding of the effective support D I = {α ∈ [0, ∞) | I(α) < ∞} of the rate function I. Note first that by convexity of the rate function I, the effective support D I is an interval in [0, ∞). We denote by l min := inf D I and by l max := sup D I .

  and hence we only need to show that there exists a constant L such that for any g ∈ Isom(X), there exists s ∈ S satisfying (sg • o, g -1 • o) o ≤ L . This follows directly by the defining property of a Schottky set (see Definition 2.5) applied to y = g • o and z = g -1 • o.

  1 2 log ||g|| = d(g • o, o) where g ∈ G, o denotes the origin in D and ||.|| is the operator norm induced by the Euclidean norm on R 2 , [?, Example 5.5] already provides an example of a rate function that explodes on (supp(µ)). Below, we shall give more examples where rate function explodes on any subset of { sub (supp(µ)), (supp(µ))}. Example 11.4. Consider G = SL 2 (R) acting isometrically on the Poincaré disc D endowed with the usual hyperbolic metric d. Let c a and c b be two geodesics in D that are of distance d = 1 to the origin and denoting their endpoints on ∂D, respectively, by {x + a , x - a } and {x + b , x - b }, suppose that these are ordered as (x - b , x + b , x + a , x - a ). For k ≥ 1, t ∈ {a, b}, t k be hyperbolic elements of G with translation axis c t , attracting/repelling fixed points x + t and x - t and translation distance 10 -1 k for t = b and 1 k for t = a. Let S = {a k , b k | k ≥ 1} and let Y i 's be the coordinate functions on S N . It is easy to see that the semigroup Γ generated by S consists of hyperbolic elements whose translation axes is contained in the connected region bounded by c a and c b . It follows, e.g. by [?, Lemma 6.3], that denoting by D > 0 twice the distance between c a and c b , for any g, h ∈ Γ, we have (11.5) τ (γ) + τ (h) ≤ τ (gh) ≤ τ (γ) + τ (h) + D.

(

  11.8) 0 ≤ d(g • o, o) -τ (γ) ≤ D + 4.

  For a subset B of Isom(X, d), we consider the following numerical conjugacy invariant ∞ (B) := lim sup k∈N * have ∞ (B) ≤ (B) (see also [?, Lemma 1.1]). Using a Schottky-like argument, one gets Proposition 11.9 (Geometric Berger-Wang equality, [?, ?]). For a countable bounded non-elementary subset B of Isom(X, d), we have ∞ (B) = (B). This result is a geometric analogue of a result due to Berger-Wang which tells that for a bounded set B of matrices in Mat(d, C), one has sup where ρ(.) denotes the spectral radius and ||.|| is any operator norm on the algebra Mat(

  Fix any K larger than L + δ, and consider any x ∈ O K (x m , x n )) c , where m ≤ n ≤ p. By definition, we have (x m , x) xn > K. Keeping (x m , x p ) xn ≤ L into account, hyperbolicity yields L ≥ (x m , x p ) xn ≥ min{(x m , x) xn , (x, x p ) xn } -δ. This forces (x, x p ) xn ≤ L + δ ≤ K, which gives x ∈ O K (x p , x n ), as required.

E

  (e λdm+n ) ≤ E(e λdn ) • E(e λdm ) . Then for any a > l := lim n→∞ E(d n ) n one has lim inf n→∞ -ln (P(d n ≥ an)) n > 0 .

Fekete

  Using Markov's inequality we get that, for all n and λ > 0, P(d n ≥ an) = P(e λdn ≥ e λan ) ≤ e -λan E(e λdn ) .Applying the logarithm and dividing by λn we get 1 λ ln P(d n ≥ an)

  which is a positive quantity if n is sufficiently large. Also, again by Lemma 10.14, there exists p ∈ υ so that d(p , π gn (x)) ≤ D 1 ; denote by υ the initial subgeodesic of υ with terminal point p . Notice that for n large enough we have d(x, p ) ≥ d(x, π gn

  It is readily seen by (11.5) that we have the following inclusion of events for every n ≥ 1 and 1 ≤ k ≤ n:

	(11.6)	1 n	τ (ω 1 . . . ω n ) > 10 -	1 2k	⊂ bn,k ≥	n 2
	and
	(11.7)		1 n	τ (ω 1 . . . ω n ) <	1 2k	⊂ ân,k ≥	n 2	.

Now for t ∈ {a, b}, n ≥ k ≥ 1 and (s 1 , . . . , s n ) ∈ S n , denote by tn,k the number of t i 's in (s 1 , . . . , s n ) with i ≥ k.

  A.6) O K (x n , x m ) ⊂ O K+δ (x p , x m ) .Proof. As in the proof of Lemma A.3, let L (depending on λ, C) be so that for all m ≤ n ≤ p we have (x m , x p ) xn ≤ L, so that we also have (x n , x p ) xm ≥ d(x m , x n ) -L. Fix any K ≥ L + δ. By definition, if x ∈ O K (x n , x m ), then (x n , x) xm ≤ K. If m -n is sufficiently large (depending on K), then we have (x n , x p ) xm > K + δ. Using hyperbolicity, we get min{(x p , x) xm , (x n , x p ) xm } ≤ (x, x n ) xm + δ ≤ K + δ.

Appendix C. Properness and identification of the rate function References

Introduction

Let Γ be an infinite, countable group acting by isometries on a metric space (X, d), µ a probability measure on Γ and z 0 ∈ X a base point. A (µ, z 0 )-random walk on X, or random walk on X for short, is the image under the orbital map γ → γ • z 0 of the random walk on Γ driven by the measure µ. We denote with (γ n ) n∈N ∈ Γ N (resp. (z n ) n∈N ∈ X N ) the sequence of the successive positions of the walk on Γ (resp. the sequence of the successive positions of the image random walk on X). We refer to Section 3.1 for basics on random walks.

We assume that the random variable d(z 0 , z 1 ) has a finite exponential moment. We refer to that property saying that 'µ has a finite exponential moment'. In the sequel P denotes the law of the random walk and E the corresponding expectation.

2010 Mathematics Subject Classification. 60F10,60B15,20P05,37D99. The first author was partially founded by the ERC n • 647133 'IChaos'. The third author is supported by SNF grant 182089.

Proof. Given a geodesic υ, we denote by π υ a choice of nearest point projection from X to υ. Given two points x, y ∈ X we denote by [x, y] the choice of any geodesic path joining x to y. Given any y ∈ X we define N υ (y) := {x ∈ X , d(π υ (y), π υ (x)) ≥ d(x, π υ (x))} . Note that the above set actually depends on π υ (y) only and, in particular, not on d(y, υ). We refer to [MT18a, Section 2] and [Mah10, Section 3] for more details about the nearest point retraction.

Let I be an interval of Z and (x i ) i∈I be a discrete path whose endpoints lie on the geodesic υ. Given k ∈ I \ ∂I we define [START_REF] Mathieu | Deviation inequalities for random walks[END_REF]Lemma 11.4, Claim 1] and Figure 2). The following lemma is the geometric key of the proof.

Lemma 8.4. [MS20, Lemma 11.4] For any > 0 there are constants c 1 , c 2 > 0 such that if

The statement above is a simplified version of [START_REF] Mathieu | Deviation inequalities for random walks[END_REF]Lemma 11.4]. The proof follows the same line and is illustrated in Figure 2.

We now use Lemma 8.4 with the successive positions of the random walk (x i = z i ). Recall that we want to show that there are constants C 1 , C 2 such that for any n > k > 0 and any R > 0, we have

We fix k, n and R > 0. For a path (z j ) satisfying (z n , z 0 ) z k > R, we define the times k 1 , k 2 as in Lemma 8.4.

We distinguish two cases, depending on whether or not k 2 -k 1 is large with respect to R.

The next lemma addresses the case of paths with a small value for k 2 -k 1 .

Lemma 8.5. There are constants c 3 , c 4 , C > 0 such that

Proof. We will look at all the possible values of k 1 , k 2 and conclude using the union bound.

Since we assumed that (z n , z 0 ) z k > R and by construction of N υ (z k ), we have that d(z k1 , z k ) ≥ R -100δ [MS20, Lemma 11.4, Claim 1]. Let 0 ≤ m < c 3 R for some c 3 that we will fix later on. Choose α < k and β > k such that β -α = m. We have

This clearly yields a contradiction in view of the definition of ∞ (B) using the fact that (g n ) = n (g) for every n ∈ N and g ∈ Isom(X). 11.3.1. Hausdorff convergence. One can use Lemma 10.6 and Proposition 10.8 to give a direct proof of Proposition 2.18. Here, we give a short proof based on our large deviations results.

Proof of Proposition 2.18. It follows from the definitions that for every ε > 0, there exists N ∈ N such that for every n ≥ N and g ∈ B n , sub (B) ≤ 1 n d(z 0 , g • z 0 ) ≤ (B) + ε. This already implies the statement if sub (B) = (B), so let sub (B) < (B). Then, for every ε ∈ (0, ( (B)sub (B))/2), the set B contains a finite subset B such that (B ) ≥ (B) -ε and sub (B ) ≤ sub (B) -ε. This follows from the definitions of (B) and sub (B). We can therefore suppose that B is finite. Now endow B with the uniform probability measure and consider the corresponding random walk on Isom(X). Given an interval J of non-empty interior in [ sub (B), (B)], by Theorem 1.2 and 3. of Theorem 1.5, we have -lim inf n→∞

This says, in particular, that for every n ∈ N large enough, we have

Together with the first paragraph above, this shows the Hausdorff convergence of 1 n d(B n •z 0 , z 0 ). The convergence of the sets 1 n τ (B n ) is deduced similarly using Theorem 1.4.

Appendix A. Existence of Schottky sets

We prove Proposition 3.14 that we recall here for the reader's convenience.

Proposition A.1 (Existence of Schottky sets). Let Γ be a countable group acting by isometries on a geodesic hyperbolic space X, z 0 ∈ X and µ a non-elementary probability measure on Γ. Then there is p ∈ N such that supp(µ * p ) contains a Schottky set.

Proof. We first reduce the proof to a purely geometric statement. Since we assumed that supp(µ) generates a non-elementary discrete semigroup there are two independent loxodromic elements γ 1 , γ 2 ∈ Γ and p 1 , p 2 ∈ N such that µ * pi (γ i ) > 0 for i ∈ {1, 2}. In particular we have

2 ) has the same fixed points as γ 1 (resp. γ 2 ), the pair (γ p2 1 , γ p1 2 ) is still a pair of two independent loxodromic isometries. Therefore, up to taking some powers of µ one can suppose that supp(µ) contains two independent loxodromic elements.

For any pair γ 1 , γ 2 ∈ Γ, let S k (γ 1 , γ 2 ) ⊂ Γ be the set of all elements of Γ which can be written as a product of exactly k elements in {γ 1 , γ 2 }. Note that S k (γ 1 , γ 2 ) is contained in the support of µ * k . Proposition A.1 is an immediate consequence of the following Proposition A.2. Let γ 1 , γ 2 two independent loxodromic isometries. Then there is k ∈ N such that S k (γ 1 , γ 2 ) contains a Schottky set as in Definition 2.5.

Proof. For any points x, y ∈ X and any C > 0, we define

which we call the C-shadow of y seen from x. Note that one can define it equivalently as

which is to say, when X is geodesic and up to a constant depending on δ, the set of all points z such that any geodesic from z to x passes through the ball B(y, C).

An easy consequence of the Morse lemma is the following.

Fix K 2 satisfying Lemma A.7 for both γ 1 and γ 2 (notice that increasing K 2 does not affect the conclusion of the lemma).

Lemma A.8. There exists n > 0 so that the following hold.

) both items above also hold replacing "n" with "-n", (4) the conclusion of Lemma A.7 holds for both γ 1 and γ 2 , for the given n, (5)

have distinct endpoints at infinity, there exists D so that for all n, m ≥ 0 we have (γ

For all sufficiently large n, we have

Indeed, by definition of shadow we have

, and by hyperbolicity we have

, so that, in fact, we have (x, y) x0 ≤ D + 2δ. This shows item 2. Item 3 follows using the same arguments, again for any sufficiently large n. Up to increasing n, Lemma A.7 applies. For the last item, notice that we have (x 0 , x 0 ) γ -n i •x0 = d(x 0 , γ -n i • x 0 ), which is larger than K 2 for n sufficiently large as above.

Fix n as in the previous lemma and denote

. We call a word in the alphabet {γ 2n 1 , γ 2n 2 } a positive word, while a negative word is a word in {γ -2n

In what follows we will conflate positive words and the corresponding group element. (A priori, different positive words might correspond to the same group element; we will deal with this later.) For w a positive word, denote O(w)

) . Lemma A.9. For any integer k there exists D so that the following holds. If w, w are distinct positive words of the same length k then O(w)∩O(w ) = ∅ and whenever x ∈ O(w) and y ∈ O(w ), we have (x, y) x0 ≤ D.

Proof. Consider distinct positive words w, w of length k. Up to swapping them, we can write them as w = uv, w = uv , where v starts with γ 2n 1 and v starts with γ 2n 2 (and we allow u to be empty). By lemma A. Notice that the lemma implies that distinct words of the same length correspond to distinct group elements (since the O(w) are non-empty by Lemma A.8-( 5)).

Similar arguments as in the previous lemma also give

Lemma A.10. If w, w are distinct negative words of the same length then, for i = 1, 2, we have w

We claim that the set S of all (group elements corresponding to) positive words of length 7 is a Schottky set, where the constant C is any constant larger than D + δ for D as in Lemma A.9 with k = 4. Let y, z ∈ X. For i = 1, 2, let v i be the positive word constructed as follows. If there is a positive word v of length 3 so that z ∈ v -1 • O - i , then set v = v i ; note that there is at most one such word by Lemma A.10. If there is no such v, choose any positive word of length 3 as v i . We might have

Suppose by contradiction that at least one third of all s ∈ S are so that (y, s • z) x0 > C. Then we have a subset S of S with #S ≥ #S/3, that is, #S ≥ 43, so that for any s 1 , s 2 ∈ S we have

by hyperbolicity.

From now and until the end of the proof, we refer to positive words of length 7 simply as words. Since there are at most 32 = 2 × 2 4 words ending with either v 1 or v 2 , there must be at least 11 words which belong to S and not ending with v 1 or v 2 .

We are then left with a set of 11 words which do not end with v 1 or v 2 and such that Inequality (A.11) holds for any pair of such words.

Moreover, since there are at most 8 words that start with 4 given letters, out of these 11 words there must be 2 which have different initial subword of length 4. To sum up, we have shown so far that there are 2 words ω = uv and ω = u v with u = u and v, v / ∈ {v 1 , v 2 }. Let us come to the desired contradiction by showing that

Appendix B. Hamana's argument

We mainly repeat arguments from [START_REF] Hamana | Asymptotics of the moment generating function for the range of random walks[END_REF] requiring only sub-additivity. Let X be metric space, µ a probability measure on Isom(X) with a finite exponential moment and z 0 ∈ X. Recall that we denoted by z n the position in X at time n of the random walk driven by µ. By the triangle inequality we have for every n, m ∈ N.

Recall that by sub-additivity and because d(z 0 , z m ) follows the same law as d(z n , z n+m ) the following limit is well defined

where we denoted d n := d(z 0 , z n ).

Appendix C. Properness and identification of the rate function

Here, we show that the rate function appearing in Theorem 1.2 is proper and indicate a way of identifying the rate function as a Legendre transform of a generating function, under a stronger moment condition. These admit simple proofs and should be well-known to experts; however, we did not find an explicit reference and hence we indicate the argument for the convenience of the reader who may not be well-versed in large deviation theory. Finally, we give an explicit example of a rate function and suggest some open questions.

C.0.1. Exponential tightness. We show that the finite exponential moment assumption implies exponential tightness of the sequence 1 n d n of random variables where, as before, we denote d n = d(z n , z 0 ). We provide the proof for reader's convenience. To see this, note that by Chebyshev inequality, for every λ ≥ 0, we have (C.2) P(d n ≥ tn) ≤ E[e λdn ]e -λtn . Using finite exponential moment assumption, let λ 0 > 0 be such that E[e λ0d1 ] < ∞. In (C.2), taking logarithm, dividing by n and specializing to some λ 1 > 0 such that λ 0 ≥ λ 1 , we get 1

On the other hand, it follows by the independence of random walk increments and the subadditivity that for all n ≥ 1, we have 1 n log E[e λ1dn ] ≤ log E[e λ1d1 ]. Therefore, we obtain lim sup

Since E[e λ1d1 ] < ∞ and λ 1 > 0, the result follows by taking the limit as t → ∞.

C.0.2. Identification of the rate function. In this part, let µ be a non-elementary probability measure on Isom(X) which has strong exponential moment in the sense that E[exp(αd n )] < ∞ for every α ≥ 0. Note that clearly, a probability measure µ of bounded support has strong exponential moment. The limit Laplace transform of the sequence

This function already appeared in the proof of Lemma B.1. As mentioned there, for the random variables (d n ), this limit exists by subadditivity arguments without appeal to LDP. More generally, provided that the sequence 1 n d n satisfies a LDP with convex rate function, this convergence is also a consequence of Varadhan's integral lemma (see [?] section 4.3), which, moreover, identifies the limit. In the other direction, we note that nice analytic properties (e.g. differentiability, steepness) of this function have direct implications for the LDP (see e.g. Gärtner-Ellis theorem [?, §4]).

The following lemma gives an expression of the rate function appearing in Theorem 1.2 under strong exponential moment assumption. Let us finish with an example of a rate function that one can obtain using the previous lemma, and some questions.

It is not difficult to pinpoint the explicit expression of the rate function for the standard random walk on the free group F q of rank q ≥ 1. It is given by the following

We remark that, among others, this function satisfies the following properties: 1) it is analytic and strictly convex on its effective support, 2) I(0) = -log √ 2q-1 q where √ 2q-1 q is the spectral radius of the standard random walk on