Random Walks On Reductive Groups Y. Benoist & J.-F. Quint

10CONTENTSset A is {0, 1}, and we are choosing the tk to be either 0 or 1 with equalprobability and independently of the previous choices of tj for j k.We want to study the sequence of partial sums sn : t1 · · · tn . Inparticular, we want to know :(0.6)What is the asymptotic behavior of sn ?We will explain in Section 0.4 various classical answers to this question.On the one hand, some of these classical answers describe the behavior in law of this sequence. They tell us what we can expect at timen when n is large. These statements only involve the law of the randomvariable sn which is nothing else than the nth -convolution power µ n ofµ i.e.µ n µ · · · µ.For instance, the Central Limit Theorem (CLT), the Large DeviationsPrinciple (LDP) and the Local Limit Theorem (LLT) are statementsin law. An important tool in this point of view is Fourier analysis.On the other hand, some classical answers describe the behavior ofthe individual trajectories s1 , s2 , . . . , sn , . . . These statements are truefor almost every trajectory. The trajectories are determined by elements of the Bernoulli space B : AN : {b (t1 , . . . , tn , . . .) tn A}of all possible sequences of random choices. Here “almost every” referto the Bernoulli probability measure β : µ Non this space B. This space B is also called the space of forwardtrajectories. For instance, the Law of Large Numbers (LLN) and theLaw of the Iterated Logarithm (LIL) are statements about almost everytrajectory. An important tool in this point of view is the conditionalexpectation.The interplay between these two aspects is an important feature ofProbability Theory. The Borel-Cantelli lemma sometimes allows oneto transfer results in law into almost-sure results. Conversely, the pointof view of trajectories gives us a much deeper level of analysis on theprobabilistic phenomena that cannot be reached by the sole study ofthe laws µ n .0.4. What classical results should I know? This short bookis as self-contained as possible. We will reprove many classical factsfrom Probability Theory. However we will take for granted basic factsfrom Linear Agebra, Integration Theory and Functional Analysis. A

INTRODUCTION11few results on real reductive algebraic groups, their representations andtheir discrete subgroups will be quoted without proof.The reader will more easily appreciate the streamlining of this bookif he or she knows classical Probability Theory. Indeed the main objective of this book is to present for “products of iid random matrices” theanalogs of the following five classical theorems for ”sums of iid randomnumbers”.In these five classical theorems, we fix a probability measure µ onR and set b (t1 , . . . , tn , . . .) B and sn t1 · · · tn for the partialsums. The sequence b is chosen according to the law β, which meansthat the coordinates tk are iid random real numbers of law µ.The first theorem is the Law of Large Numbers due to many authorsfrom Bernoulli up to Kolmogorov.It tells us that, when µ has a finiteRfirst moment i.e. when R t dµ(t) , almost every trajectory has adrift which is equal to the average of the law :Zt dµ(t).(0.7)λ : RTheorem 0.1. (LLN) Let µ be a Borel probability measure on Rwith a finite first moment. Then, for β-almost all b in B, one has(0.8)lim 1n nsn λ.The second theorem is the Central Limit Theorem which is also dueto many authors from Laplace up to Lindeberg and Lévy. It tells usthat, when µ is non-degenerate i.e. is Rnot a Dirac mass, and when µhas a finite second moment i.e. when R t2 dµ(t) , the recentered law of µ n spreads at speed n, more precisely, it tells us that therenormalized variables sn nλconverge in law to a Gaussian variablenwhich has the same variance Φ as µ :ZΦ : (t λ)2 dµ(t).RTheorem 0.2. (CLT) Let µ be a non-degenerate Borel probabilitymeasure on R with a finite second moment. Then, for any boundedcontinuous function ψ on R, one hasZZs2 2Φe (0.9)limψ s nλdµ n (s) ψ(s) ds.nn 2πΦRRThe third theorem is the Law of the Iterated Logarithm discoveredby Khinchin. It tells us that almostall recentered trajectories spread at a slightly higher speed than n. More precisely it tells us that the

