{'fraction_non_alphanumeric': 0.05649310062983797, 'fraction_numerical': 0.01204384826193567, 'mean_word_length': 3.8024705610713463, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 26, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Subadditive and Multiplicative Ergodic Theorems

A result for subadditive ergodic cocycles is proved that provides more delicate information than Kingman's subadditive ergodic theorem. As an application we deduce a multiplicative ergodic theorem generalizing an earlier result of Karlsson-Ledrappier, showing that the growth of a random product of semi-contractions is always directed by some horofunction. We discuss applications of this result to ergodic cocycles of bounded linear operators, holomorphic maps and topical operators, as well as a random mean ergodic theorem.


Introduction
Products of random operations arise naturally in a variety of contexts from pure mathematics to more applied sciences. Typically the operations, or the maps, do not commute, but one would nevertheless hope to have asymptotic regularity of various associated quantities. In the commutative case one has the standard ergodic theorem or what in probability is called the law of large numbers. A very important and genuinely non-commutative case is that of products of random matrices. These are governed by the multiplicative ergodic theorem of Oseledets which in particular is a fundamental theorem in differentiable dynamics. Another area which belongs to this study is the subject of random walks on groups.
It is a remarkable fact that, in many such situations, one can introduce a metric which is invariant or non-expanded by the transformations under consideration. This gives a way to quantify the behaviour of random products of maps, such as linear operators, holomorphic maps, symplectomorphisms, or homogeneous-monotone maps. Due to the non-expansion of the metric and the triangle inequality, numerical quantities associated to the random products then satisfy a form of subadditivity.
Kingman proved in [Ki68] the subadditive ergodic theorem, which is a generalization of the usual ergodic theorem to subadditive cocycles. This extension is very useful, with many applications. In the particular case of random products, Kingman's theorem asserts that there is a well-defined growth rate, or in a different terminology, a certain speed with which these products tend to infinity.
Our goal is to understand to what extent random products tend to infinity following a specific direction, using the notion of horofunction. Horofunctions made one of their first explicit appearances in the 1926 Wolff-Denjoy theorem which describes the dynamics of holomorphic self-maps of the unit disk. As was noted by those authors, and extended and commented on by several people since then, the mechanism behind this result is the Schwartz lemma which implies that the holomorphic maps do not increase the Poincaré distance between points, and the fact that the unit disk with this metric is the hyperbolic plane, see e.g. [K01,KeL07,AR14].
Our strategy is to show first a substantial refinement of Kingman's theorem. Then, we apply it to prove a very general multiplicative ergodic theorem, extending one aspect of the Wolff-Denjoy theorem to a vastly more general setting: the asymptotic behaviour of random products of 1-Lipschitz maps of any metric space in terms of horofunctions. This generalizes and reproves the main theorem in [KL06], which in turn extends several known results, such as the one of Oseledets mentioned above, and which has delivered unexpected applications. Our theorem has a weak-type formulation involving linear or metric functionals (a generalization of horofunctions to a non-proper setting). Hence, it can hold in a very general setting, contrary to results yielding a stronger convergence, that are known to fail if the geometric properties of the space are not good enough. Moreover, under suitable assumptions on the space, our a priori weaker statement can automatically be promoted to the stronger one.
As for further new applications, our theory leads to an ergodic theorem for cocycles of bounded linear operators. Ruelle proved the first such theorem in infinite dimension assuming compactness of the operators [R82]. It was generalized by Mañé, Thieullen and others, see the recent monograph [LL10] for more details. The interest for such statements about semi-flows on Hilbert spaces comes from Ruelle to the more recent work of Lian and Young in the study of certain stochastic differential equations, partial differential equations of evolution with application to hydrodynamic turbulence, such as the Navier-Stokes equation [R82,R84,ER85,LY12]. There are also other potential contexts of application, see for example the remark in [F02, p. 10].
Our subadditive theorem is stated in Paragraph 1.1 and proved in Section 2. The ergodic theorem for random products is then stated in Paragraph 1.2 and proved in Section 3. Finally, Paragraph 1.3 and the remaining sections of this article are devoted to a brief discussion of some applications.
1.1. Existence of good times for subadditive cocycles. Let (Ω, µ) be a measure space with µ(Ω) = 1 and let T : Ω → Ω be an ergodic measure preserving map. A measurable function a : N × Ω → R which satisfies a(n + m, ω) ≤ a(n, ω) + a(m, T n ω) for all integers n, m > 0 and a.e. ω ∈ Ω is called a subadditive cocycle. For convenience we also set a(0, ω) ≡ 0. One says that a is integrable if a(1, ω) is integrable and one defines the asymptotic average Kingman's theorem asserts that, almost surely, a(n, ω)/n tends to A. Moreover, if A > −∞, the convergence also holds in L 1 (µ).
We prove in Section 2 the following subadditive ergodic statement (cf. Problem 3.3 in [K02]): Theorem 1.1. Let a(n, ω) be an integrable and subadditive cocycle relative to the ergodic system (Ω, µ, T ) as above, with finite asymptotic average A. Then for almost every ω there are integers n i := n i (ω) → ∞ and positive real numbers δ ℓ := δ ℓ (ω) → 0 such that for every i and every ℓ ≤ n i , This statement significantly refines Proposition 4.2 in [KM99]. It is not a consequence of Kingman's theorem: by subadditivity, we have by Kingman's theorem, so the upper bound in (1.1) readily follows from Kingman's theorem. On the other hand, the lower bound, which asserts that the cocycle is close to being additive at all times ℓ between 0 and n i , is much more delicate.
This lower bound is reminiscent of Pliss' lemma, a combinatorial lemma which proved very useful in hyperbolic dynamics, see for instance [ABV00]. For any additive sequence tending linearly to infinity, this lemma entails the existence of good times n i for which the behavior of the sequence between n i − ℓ and n i is well controlled for all ℓ ≤ n i . Our statement is both weaker (since there is an additional error ℓδ ℓ ) and stronger since it applies in random subadditive situations and makes it possible to approach the true asymptotics Aℓ.
We will apply Theorem 1.1 to the context of multiplicative ergodic theorems below, but it could also be of interest for different questions, for example [GG14] used [KM99,Prop. 4.2] to re-prove and extend Livsic's theorem of [Ka11].
Remark 1.2. Define the upper asymptotic density of a subset U of the natural numbers as The proof of Theorem 1.1 gives in fact more information, namely that on a set of large measure one can take δ ℓ independent of ω, and one can have many good times n i . More precisely, fix ρ > 0, then there exist a sequence δ ℓ → 0 and a subset O ⊂ Ω of measure at least 1 − ρ such that, for every ω ∈ O, the subset of good times A(ω) ⊂ N (made of those n for which (1.1) holds for all ℓ ≤ n) has upper asymptotic density at least 1 − ρ.
1.2. Random products and metric functionals. Horocycles, horodisks etc are concepts originally coming from two-dimensional hyperbolic geometry and complex analysis. A general definition of the corresponding horofunctions (now also called Busemann functions) in terms of geodesic rays γ(t) was noted by Busemann: As emphasized by Gromov, this definition leads to a natural bordification of metric spaces, by mapping the space into its set of continuous functions equipped with the topology of uniform convergence on bounded sets. We consider instead pointwise convergence, following for example [GV12]. Let (X, d) be a metric space, fix x 0 ∈ X, and define the continuous injection The functions h x are all 1-Lipschitz maps. As indicated, we endow the space R X of real valued functions on X with the product topology, i.e., the topology of pointwise convergence. The closure of the image Φ(X) will therefore be compact. By definition we call the elements in this compact set for metric functionals. Thus, to every point x there is a unique associated metric functional h x , and then there may be further functionals obtained as limit points: To relate to the standard notion, we call limits, as x → ∞, of h x in the uniform convergence on bounded sets for horofunctions. If X is proper and geodesic, then X is precisely the set of horofunctions. If the metric space is particularly nice, for instance CAT(0), then horofunctions and Busemann functions coincide. For non-proper metric spaces a Busemann function might not be a horofunction since the convergence might not be uniform on bounded sets, and conversely a horofunction might not be a Busemann function since it might be obtained as a limit which does not correspond to any geodesic ray. Our terminology is in part inspired by the simple fact that for infinite dimensional Hilbert space H, the set H contains the closed unit ball of continuous linear functionals. The definition of metric functionals is also somewhat parallel to the one of linear functionals: metric functionals are maps X → R that vanish at the origin x 0 and respect the metric structure of the spaces.
Note the order in which the maps are composed. We require a weak measurability property: for all x ∈ X and all n ∈ N, the map ω → u(n, ω)x from Ω to X should be measurable. For instance, this is the case if ϕ : Ω → SC(X) is measurable where SC(X) is endowed with the compact-open topology (i.e., the topology of uniform convergence on compact subsets of X) and X is locally compact (this last assumption ensures that the composition map SC(X) × SC(X) → SC(X) is continuous, so that u(n, ·) : Ω → SC(X) is also measurable). This is also the case when X is a Banach space and ϕ is measurable from Ω to the space of bounded linear operators on X with the topology of norm convergence. We say that the above cocycle u(n, ω) is integrable if a condition which is independent of x ∈ X. In this case, the subadditive cocycle a(n, ω) = d(x, u(n, ω)x) is also integrable. Hence, by Kingman's theorem, d(x, u(n, ω)x)/n converges almost surely to a limit A ≥ 0 (which does not depend on the choice of the basepoint x). In Section 3, the above subadditive ergodic statement is used to establish the following multiplicative ergodic theorem: Theorem 1.3. Let u(n, ω) be an integrable ergodic cocycle of semi-contractions of a metric space (X, d). Then for a.e. ω there exists a metric functional h ω of X such that for all x Moreover, if X is separable and Ω is a standard probability space, one can choose the map ω → h ω to be Borel measurable.
The main theorem of [KL06] is the same statement, but with the additional assumption that the cocycle u takes it values in isometries of X, instead of semi-contractions (moreover it was formulated only for proper spaces). This additional assumption makes it possible to use the action of the cocycle on the space of metric functionals, and use an additive cocycle there. This proof cannot work for semi-contractions. The present proof will instead use Theorem 1.1 and is thus quite different. Theorem 1.3 was conjectured in [K04] for proper metric spaces. With a use of the Hahn-Banach theorem, see Section 3, this specializes to the following statement in the case of Banach spaces.
Corollary 1.4. Let u(n, ω) be an integrable ergodic cocycle of semi-contractions of a subset D of a Banach space X. Then for a.e. ω there is a linear functional f ω of norm 1 such that for any x ∈ D, This generalizes the main theorem in Kohlberg-Neyman [KN81], dealing with u(n, ω) = A n and D convex (the latter condition was removed in [PR83]). For the random setting previous results can be found in [K04]. When X is strictly convex and reflexive, the conclusion implies weak convergence of u(n, ω)x/n. When the norm of the dual of X is Fréchet differentiable, the conclusion implies norm convergence of u(n, ω)x/n. In general however the above statement is best possible in view of a counterexample in [KN81].
1.3. Applications. In this paragraph, we describe briefly different settings where our results apply. More involved applications are described in Sections 4, 5 and 6.
Applied mathematics provides a wealth of examples of non-expansive mappings of Banach spaces, especially ℓ ∞ , for example in dynamical programming and topical matrix multiplication (homogeneous-order-preserving), generalizing matrices in the max-plus or min-plus (tropical) semi-ring. In finite dimensions the existence of Lyapunov exponents has been studied, in particular what could then be called a tropical Oseledets multiplicative ergodic theorem. We refer to [CT80,Co88,Ma97,Gu03]. Our Corollary 1.4 implies some known and some not previously known statements in this setting.
More precisely, let S be a set and consider the Banach space B(S) of bounded real-valued functions f : S → R with the sup-norm. Consider a map A : B(S) → B(S) (not necessarily linear) with the properties: for all x • (semi-homogeneity) for any positive constant a, it holds that Blackwell observed in 1965 that such maps A are semi-contractive. He had a constant 0 < β < 1 in the second condition which corresponds to discounting in financial settings. When S = {1, 2, . . . , d} these operators, which now can be viewed as functions A : R d → R d , and with equality in the second condition, are sometimes called topical functions (see [Gu03]). A multiplicative variant of this type of maps are self-mappings of cones A : C → C with A(ax) = aA(x) and x ≤ y implies Ax ≤ Ay with respect to the cone partial order. Such maps are semi-contractive in Hilbert's metric and its variants.
Our theorems apply to random products of such mappings, and information about metric functionals can be found in [Wa08].
Consider now the random ergodic set-up, first considered in particular by von Neumann-Ulam, see [Ka52]. Let L ω be a collection of measure-preserving transformations of a probability space (Y, ν), indexed by ω ∈ Ω. Let T : Ω → Ω be an ergodic measure-preserving map. Given v : Y → R and y ∈ Y , ω ∈ Ω, we consider the average Let u(n, ω) denote the corresponding multiplicative cocycle. Then the above average equals (u(n, ω)0)(y)/n. Hence, the following corollary (which follows readily from Corollary 1.4) is a generalization of the (random) mean ergodic theorem: Corollary 1.5. Let X be a Banach space and let U be a strongly measurable map from Ω to linear operators on X. Suppose that U ω ≤ 1 for every ω ∈ Ω. Then for every v ∈ X and a.e. ω there is a linear functional F ω of X with F ω = 1 such that Again we remark that when X is strictly convex and reflexive, the conclusion implies weak convergence of the ergodic average in question and when the norm of the dual of X is Fréchet differentiable, the conclusion implies norm convergence. It is however known, due to Yosida [Ka52], that in this situation if there is a weakly convergent subsequence then strong convergence of the whole sequence follows. So X being strictly convex and reflexive would suffice. One of the most general results of this type, with norm convergence, was obtained by Beck-Schwartz for reflexive spaces in 1957. (There are many papers considering norm convergence of similar or more general averages.) Note here that it is well-known that the Carleman-von Neumann mean ergodic theorem (i.e. with the norm convergence) does not hold in general for Banach spaces. Our statement does hold, and implies as said norm convergence under the conditions mentioned.
As another application we show in Section 4: Theorem 1.6. Let v(n, ω) = A(T n−1 ω)A(T n−2 ω) · · · A(ω) be an integrable ergodic cocycle of bounded invertible linear operators of a Hilbert space. Denote the positive part [v(n, ω)] := (v(n, ω) * v(n, ω)) 1/2 . Then for a.e. ω there is a norm 1 linear functional F ω on the space of bounded linear operators such that This general statement can under further assumptions be promoted to yield some known theorems. The same remarks as after Corollary 1.4 apply. For example if the Hilbert space has finite dimension, then Sym can be given a Hilbert space structure and it follows that converges. This is known to be equivalent to Oseledets' multiplicative ergodic theorem, as for example explained in [R82]. In the infinite dimensional case and restricting to identity plus Hilbert-Schmidt operators, one gets a uniform convergence, as observed in [KM99], stronger than that in [R82] for compact operators. Note that in general the conclusion of the standard multiplicative ergodic theorem is too strong: if A is a bounded linear operator on a Hilbert space and v is a nonzero vector, it is not true in general that converges as n → ∞. See [LL10,Sc06] for comparison. In Section 5 we exemplify a consequence of Theorem 1.3 in the complex analytic setting, and yet another application in Section 6. A further possibility would be to consider random products of diffeomorphisms of a compact manifold, and exploit the induced isometric action on the space of Riemannian metrics. This space has been studied somewhat, it is known to be CAT(0) but not complete. For two or more generic diffeomorphisms there is no joint invariant measure on the manifold, so Oseledets' theorem does not apply, but our Theorem 1.3 applies.

Subadditive ergodic cocycles
In this section, we prove Theorem 1.1. By passing to the natural extension if necessary, one can assume without loss of generality that T is invertible.
One of the inequalities in (1.1) is known. Indeed, by definition a(n, ω) ≤ a(n − ℓ, T ℓ ω) + a(ℓ, ω) and by Kingman's theorem a(ℓ, ω) = Aℓ + o(1). This means that The other inequality is much more subtle. It says intuitively that at certain times the cocycle is nearly additive. Note that Theorem 1.1 for additive cocycles is equivalent to Birkhoff's ergodic theorem.
We begin by defining b(n, ω) = a(n, T −n ω). This is again a subadditive cocycle but for the transformation τ := T −1 and with the same asymptotic average as a. The interest in b comes from the fact that where ω ′ = T n ω. Note that, on the right-hand side, the point ω ′ is the same in both terms. We start by showing that b(n, ω) − b(n − ℓ, ω) behaves well for the majority of times n and for ℓ ≤ n large enough, by a combinatorial argument related to several proofs of Kingman's theorem (for example as in Steele [S89]). This is the key point of the proof, given in Lemma 2.2. In contrast to [KM99], we will control the majority of times and not just a small set of times. This is central to keep a good control once one changes variables back from b to a.
We begin by proving the following lemma as a warm-up. These arguments will be used again in a more elaborate form in the proof of Lemma 2.2.
Lemma 2.1. Let b be an integrable ergodic subadditive cocycle with finite asymptotic average A. Let δ > 0. Then there exists c > 0 such that for almost every ω Proof. By replacing if necessary b(n, ω) by b(n, ω) − An, one may without loss of generality assume that A = 0. We denote by τ the underlying ergodic transformation. Let V = {n ∈ N : ∃ℓ ∈ [1, n], b(n, ω) − b(n − ℓ, ω) ≤ −cℓ}. When c is large enough we would like to conclude that the density of V is small.
Fix N > 0. We will partition [0, N ] using the following algorithm. First let n 0 = N . Assuming n i is defined, we proceed as follows. If n i / ∈ V , then take n i+1 = n i − 1. If n i ∈ V , then let ℓ i ∈ [1, n i ] be as in the definition of V , and let n i+1 = n i − ℓ i . We stop when n i = 0.
We have thus decomposed the interval [0, N ) in a union of intervals . Using the subadditivity along the intervals of the first type one gets: Since V ∩ [0, N − 1] is included in the union of the intervals (n i+1 , n i ] for n i ∈ V , its cardinality |V ∩ [0, N − 1]| is bounded by (n i − n i+1 ). Therefore, the previous inequality gives |V ∩ [0, N − 1]| ≤ (M + 1)N/c. This finishes the proof, taking c sufficiently large so that (M + 1)/c ≤ δ.
In the following lemma, we replace c (large) of Lemma 2.1 by a parameter ǫ which is arbitrarily small. The price to pay in order to preserve a valid statement is to restrict it to sufficiently large ℓ. This lemma plays a crucial role in the proof of Theorem 1.1.
Lemma 2.2. Let b be an integrable ergodic subadditive cocycle with finite asymptotic average A. Let ǫ > 0 and δ > 0. There exists k ≥ 1 such that for almost every ω Proof. Without loss of generality we may assume that A = 0. We denote by τ the underlying ergodic transformation. Going to the natural extension if necessary, we can assume that τ is invertible.
The idea of the proof is that the argument we used to prove Lemma 2.1 would work in our situation if b + (1, ω) were small enough. This is not the case in general, but this is asymptotically true for the iterates of the cocycle, by Kingman's theorem: if s is large enough, then b + (s, ω)/s is very small. We will fix such an s, discretize time to work in sN, and follow the proof of Lemma 2.1 in this set. Additional errors show up in the approximation process, but they are negligible if k in the statement of the lemma is large enough. If one is to do this precisely, there is a problem that τ s is in general not necessarily ergodic. This issue is resolved by working with times in the set sN + t for fixed t ∈ [0, s − 1].
Let us start the rigorous argument. Fix ρ > 0, which corresponds to the precision we want to achieve (this value will be chosen at the end of the proof). Since b(s, ω)/s tends to 0 almost everywhere and in L 1 when s tends to infinity by Kingman's theorem, the same holds for b + . One can thus take s ∈ N such that b + (s, ω) < ρs. We also fix t ∈ [0, s − 1]. Let K = sN + t be the set of reference times we will use in the following. Once all these data are fixed, we take a large enough k.
The set of bad times, whose density we want to majorize, can be decomposed as U ∪ V , where If n ∈ U , then there exists i ∈ [0, s) such that b(n, ω) ≤ b(i, ω)−ǫ(n−i). Since b(n, ω)/n → 0 almost everywhere, we deduce that U is almost surely finite. It suffices therefore to estimate the density of V .
Consider n ∈ V and ℓ ∈ [k, n−s] such that b(n, ω)−b(n−ℓ, ω) ≤ −ǫℓ. We will approximate such an n by a time in K. Letñ be the successor of n in K, that is the smallest time in K withñ ≥ n. We writeñ = n + i with i < s. Thus, where we set F (η) = s j=−s b + (1, τ j η), which is integrable and positive. Similarly, as n − ℓ ≥ s by assumption, n − ℓ admits a predecessorñ −l in K. One has n − ℓ =ñ −l + j for some j < s, and We obtain finally that where the last inequality comes from the fact thatl ≤ ℓ + 2s is bounded by 2ℓ whenever k is sufficiently large.

Denote by
We have shown that To estimate the density of V , it suffices hence to estimate the density of W . Let N be an integer, letÑ = ps + t be its successor in K (it satisfiesÑ ≤ 2N if N is sufficiently large). We decompose K ∩ [0,Ñ ] as in Lemma 2.1. We start withñ 0 =Ñ . If we have definedñ i , we define its predecessor as follows. Ifñ i / ∈ W , we takeñ i+1 =ñ i − s. Ifñ i ∈ W , then let ℓ i ∈ sN ∩ [k,ñ i ] as in the definition of W , and setñ i+1 =ñ i −l i . We stop whenñ i = t.
We have thus decomposed [0,Ñ ) as a union of intervals of the form Using the subadditivity along the intervals of the first and the third types, one gets: Almost surely, b(Ñ , ω) = o(Ñ ) whenÑ tends to infinity. Hence, after a certain stage, we have b(Ñ , ω) ≥ −ρÑ . In the terms on the right above, we majorize the sum overñ i / ∈ W by p−1 j=0 b + (s, τ js+t ω). The trivial term b(t, ω) is estimated by F (ω). Using the definition of W , we obtain: The set W is included in the union of the intervals (ñ i+1 ,ñ i ] withñ i ∈ W , by construction. The same holds for V in view of (2.1). Therefore, |V ∩ [0, N − 1]| ≤ (ñ i −ñ i+1 ). The previous equation gives hence that: The function F is integrable, so there exists M ∈ R such that the function G = F · 1 F ≥M satisfies G < sρ. We majorize F by M + G. In the preceding equation, theñ i s in W are separated by at least k becausel i ≥ k by definition. Therefore, the number of suchñ i is at mostÑ /k. We get whenever k is sufficiently big.
Finally, if k is sufficiently large, one has (using thatÑ ≤ 2N ) where H(η) = b + (s, η) + 2G(η) has integral < 3sρ. Summing after that over t ∈ [0, s − 1], we obtain: For almost every ω, Birkhoff's theorem applied to the function H gives N +s−1 i=0 H(τ i ω) ≤ 3sρN for N sufficiently large. Thus This shows that the density of V is bounded by 14ρ/ǫ. This concludes the proof if we choose ρ = ǫδ/14 at the beginning of the argument.
We combine the two preceding lemmas in order to gain improving control over time, as follows.
Lemma 2.3. Let b be an integrable ergodic subadditive cocycle with finite asymptotic average A. Let ǫ > 0. There exist a sequence δ ℓ → 0, a subset O of measure at least 1 − ǫ and for ω ∈ O, there is a sequence of bad times U (ω) with |U (ω) ∩ [0, n − 1]| ≤ ǫn for every n, with the following property. For every ω ∈ O, for all n not in U (ω), and for every ℓ ∈ [1, n], it holds that Proof. For every i > 1, set c i = 2 −i . In view of Lemma 2.2, there exists k i such that, for almost every ω, the set Since the function n i (ω) is almost everywhere finite, we may find a subset O i of measure close to 1, say µ(O i ) > 1 − ǫ2 −i , on which n i (ω) ≤ n i , for some integer n i (which one may choose to be > n i−1 and ≥ k i ). We treat the case i = 1 separately and in a more crude manner, applying Lemma 2.1: there is a constant c 1 such that, for almost every ω, We set k 1 = 1. As above, we define hence U 1 (ω), n 1 (ω), and O 1 .
We setŌ = i≥1 O i , the good set on which things are well controlled. It satisfies µ(Ō) > 1 − ǫ. For ω ∈Ō we define a set of bad times U (ω) by We begin by showing that the bad set U (ω) satisfies |U (ω) ∩ [0, n − 1]| ≤ ǫn for every n. Let n ∈ N. Let i be such that n i ≤ n < n i+1 (there is nothing to do if n < n 1 since U (ω) ⊂ [n 1 , +∞)). Hence Since n ≥ n j for every j ≤ i, the cardinality of U j (ω) ∩ [0, n − 1] is bounded by ǫ2 −j n. Therefore the sum is not greater than ǫn, as desired.
Set I i = [n i , n i+1 ) for i > 1, and I 1 = [1, n 2 ). We define a sequenceδ ℓ = c i for ℓ ∈ I i . This sequence tends to 0. We claim that it satisfies (2.2) for every n ≥ n 1 which is not in U (ω). Indeed, fix ℓ ∈ [1, n], it belongs to an interval I i . We claim that n ≥ n i : This holds by assumption if i = 1, and if i > 1 we have n i = inf I i ≤ ℓ ≤ n. As n ≥ n i and n / ∈ U (ω), we have n / ∈ U i (ω). Moreover, ℓ ≥ k i : Indeed, if i > 1, this follows from the inequalities ℓ ≥ n i and n i ≥ k i , while if i = 1 this comes simply from the fact that k 1 = 1. Thus, the This almost finishes the proof, it just remains to treat the case n < n 1 and ℓ ∈ [1, n]. This is only a finite number of conditions. All the functions we have considered are measurable, so they are almost everywhere finite. There is therefore a subset O ofŌ, again with µ(O) > 1−ǫ, and a constant d such that for every ω ∈ O, and every n < n 1 and ℓ ∈ [1, n], we have b(n, ω) − b(n − ℓ, ω) ≥ (A − d)ℓ. Set finally δ ℓ =δ ℓ for ℓ ≥ n 1 and δ ℓ = max(d,δ ℓ ) for ℓ < n 1 . This function works.
We now deduce the theorem from these lemmas.
Proof of Theorem 1.1. We may assume that the asymptotic average A vanishes. First, we prove the easy upper bound. By subadditivity, a(n, ω) − a(n − ℓ, T ℓ ω) ≤ a(ℓ, ω), which is almost surely o(ℓ) by Kingman's theorem. This proves the upper bound in Theorem 1.1. The stronger statement in Remark 1.2 follows from the fact that the almost sure convergence a(ℓ, ω)/ℓ → 0 is uniform on sets of arbitrarily large measure.
We turn to the harder lower bound. Let b(n, ω) = a(n, T −n ω). This is a subadditive cocycle for the ergodic transformation T −1 . We may therefore apply Lemma 2.3 to it. Let ǫ > 0. The lemma gives us a set of good points O with measure at least 1 − ǫ, a sequence δ ℓ → 0 and, for ω ∈ O, a set U (ω) of bad times with |U (ω) ∩ [0, n − 1]| ≤ ǫn for every n.
Let O n = {y ∈ O : n / ∈ U (ω)} and P n = T −n O n . For ω ∈ P n and ℓ ∈ [1, n], one has Hence, if a point is contained in an infinite number of the sets P n , it satisfies the conclusion of the theorem. If the times where it belongs to P n have an asymptotic density at least 1 − ρ, it satisfies even the stronger conclusion in Remark 1.2. We have to show that this condition has large measure.
For ω ∈ Ω, we define A(ω) = {n : ω ∈ P n }, its set of good times. We would like to see that A(ω) has an upper asymptotic density larger than 1 − ρ, for ω in a subset of large measure. Let f N (ω) = |A(ω) ∩ [0, N − 1]|. The bad points are those for which f N (ω) ≤ (1 − ρ)N for all N sufficiently large. Denote by V i = {ω : ∀N ≥ i, f N (ω) ≤ (1 − ρ)N }, and V = V i the set of bad points.
We have If we have chosen ǫ sufficiently small with respect to ρ, this quantity is bounded by ρ. This proves that the lower bound of Theorem 1.1 (and even the stronger conclusion in Remark 1.2) is satisfied on a set of measure greater than 1 − ρ. Since ρ is arbitrary the proof is complete.
Here is a small example showing that, even in deterministic situations, one can not improve the lower bound in Theorem 1.1 to a bound of the form a n − a n−ℓ ≥ Aℓ − δ ℓ (where δ ℓ is any sequence tending to 0) while keeping a lot of good times. Indeed, consider a sequence a n which is either 1 or 2 for every n. This is always a subadditive sequence. Assume also that the value 2 is taken infinitely many times. Then the times for which a n − a n−ℓ ≥ −δ ℓ for all ℓ ≤ n are, up to finitely many exceptions, only the times when a n = 2. Hence, they can be arbitrarily sparse.
Since the maps are semi-contractive and thanks to the triangle inequality one verifies easily that this is a subadditive ergodic cocycle with asymptotic average A ≥ 0. In view of Theorem 1.1 we have therefore for almost every ω a sequence n i → ∞ and a sequence δ ℓ → 0 such that for every i and every ℓ ≤ n i , If we write x n = u(n, ω)x 0 and h n the horofunction associated to x n , this means that This inequality passes to limits as n i → ∞.
If X is separable, one may extract a subsequence of h n i such that h n ′ i (y) converges for all y belonging to a countable dense set of X. Since all these functions are 1-Lipschitz, convergence on every point of X follows. The limit h of h n ′ i satisfies for all ℓ the inequality In the general case, Φ(X) is still compact, but it does not have to be sequentially compact, so we should argue differently. The sets are non-empty (they contain h n i ) and form a decreasing sequence. By compactness, i Y i is also non-empty. Any element h of this intersection satisfies (3.1).
The bound |h(x ℓ )| ≤ d(x ℓ , x 0 ) ≤ Aℓ + o(ℓ) follows from the 1-Lipschitz property of h and Kingman's theorem. Therefore Finally, let us show that ω → h ω can be chosen to be Borel measurable if Ω is standard and X is separable. In this case, the topology on Φ(X) is generated by simple convergence along a dense sequence in X. Hence, Φ(X) is metrizable, and it becomes a compact metric space. Since Ω is standard, we may identify it with [0, 1].
By Remark 1.2, there exists a decomposition of Ω as the union of a set Ω ∞ of measure 0, and an increasing sequence of sets Ω i on which one can use the same sequence δ i,ℓ . By Lusin's theorem, we may also ensure that all the maps ω → u(n, ω)x 0 are continuous on Ω i .
This is a nonempty compact subset of Φ(X), depending upper semi-continuously on ω ∈ Λ i . We are looking for a measurable map ω ∈ Λ i → h ω ∈ A(ω), the only difficulty being measurability. Its existence follows for instance from [W77, Theorem 4.1].
One can deduce Corollary 1.4 as a consequence of Theorem 1.3 together with the following lemma.
Lemma 3.1. In a Banach space, for every metric functional h there is a linear functional f of norm at most 1 such that f ≤ h.
Proof. Let h be a metric functional on a Banach space X. We will show that, for any finite set F in X and any ǫ > 0, there is a linear form f on X with norm at most 1 such that f (x) ≤ h(x) + ǫ for all x ∈ F . By weak* compactness (the Banach-Alaoglu theorem), the existence of a linear form f with norm at most 1 such that The open set {h ∈ Φ(X) : ∀x ∈ F,h(x) < h(x) + ǫ} is nonempty (it contains h). Hence, as Φ(X) is the closure of X, this set contains a point y ∈ X. It satisfies for all By Hahn-Banach theorem, there exists a linear form f of norm 1 with f (y) = − y . Then, for all x ∈ F , as desired.
Alternatively, we give a direct proof of Corollary 1.4 within the vector space setting without referring to metric functionals: Proof of Corollary 1.4 directly from Theorem 1.1. Let a(n, ω) = u(n, ω)0 , which is a subadditive ergodic cocycle with asymptotic average A ≥ 0. If A = 0, then the conclusion is trivial so we assume that A > 0. In view of Theorem 1.1 we have therefore for almost every ω a sequence n i → ∞ and a sequence δ ℓ → 0 such that for every i and every We denote by x n = u(n, ω)0. By the Hahn-Banach theorem we can find a linear functional of norm 1 such that f n (x n ) = x n . Now, for any ℓ ≤ n i , By weak* compactness, there exists a linear functional f = f ω of norm at most 1 satisfying a.e. as required. In the case A > 0, the norm of f is clearly necessarily 1.
This has in turn another consequence, Corollary 1.5, as is explained in the introduction. In contrast to the finite dimensional case, the metric of Pos is less nice and the space is not locally compact. Therefore the metric functionals are less studied at present time. An alternative approach is provided thanks to Segal's inequality e u+v ≤ e u/2 e v e u/2 . This implies a weak notion of non-positive curvature: the differential isomorphism exp : Sym → Pos semi-expands distances. This means that the inverse, the logarithm, is semicontractive.

Cocycles of bounded linear operators
So let v(n, ω) = ϕ(T n−1 ω)ϕ(T n−2 ω) · · · ϕ(ω) be an integrable ergodic cocycle of bounded invertible linear operators of H. Note that we here take the opposite order compared to (1.2). Hence if we denote p n the positive part of v(n, ω), that is p n (ω) = (v(n, ω) * v(n, ω)) 1/2 , then a(n, ω) := log p n (ω) is a subadditive cocycle, where the norm is the operator norm. Indeed, notice that the p n is the orbit of the matrices v(n, ω) * acting by isometry on Pos, now in the right order for the metric statements. The distance from the identity to the nth point of the random orbit in Pos gives a subadditive cocycle. Thanks to that logarithm preserves distance from Id to p, and contracts distances between p and q not the identity, the inequalities between distances go in the right direction, so that the proof of Corollary 1.4 as given in Section 3 goes through. We conclude that for a.e. ω there is a linear functional F ω on Sym (or on the full space of bounded linear operators, by Hahn-Banach) of norm 1 such that which is Theorem 1.6. For comparison, the classical formulation of the multiplicative ergodic theorem is equivalent to the fact that p n (ω) 1/n , or 1 n log p n (ω), converges in norm as n → ∞. In general Sym is not uniformly convex, so our weaker convergence seems near best possible. Under stronger assumptions, one can probably promote it to a stronger statement. When Sym is a Hilbert space, for example in the setting of Hilbert-Schmidt operators, the linear functionals are given by M → Tr(AM ). This implies Oseledets theorem (it is actually stronger, a more uniform convergence) as Ruelle explains for compact operators, see [KM99].
As was remarked in the introduction, it is well-known that in general, even for products of just one operator, one cannot hope for a Oseledets-type Lyapunov regularity.

Cocycles of holomorphic maps
Pseudo-metrics are frequently employed in the theory of several complex variables, partly because of the Schwartz lemma but also thanks to their connection to diophantine problems (Lang's conjecture). Given a complex space Z, we denote the associated Kobayashi pseudodistance d Z . Every holomorphic map between complex spaces f : Z → W is 1-Lipschitz with respect to these pseudo-metrics: for all points z 1 , z 2 ∈ Z. Pseudo refers to that for these distances the axiom about d(x, y) = 0 may fail. On one extreme we have that the pseudo-metric on C is identically 0 for all pairs of points, while for hyperbolic Riemann surfaces it is always non-degenerate, and thus an honest metric. (These facts already explain the theorems of Liouville and Picard on entire functions.) Many papers have been devoted to the topic of extending the Wolff-Denjoy theorem, and there are also papers about composing random maps, in both orders, generalizing continued fraction expansion, see [KeL07] and references therein.
Even for a pseudo-metric one defines metric functionals and horofunctions as before. So our multiplicative ergodic theorem in principle applies, and gives an extension of the Wolff-Denjoy theorem to a vastly more general situation: Theorem 5.1. Let u(n, ω) be an integrable ergodic cocycle of holomorphic self-maps of a complex space Z. Then for a.e. x there is a metric functional h ω for the pseudo-metric space (Z, d Z ) such that It remains to understand horofunctions. Under certain convexity and smoothness assumptions, these metrics are Gromov hyperbolic or something slightly weaker, and our result then implies that the orbit converges to a boundary point, provided τ > 0. For the state-of-theart of the metric geometry of the Kobayashi metric, we refer to [K05, AR14, Z14] and references therein. Here is a corollary: Corollary 5.2. Let u(n, ω) be an integrable ergodic cocycle of holomorphic maps of D, where D is a bounded domain in C d which is either strictly convex, strictly pseudo-convex with C 2 -smooth boundary, or pseudo-convex with analytic boundary. Unless for a.e. ω 1 n d D (u(n, ω)z, z) → 0 as n → ∞, it holds that a.e. orbit u(n, ω)z converges to some boundary point ξ ω ∈ ∂D. The boundary point may depend on ω but is independent of z ∈ D.
Proof. It is known that under these assumptions on D the metric space (D, d) is a proper metric space, where d = d D the Kobayashi metric. Assuming τ > 0, the orbit accumulates on ∂D and our Theorem 1.3 provides for a.e. ω a horofunction h such that h(u(n, ω)z) → −∞ when n → ∞ and any z ∈ D. We may assume that a sequence x n defining h (say with base point x) converges to some point ξ in ∂D.
In the case D is strictly convex it is shown in [AR14] that Abate's big horospheres F x (ξ, R) = z ∈ D : lim inf w→ξ d(z, w) − d(x, w) < 1 2 log R can only meet the boundary in one point. It is clear that {z : h(z) < 0} is contained in F x (ξ, 0). Thus we must have that u(n, ω)z → ξ as n → ∞.
In the two remaining cases it is known from [K05] and references therein that for any sequence z n converging to a different boundary point, there is a constant R > 0 such that for all n, m R > (z m , x n ) := 1 2 (d(x, z m ) + d(x, x n ) − d(z m , x n )) .
Therefore it would be impossible that h(z m ) < 0 since d(x, z m ) → ∞. Hence again the conclusion that u(n, ω)z → ξ.

Behaviour of extremal length under holomorphic self-maps of Teichmüller space
Thurston announced in his celebrated preprint from 1976 [T88, Theorem 5] that isotopy classes of surface diffeomorphisms admit some kind of Lyapunov exponents. Let S be a closed surface of genus g ≥ 2. For any isotopy class α of simple closed curves on S, and ρ a Riemannian metric, the length L ρ (α) is the shortest length of a curve in the isotopy class α for the metric ρ. Given a diffeomorphism f of S, there are a finite number of exponents λ i such that L ρ (f n α) 1/n → λ i as n → ∞ for some i depending on α. In the generic case there is only one exponent. This is proved passing to the Teichmüller space T g and instead letting f act on the equivalence classes of metrics, which are points in T g . Indeed, one has L ρ (f n α) = L f −n ρ (α).
This was partly generalized to cocycles in [K14], see also [H14] for a refinement in the i.i.d. case. In several instances, again mainly due to Thurston, certain holomorphic selfmaps of the Teichmüller space arise. Unless they are biholomorphic they do not give rise to an isotopy class of diffeomorphisms of the underlying surface. It is therefore natural to consider how lengths behave under the metric u(n, ω) with this order of composition. In the case of holomorphic maps it is more natural to consider length from complex analysis, namely the extremal length of Beurling-Ahlfors: where the supremum is taken over all metrics in the conformal class of x. We get applying our main theorem to the Teichmüller distance, using the identification of horofunctions in this metric due to Liu and Su, and following the arguments in [K14]: Theorem 6.1. Let u(n, ω) be an integrable cocycle of holomorphic self-maps of the genus g Teichmüller space T g . Denote by d T the Teichmüller distance. Then for a.e. ω there is a simple closed curve α = α ω such that lim n→∞ 1 n log Ext u(n,ω)ρ (α) = 2 lim n→∞ 1 n d T (u(n, ω)ρ, ρ).
The link between the Teichmüller metric d T and extremal length comes via Kerckhoff's formula: log Ext x (α) Ext y (α) .