Gerold Alsmeyer Random Recursive Equations and Their Distributional Fixed Points January23,2012 Springer Preface Use the template preface.tex together with the Springer document class SVMono (monograph-type books) or SVMult (edited books) to style your preface in the Springerlayout. Aprefaceisabook’spreliminarystatement,usuallywrittenbytheauthorored- itorofawork,whichstatesitsorigin,scope,purpose,plan,andintendedaudience, andwhichsometimesincludesafterthoughtsandacknowledgmentsofassistance. When written by a person other than the author, it is called a foreword. The preface or foreword is distinct from the introduction, which deals with the subject ofthework. Customarilyacknowledgmentsareincludedaslastpartofthepreface. Place(s), FirstnameSurname monthyear FirstnameSurname v Acknowledgements Use the template acknow.tex together with the Springer document class SVMono (monograph-type books) or SVMult (edited books) if you prefer to set your ac- knowledgement section as a separate chapter instead of including it as last part of yourpreface. vii Contents 1 Introduction................................................... 1 1.1 Atrueclassic:thecentrallimitproblem........................ 1 1.2 Aprominentqueuingexample:theLindleyequation ............. 4 1.3 Arichpoolofexamples:branchingprocesses................... 7 1.4 ThesortingalgorithmQuicksort ........................... 10 1.5 Randomdifferenceequationsandperpetuities................... 16 1.6 Anonlineartimeseriesmodel ................................ 20 1.7 Anoisyvotermodelonadirectedtree ......................... 22 1.8 Anexcursiontohydrology:theHorton-Strahlernumber .......... 24 2 Renewaltheory ................................................ 29 2.1 Anintroductionandfirstresults............................... 29 2.2 Animportantspecialcase:exponentiallifetimes................. 33 2.3 Lattice-type ............................................... 35 2.4 Uniformlocalboundednessandstationarydelaydistribution ...... 37 2.4.1 Uniformlocalboundedness............................ 37 2.4.2 Finitemeancase:thestationarydelaydistribution......... 38 2.4.3 Infinitemeancase:restrictingtofinitehorizons ........... 40 2.5 Blackwell’srenewaltheorem................................. 42 2.5.1 Firststepoftheproof:shakingofftechnicalities.......... 42 2.5.2 Settingupthestage:thecouplingmodel ................. 44 2.5.3 Gettingtothepoint:thecouplingprocess ................ 45 2.5.4 Thefinaltouch ...................................... 46 2.6 Thekeyrenewaltheorem .................................... 47 2.6.1 DirectRiemannintegrability........................... 48 2.6.2 Thekeyrenewaltheorem:statementandproof............ 52 2.7 Therenewalequation ....................................... 55 2.7.1 Gettingstarted....................................... 56 2.7.2 Existenceanduniquenessofalocallyboundedsolution .... 57 2.7.3 Asymptotics ........................................ 58 2.8 Renewalfunctionandfirstpassagetimes ....................... 63 ix x Contents 2.9 Anintermezzo:randomwalks,stoppingtimesandladdervariables . 65 2.10 Two-sidedrenewaltheory:ashortpathtoextensions ............. 72 2.10.1 Thekeytool:cyclicdecomposition ..................... 72 2.10.2 Uniformlocalboundednessandstationarydelaydistribution 74 2.10.3 ExtensionsofBlackwell’sandthekeyrenewaltheorem .... 75 2.10.4 Anapplication:Tailbehaviorofsup S inthenegative n 0 n driftcase .......................≥.................... 77 3 Iteratedrandomfunctions ...................................... 81 3.1 Themodel,definitions,somebasicobservationsandexamples..... 81 3.1.1 Definitionofaniteratedfunctionsystemanditscanonical model.............................................. 82 3.1.2 Lipschitzconstants,contractionpropertiesandthetop Liapunovexponent................................... 85 3.1.3 Forwardversusbackwarditerations..................... 86 3.1.4 Examples........................................... 87 3.2 GeometricergodicityofstronglycontractiveIFS ................ 90 3.3 ErgodictheoremformeancontractiveIFS...................... 96 3.4 AcentrallimittheoremforstronglymeancontractiveIFS.........102 4 Powerlawbehaviorofstochasticfixedpointsandimplicitrenewal theory ........................................................107 4.1 Goldie’simplicitrenewaltheorem.............................107 4.2 Makingexplicittheimplicit..................................111 4.3 Proofoftheimplicitrenewaltheorem..........................113 4.3.1 ThecasewhenM 0a.s. .............................116 ≥ 4.3.2 ThecasewhenP(M>0) P(M<0)>0 ...............116 ∧ 4.3.3 ThecasewhenM 0a.s. .............................120 ≤ 4.4 Applications...............................................122 4.4.1 Randomdifferenceequationsandperpetuities ............122 4.4.2 Lindley’sequationandarelatedmax-typeequation........129 d 4.4.3 Letac’smax-typeequationX =M(N X)+Q............131 ∨ 4.4.4 TheAR(1)-modelwithARCH(1)errors .................135 5 The smoothing transform: a stochastic linear recursion with branching PartI:Contractionproperties ...................................143 5.1 Settingupthestage:theweightedbranchingmodel ..............145 5.2 Adigression:weightedbranchingandrandomfractals............151 5.3 TheminimalLp-metric......................................155 5.4 ConditionsforS tobeaself-mapofPp(R) ...................163 5.5 ContractionconditionsforS ................................168 5.5.1 Convergenceofiteratedmeanvalues....................168 5.5.2 Contractionconditionsif0<p 1.....................170 ≤ 5.5.3 Contractionconditionsif p>1 ........................171 Contents xi 5.5.4 Contractionconditionsif p>2and∑i 1 Ti Lp.........179 5.5.5 Aglobalcontractionconditionif p 1≥..|..|.∈.............183 ≥ 5.5.6 Existenceofexponentialmoments......................184 5.6 Anapplication:Quicksortasymptotics......................188 5.7 TheHausdorffdimensionofrandomCantorsets:completingthe proofofTheorem5.12 ......................................194 6 Thecontractionmethodforaclassofdistributionalrecursions ......205 6.1 Thesetup:adistributionalrecursionofgeneraladditivetype ......206 6.2 TheZolotarevmetric........................................207 6.3 Asymptoticnormality:ZolotarevversusminimalLp-metrics ......215 6.4 Backtorecurrenceequation(6.2):ageneralconvergencetheorem..217 6.5 Thedegeneratecase:recursion(6.2)withtautologicallimitequation223 6.6 Applications...............................................233 6.6.1 Thetotalpathlengthinarandomrecursivetree...........233 6.6.2 Thenumberofleavesofarandomrecursivetree ..........240 6.6.3 Sizeandtotalpathlengthofarandomm-arysearchtree....243 7 The smoothing transform: a stochastic linear recursion with branching PartII:Fixedpoints............................................251 7.1 Thesmoothingtransformwithdeterministicweights .............251 References.....................................................251 A Aquicklookatsomeergodictheoryandtheorems .................257 A.1 Measure-preservingtransformationsandergodicity ..............257 A.2 Birkhoff’sergodictheorem ..................................259 A.3 Kingman’ssubadditiveergodictheorem........................260 B Convexfunctioninequalitiesformartingalesandtheirmaxima......263 C Banach’sfixedpointtheorem....................................267 D Hausdorffmeasuresanddimension ..............................271 Index .............................................................281