12CONTENTSprecise scale at which almost all recentered trajectories fill a boundedinterval is n log log n.Theorem 0.3. (LIL) Let µ be a non-degenerate Borel probabilitymeasure on R with a finite second moment. Then, for β-almost all bin B, the set of cluster points of the sequence sn nλ2Φ n log log nis equal to the interval [ 1, 1].The fourth theorem is the Large Deviations Principle due to Cramér.IttellsR α t us that when µ has a finite exponential moment i.e. whene dµ(t) , for some α 0, the probability of an excursionRaway from the average decays exponentially. We will just state belowthe upper bound in the large deviations principle.Theorem 0.4. (LDP) Let µ be a Borel probability measure on Rwith a finite exponential moment. Then, for any t0 0, one has(0.10)1lim sup µ n ({t R t nλ nt0 }) n 1.n The fifth theorem is the Local Limit Theorem due to many authorsfrom de Moivre up to Stone. It tells us that the rate of decay forthe probability that the recentered sum sn nλ belongs to a fixedinterval is 1/ n. For sake of simplicity, we will assume below that µ isaperiodic i.e. µ is not supported by an arithmetic progression m0 tZwith m0 R and t 0. Indeed the statement is just slightly differentwhen µ is supported by an arithmetic progression.Theorem 0.5. (LLT) Let µ be an aperiodic Borel probability measure on R with a finite second moment. Then, for all a1 a2 , onehas a2 a1lim n µ n (nλ [a1 , a2 ]) .n 2πΦ0.5. Can you show me nice sample results from this topic?The five main results that we will explain in this book are the analogs ofthe five classical theorems that we just quoted in the previous section.We will state below special cases of these five results. We will explain inSection 0.8 what kind of generalizations of these special cases is neededfor a better answer to Question 0.1.In these five results, we fix a Borel probability measure µ on thespecial linear group G : SL(d, R), we set V Rd , and we fix aEuclidean norm k.k on V . We denote by A the support of µ, and by

INTRODUCTION13Γµ the closed subsemigroup of G spanned by A. For n 1, we denoteby µ n the nth -convolution powerµ n : µ · · · µ.The forward trajectories are determined by elements of the Bernoullispace B : AN : {b (g1 , . . . , gn , . . .) gn A}(0.11)endowed with the Bernoulli probability measure β : µ N .As in Section 0.4, the sequence b is chosen according to the law β whichmeans that b is a sequence of iid random matrices gk chosen with lawµ, and we want to understand the asymptotic behavior of the productspn : gn · · · g1 . We assume, to simplify this introduction, that(0.12)- µ has a finite exponential moment,- Γµ is unbounded and acts strongly irreducibly on V .Inassumptions, finite exponential moment means that one hasR theseαkgkdµ(g) for some α 0. Notice that the word exponential isGnatural in this context if one keeps in mind the equality kgkα eα log kgk .In these assumptions, strongly irreducible means that no proper finiteunion of vector subspaces of V is Γµ -invariant.These conditions are satisfied for instance whenµ 21 (δa0 δa1 ) where a0 2111 and a1 01 10 ,or, more generally, where a0 2 1 0 . 1 1 0 . 0 0 1 . . . . .0 0 0 . 00 0 . 1and a1 0 0 0 .1 100.00 10.0 . 0. 0 . 0 . 1 . 0.In this example, one has A {a0 , a1 } and we are choosing the gkto be either a0 or a1 with equal probability and independently of theprevious choices of gj for j k. The partial products pn : gn · · · g1can take 2n values with equal probability. This concrete example isvery interesting to keep in mind. Indeed, the whole machinery we aregoing to explain in this book is necessary to understand the asymptoticbehavior of pn in this case.

14CONTENTSWe denote by λ1 λ1,µ the first Lyapunov exponent of µ, i.e.Z1(0.13)λ1 : limlog kgk dµ n (g).n n GThe first result tells us that the variables log kpn vk satisfy the Lawof Large Numbers. It is due to Furstenberg.Theorem 0.6. (LLN) For all v in V r {0}, for β-almost all b inB, one has(0.14)lim 1n nlog kgn · · · g1 vk λ1 , and one has λ1 0.The second result tells us that the variables log kpn vk satisfy the1Central Limit Theorem i.e. that the renormalized variables log kpn vk nλnconverge in law to a nondegenerate Gaussian variable.Theorem 0.7. (CLT) The limitZ1Φ : lim(log kgk n λ1 )2 dµ n (g)n n Gexists and is positive Φ 0. For all v in V r {0}, for any boundedcontinuous function ψ on R, one hasZZs2 2Φe1 (0.15)limψ log kgvk nλψ(s) dµ n (g) ds.nn 2πΦGRThe third result tells us that the variables log kpn vk satisfy a lawof the iterated logarithm.Theorem 0.8. (LIL) For all v in V r {0}, for β-almost all b inB, the set of cluster points of the sequencelog kgn · · · g1 vk nλ1 2Φ n log log nis equal to the interval [ 1, 1].The fourth result tells us that the variables log kpn vk satisfy a LargeDeviations Principle.Theorem 0.9. (LDP) For all v in V r {0}, for any t0 0, onehas(0.16)1lim sup µ n ({g G log kgvk nλ1 nt0 }) n 1.n The fifth result tells us that the variables log kpn vk satisfy a LocalLimit Theorem.

INTRODUCTION15Theorem 0.10. (LLT) For all a1 a2 , for all v in V r {0}, onehas na2 a1n µ ({g G log kgvk nλ1 [a1 , a2 ] }) .n 2πΦlimTheorems 0.7 up to 0.10 are in Le Page’s thesis under technicalassumptions. Since then, the statements have been extended and simplified by Guivarc’h, Raugi, Goldsheid, Margulis, and the authors.0.6. How does one prove these nice results? Thanks for yourenthusiasm. As for sums of random numbers, we will use tools comingfrom Probability Theory like the Doob Martingale Theorem, tools coming from Ergodic Theory like the Birkhoff Ergodic Theorem and toolscoming from Harmonic Analysis like the Fourier Inversion Theorem.New tools will be needed. We will be able to understand the asymptotic behavior of the product pn of iid random matrices, only byfirst studying the associated Markov chain on the projective space P(V )whose trajectories, starting from x Rv, are n 7 xn : pn x. We willalso study the ergodic properties along these trajectories of the cocycleσ1 on P(V ) given by.σ1 (g, x) kgvkkvkIndeed, for a vector v of norm kvk 1, the quantity sn : log kpn vkthat we want to study is nothing else than the sumnXlog kpn vk σ1 (gk , xk 1 ).k 1These random real variables tk : σ1 (gk , xk 1 ) whose sum is sn are notalways independent because the point xk 1 depends on what happenedbefore. This is why we will need tools from Markov chains.First we have to understand the statistics of the trajectories xk i.e.we have to answer to Question (0.4). That is why we will study theinvariant probability measures ν of this Markov chain, i.e. the probability measures ν on P(V ) which satisfy µ ν ν. Those probabilitymeasures ν are also called µ-stationary. This will allow us to prove theLLN and to give a formula for the drift analog to (0.7) :Z(0.17)λ1 σ1 (g, x) dµ(g) dν(x).G P(V )This formula is due to Furstenberg.We will see that, when the action of Γµ on V is proximal the invariant probability measure ν on P(V ) is unique. The assumption proximalmeans that there exists a rank-one matrix which is a limit of matrices

16CONTENTSλn γn with λn 0 and γn in Γµ . In this case Furstenberg’s formula(0.17) reflects the fact that, for all starting point x in P(V ), the sequence (xn )n 1 becomes equidistributed according to the law ν, forβ-almost all b. When Γµ is not proximal, the asymptotic behavior ofthe sequence (xn )n 1 is described in [13].Second we have to understand the transfer operator P and its generalisation the complex transfer operator Piθ with θ R. This operator Piθ is the bounded operator on C 0 (P(V )), given by, for any ϕ inC 0 (P(V )) and any x in P(V ),Z(0.18)Piθ ϕ(x) eiθ σ1 (g,x) ϕ(gx) dµ(g).GThe CLT 0.7 describes the asymptotic behavior of the probability measures on Rµn,x : image of µ n by the map g 7 log kgvk.kvkThe Fourier transform of these measures is given by the classical andelegant formula with θ in R,(0.19)nµdn,x (θ) Piθ 1(x),where 1 is the constant function on P(V ) equal to 1. The behavior ofthe righthand side of this formula will be controlled by the “largest”eigenvalue of Piθ . This formula (0.19) explains how spectral data fromthe complex transfer operator Piθ can be used in combination with theFourier Inversion Theorem to prove not only the CLT but also the LIL,the LDP and the LLT. We will be able to reduce our analysis to thecase where the action of Γµ on V is proximal. We will see then thatthis operator Piθ has a unique “largest” eigenvalue λiθ when θ is small,and that this eigenvalue λiθ varies analytically with θ.0.7. Can you answer your own questions now? You are right,what took us so long to explain are nothing but answers to Questions(0.4) and (0.5). We will deduce answers to Questions (0.2) and (0.3)from these.Indeed, we will first check that, under assumption (0.12), the random variables log kpn k satisfy the same LLN, CLT, LIL and LDP aslog kpn vk. Technically, this will not be too difficult since these four limitlaws involve a renormalization which will erase the difference betweenlog kpn k and log kpn vkWe will also check that, when moreover Γµ is proximal, the randomvariables log f (pn v) satisfy the same LLN, CLT, LIL and LDP aslog kpn vk. This will be more delicate since we will have to control theexcursions of the sequence pn x near the kernel of f . The key point

INTRODUCTION17will be to prove a Hölder regularity result for the stationary measureν which is due to Guivarc’h.0.8. Why is this book less simple than these samples? Thequantityκ1 (g) : log kgkgives us information on the size of a matrix g only “in one direction”. Itis much more useful in the applications to deal with all the logarithms ofjsingular values κj (g) : log k k j 1(g)kand to introduce the “multinorm”(g)k(0.20)κV (g) : (κ1 (g), . . . , κd (g)).A less naive way to ask our question (0.1) is :(0.21)Can one describe the asymptotic behavior of κV (pn )?The answer to this question is Yes! These random variables κV (pn )satisfy a LLN with average λ. However they do not exactly satisfy aCLT: the renormalized variable κV (p nn) nλ converges in law but the limitlaw is only a “folded Gaussian law” i.e. the “image of a Gaussian lawby a homogeneous continuous locally linear map”!The support of this limit law depends only on λ and the “Zariskiclosure” Gµ of the semigroup Γµ . This Zariski closure Gµ is alwaysa reductive algebraic group with compact center. The “folding” phenomenon occurs already when d 4 and Gµ SO(2, 2)!The whole picture becomes much clearer when one adopts the following more intrinsic point of view.We start with a connected real semisimple algebraic group, call itagain G, and a Borel probability measure µ on G. We consider iidrandom variables gn G of law µ and want, again, to describe the asymptotic behavior of the products pn : gn · · · g1 . In this point of view,we forget about the embedding ρ of G in GL(V ) which was responsiblefor the folding of the Gaussian law. We replace the conditions (0.12)by- µ has a finite exponential moment,(0.22)- the semigroup Γµ spanned by A is Zariski dense in G,where A is the support of µ.The projective space P(V ) is replaced by the flag variety P of G,and the norm is replaced by the Cartan projection κ of G. Exactlyas in Section 0.6, we will use a cocycle σ(g, η) on the flag variety P,called the Iwasawa or Busemann cocycle. The Iwasawa cocycle σ takesits values in a real vector space a called the Cartan subspace whosedimension is the real rank r of G. The Cartan projection κ and takes

18CONTENTSits values in a simplicial cone a of a called the Weyl chamber. Theprecise definitions will be given later. For every η in P, the asymptoticbehavior of κ(pn ) will be related to the asymptotic behavior of σ(pn , η).Our questions now become(0.23)What is the asymptotic behavior of κ(pn ) and σ(pn , η)?We will see that the random variables σ(pn , η) and κ(pn ) satisfy aLLN, CLT, LIL and LDP. We will also check the LLT for the randomvariables σ(pn , η).0.9. Can you state these more general limit theorems?Here are the statements for the Iwasawa cocycle σ. The assumptionson µ are given in (0.22).Theorem 0.11. (LLN) There exists a unique µ-stationary probability measure ν on P. The averageZσ(g, η) dµ(g) dν(η)σµ : G Pbelongs to the interior of the Weyl chamber a .For η in P, for β-almost all b in B, one haslim 1 σ(gnn n· · · g1 , η) σµThis multidimensional version of Theorem 0.6 is due to Guivarc’hRaugi and Goldsheid-Margulis. An important new output there is thefact that the Lyapunov vector σµ belongs to the interior of the Weylchamber a .Theorem 0.12. (CLT) There exists a Euclidean norm k.kµ on asuch that, for all η in P, for any bounded continuous function ψ on a,ZZ kvk2σ(g,η) nσµ n r/2 2µ ψlimdµ (g) (2π)ψ(v)edπµ (v),nn Gawhere dπµ (v) dv1 · · · dvr in an orthonormal basis for k.kµ .This multidimensional version of Theorem 0.7 is due to Guivarc’hand Goldsheid. An important new output there is the fact that thesupport of the limit Gaussian law is the whole Cartan subspace a.Here are the multidimensional versions of Theorems 0.8, 0.9 and0.10.Theorem 0.13. (LIL) For all η in P, for β-almost all b in B, theset of cluster points of the sequenceσ(gn · · · g1 , η) nσµ 2n log log n

INTRODUCTION19is equal to the unit ball Kµ of k.kµ .Theorem 0.14. (LDP) For any t0 0, one has1lim sup sup µ n ({g G kσ(g, η) nσµ k nt0 }) n 1.n η PTheorem 0.15. (LLT) For all bounded open convex set C of a

random matrices" or more precisely \products of iid random matrices" is sometimes also called \random walks on linear groups". It began in the middle of the 20th century. It nds its roots in the speculative work of Bellman in [8] who guessed that an analog of classical Probability Theory for \sums of random numbers" might be true for the coe cients