Preface If you place a large number of points randomly in the unit square, what is the distribution of the radius of the largest circle containing no points? Ofthesmallestcirclecontaining4points?WhydoBrowniansamplepaths havelocalmaximabutnotpointsofincrease,andhownearlydotheyhave points of increase? Given two long strings of letters drawn i.i.d. from a (cid:12)nitealphabet,howlong isthelongest consecutive(resp. non-consecutive) substring appearing in both strings? If an imaginary particle performs a simple random walk on the vertices of a high-dimensional cube, how long does it take to visit every vertex? If a particle moves under the in(cid:13)uence of a potential (cid:12)eld and random perturbations of velocity, how long does it take to escape from a deep potential well? If cars on a freeway move with constant speed (random from car to car), what is the longest stretch of empty road you will see during a long journey? If you take a large i.i.d. samplefroma2-dimensionalrotationally-invariantdistribution,whatisthe maximum over all half-spaces of the deviation between the empirical and true distributions? These questions cover a wide cross-section of theoretical and applied probability. The common theme is that they all deal with maxima or min- ima, in some sense. The purpose of this book is to explain a simple idea which enables one to write down, with little e(cid:11)ort, approximate solutions to such questions. Let us try to say this idea in one paragraph. (a) Problems about random extrema can often be translated into prob- lems about sparse random sets in d 1 dimensions. (cid:21) (b) Sparserandomsetsoftenresemblei.i.d.randomclumpsthrowndown randomly (i.e., centered at points of a Poisson process). (c) The problem of interest reduces to estimating mean clump size. (d) This mean clumpsize canbeestimated byapproximating theunder- lying random process locally by a simpler, known process for which explicit calculations are possible. (Part (b) explains the name Poisson clumping heuristic). ii This idea is known, though rarely explicitly stated, in several speci(cid:12)c settings,butitspowerandrangeseemsnottobeappreciated.Iassertthat this idea provides the correct way to look at extrema and rare events in a wide range of probabilistic settings: to demonstrate this assertion, this booktreatsover100examples.Ourargumentsareinformal,andwearenot goingtoproveanything.Thisisarathereccentricformatforamathematics book | some reasons for this format are indicated later. The opening list of problems was intended topersuade every probabilist to read the book! I hope it will appeal to graduate students as well as experts, to the applied workers as well as theoreticians. Much of it should becomprehensibletothereaderwithaknowledgeofstochasticprocessesat the non-measure-theoretic level (Markov chains, Poisson process, renewal theory, introduction to Brownian motion), as provided by the books of Karlin and Taylor (1975; 1982) and Ross (1983). Di(cid:11)erent chapters are somewhat independent, and the level of sophistication varies. Althoughthebookrangesovermany(cid:12)eldsofprobabilitytheory,ineach (cid:12)eld we focus narrowly on examples where the heuristic is applicable, so this work does not constitute a complete account of any (cid:12)eld. I have tried to maintain an honest \lecture notes" style through the main part of each chapter. At the end of each chapter is a \Commentary" giving references to background material and rigorous results. In giving references I try to give a book or survey article on the (cid:12)eld in question, supplemented by recent research papers where appropriate: I do not attempt to attribute results to their discoverers. Almost all the examples are natural (rather than invented to show o(cid:11) the technique), though I haven’t always given a thorough explanation of how they arise. The arguments in examples are sometimes deliberately concise. Most results depend on one key calculation, and it is easier to see this in a half-page argument than in a three-page argument. In rigorous treatments it is often necessary to spend much e(cid:11)ort in showing that certain e(cid:11)ects are ultimately negligible; we simply omit this e(cid:11)ort, relying on intuition to see what the dominant e(cid:11)ect is. No doubt one or two of our heuristic conclusionsarewrong:ifheuristicargumentsalwaysgavetherightanswer, then there wouldn’t be any point in ever doing rigorous arguments, would there? Various problems which seem interesting and unsolved are noted as \thesis projects", though actually some are too easy, and others too hard, for an average Ph.D. thesis. Themost-studied (cid:12)eldofapplication oftheheuristicis toextremesof1- parameter stationary processes. The standard reference work on this (cid:12)eld, Leadbetteretal.(1983),givestheoreticalresultscoveringperhaps10ofour examples. One could write ten similar books, each covering 10 examples from another (cid:12)eld. But I don’t have the energy or inclination to do so, which is one reason why this book gives only heuristics. Another reason is that connections between examples in di(cid:11)erent (cid:12)elds are much clearer in theheuristictreatmentthaninacompletetechnicaltreatment,and Ihope iii this book will make these connections more visible. At the risk of boring some readers and annoying others, here is a para- graph on the philosophy of approximations, heuristic and limit theorems. Theproperbusinessofprobabilistsiscalculatingprobabilities.Oftenexact calculations are tedious or impossible, so we resort to approximations. A limit theorem is an assertion of the form: \the error in a certain approxi- mationtendsto0as(say)N ".Callsuch limit theoremnaiveifthere !1 is no explicit error bound in terms of N and the parameters of the under- lying process. Such theorems are so prevalent in theoretical and applied probability that people seldom stop to ask their purpose. Given a serious applied problem involving speci(cid:12)c parameters, the natural (cid:12)rst steps are to seek rough analytic approximations and to run computer simulations; the next step is to do careful numerical analysis. It is hard to give any argument for the relevance of a proof of a naive limit theorem, except as a vague reassurance that your approximation is sensible, and a good heuris- tic argument seems equally reassuring. For the theoretician, the defense of naive limit theorems is \I want to prove something, and that’s all I can prove".Thereare(cid:12)eldswhicharesu(cid:14)cientlyhardthatthisisareasonable attitude (some of the areas in Chapters G, I, J for example), but in most of the (cid:12)elds in this book the theoretical tools for proving naive limit the- orems have been su(cid:14)ciently developed that such theorems are no longer of serious theoreticalresearch interest (although a fewbooks consolidating the techniques would be useful). Mostofourapproximations inparticularexamplescorrespondtoknown naive limit theorems, mentioned in the Commentaries. I deliberately de- emphasizethisaspect,sinceasarguedaboveIregardthenaivelimittheory asirrelevantforapplicationsandmostlytriteastheory.Ontheotherhand, explicit error bounds are plainly relevant for applications and interesting astheory(becausetheyaredi(cid:14)cult,forastart!).Inmostofourexamples, explicit error bounds are not know: I regard this as an important area for future research. Stein’s method is a powerful modern tool for getting explicit bounds in \combinatorial" type examples, whose potential is not widely realized. Hopefully other tools will become available in the future. Acknowledgements: As someone unable to recollect what I had for dinner last night, I am even more unable to recollect the many people who (con- sciously or unconsciously) provided sources of the examples; but I thank them.CoursebasedonpartialearlydraftsofthebookweregiveninBerke- ley in 1984 and Cornell in 1986, and I thank the audiences for their feed- back. In particular, I thank Persi Diaconis, Rick Durrett, Harry Kesten, V. Anantharam and Jim Pitman for helpful comments. I also thank Pilar Fresnedo for drawing the diagrams, and Ed Sznyter for a great job con- a verting my haphazard two-(cid:12)ngered typing into this elegant LTEX book. Contents A The Heuristic 1 A1 The M/M/1 queue. : : : : : : : : : : : : : : : : : : : : : : : 1 A2 Mosaic processes on R2. : : : : : : : : : : : : : : : : : : : : 2 A3 Mosaic processes on other spaces. : : : : : : : : : : : : : : : 5 A4 The heuristic. : : : : : : : : : : : : : : : : : : : : : : : : : : 5 A5 Estimating clump sizes. : : : : : : : : : : : : : : : : : : : : 7 A6 The harmonic mean formula. : : : : : : : : : : : : : : : : : 8 A7 Conditioning on semi-local maxima. : : : : : : : : : : : : : 10 A8 The renewal-sojourn method. : : : : : : : : : : : : : : : : : 11 A9 The ergodic-exit method. : : : : : : : : : : : : : : : : : : : 12 A10 Limit assertions. : : : : : : : : : : : : : : : : : : : : : : : : 14 A11{A21 Commentary : : : : : : : : : : : : : : : : : : : : : : : 15 B Markov Chain Hitting Times 23 B1 Introduction. : : : : : : : : : : : : : : : : : : : : : : : : : : 23 B2 The heuristic for Markov hitting times.: : : : : : : : : : : : 24 B3 Example: Basic single server queue. : : : : : : : : : : : : : : 25 B4 Example: Birth-and-death processes. : : : : : : : : : : : : : 25 B5 Example: Patterns in coin-tossing. : : : : : : : : : : : : : : 26 B6 Example: Card-shu(cid:15)ing. : : : : : : : : : : : : : : : : : : : : 27 B7 Example: Random walk on Zd modN. : : : : : : : : : : : : 28 B8 Example: Random trapping on Zd. : : : : : : : : : : : : : : 28 B9 Example: Two M/M/1 queues in series. : : : : : : : : : : : 28 B10 Example: Large density of heads in coin-tossing. : : : : : : 29 B11 Counter-example. : : : : : : : : : : : : : : : : : : : : : : : : 30 B12 Hitting small subsets. : : : : : : : : : : : : : : : : : : : : : 30 B13 Example: Patterns in coin-tossing, continued. : : : : : : : : 31 B14 Example: Runs in biased die-throwing. : : : : : : : : : : : : 31 B15 Example: Random walk on Zd modN, continued. : : : : : 32 B16 Hitting sizable subsets. : : : : : : : : : : : : : : : : : : : : : 32 B17 Theergodic-exitformoftheheuristicforMarkovhittingtimes. 32 B18 Example: A simple reliability model. : : : : : : : : : : : : : 33 B19 Example: Timesharing computer. : : : : : : : : : : : : : : : 33 CONTENTS v B20 Example: Two M/M/1 queues in series. : : : : : : : : : : : 35 B21 Another queueing example. : : : : : : : : : : : : : : : : : : 37 B22 Example: Random regular graphs. : : : : : : : : : : : : : : 38 B23{B32 Commentary : : : : : : : : : : : : : : : : : : : : : : : 38 C Extremes of Stationary Processes 44 C1 Classical i.i.d. extreme value theory. : : : : : : : : : : : : : 44 C2 Examples of maxima of i.i.d. sequences. : : : : : : : : : : : 45 C3 The point process formulation. : : : : : : : : : : : : : : : : 47 C4 The heuristic for dependent extrema. : : : : : : : : : : : : : 48 C5 Autoregressive and moving average sequences. : : : : : : : : 48 C6 Example: Exponential tails. : : : : : : : : : : : : : : : : : : 49 C7 Approximate independence of tail values. : : : : : : : : : : 50 C8 Example: Superexponential tails. : : : : : : : : : : : : : : : 50 C9 Example: Polynomial tails. : : : : : : : : : : : : : : : : : : 50 C10 The heuristic for dependent extrema (continued). : : : : : : 51 C11 Additive Markov processes on [0; ). : : : : : : : : : : : : : 52 1 C12 Continuous time processes: the smooth case. : : : : : : : : : 54 C13 Example: System response to external shocks. : : : : : : : : 55 C14 Example: Uniform distribution of the Poisson process. : : : 56 C15 Drift-jump processes. : : : : : : : : : : : : : : : : : : : : : : 57 C16 Example: Positive, additive processes. : : : : : : : : : : : : 58 C17 Example: Signed additive processes. : : : : : : : : : : : : : 58 C18 Positive, general drift processes. : : : : : : : : : : : : : : : : 58 C19 Autoregressive symmetric stable process. : : : : : : : : : : : 59 C20 Example: The I5 problem. : : : : : : : : : : : : : : : : : : : 60 C21 Approximations for the normal distribution. : : : : : : : : : 62 C22 Gaussian processes. : : : : : : : : : : : : : : : : : : : : : : : 63 C23 The heuristic for smooth Gaussian processes. : : : : : : : : 64 C24 Monotonicity convention. : : : : : : : : : : : : : : : : : : : 64 C25 High-level behavior of smooth Gaussian processes. : : : : : 65 C26 Conditioning on semi-local maxima. : : : : : : : : : : : : : 66 C27 Variations on a theme. : : : : : : : : : : : : : : : : : : : : : 67 C28 Example: Smooth 2 processes. : : : : : : : : : : : : : : : : 68 X C29{C40 Commentary : : : : : : : : : : : : : : : : : : : : : : : 69 D Extremes of Locally Brownian Processes 72 D1 Brownian motion.: : : : : : : : : : : : : : : : : : : : : : : : 72 D2 The heuristic for locally Brownian processes. : : : : : : : : 73 D3 One-dimensional di(cid:11)usions. : : : : : : : : : : : : : : : : : : 74 D4 First hitting times for positive-recurrent di(cid:11)usions. : : : : : 76 D5 Example: Gamma di(cid:11)usion. : : : : : : : : : : : : : : : : : : 77 D6 Example: Re(cid:13)ecting Brownian motion. : : : : : : : : : : : : 78 D7 Example: Di(cid:11)usions under a potential. : : : : : : : : : : : : 78 D8 Example: State-dependent M/M/1 queue. : : : : : : : : : : 79 vi CONTENTS D9 Example: The Ornstein-Uhlenbeck process. : : : : : : : : : 80 D10 Gaussian processes. : : : : : : : : : : : : : : : : : : : : : : : 81 D11 Example: System response to external shocks. : : : : : : : : 82 D12 Example: Maximum of self-normalized Brownian bridge. : : 82 D13 Boundary-crossing. : : : : : : : : : : : : : : : : : : : : : : : 83 D14 Example: Boundary-crossing for re(cid:13)ecting Brownian motion. 84 D15 Example: Brownian LIL. : : : : : : : : : : : : : : : : : : : : 85 D16 Maximaandboundary-crossingforgeneralGaussianprocesses. 86 D17 Example: Maximum of Brownian bridge. : : : : : : : : : : : 86 D18 Maxima of non-stationary Gaussian processes.: : : : : : : : 87 D19 Example: Maximum of Brownian Bridge with drift. : : : : : 88 D20 Example: Brownian motion and quadratic boundary. : : : : 88 D21 Example: Ornstein-Uhlenbeck quadratic boundary. : : : : : 89 D22 Semi-local maxima for the Ornstein-Uhlenbeck process. : : 90 D23 Example: A storage/queuing process. : : : : : : : : : : : : : 91 D24 Approximation by unstable Ornstein-Uhlenbeck process. : : 93 D25 Example: Escape from a potential well. : : : : : : : : : : : 93 D26 Example: Di(cid:11)usion in random environment. : : : : : : : : : 94 D27 Interpolating between Gaussian processes. : : : : : : : : : : 95 D28 Example: Smoothed Ornstein-Uhlenbeck. : : : : : : : : : : 95 D29 Boundary-crossing revisited. : : : : : : : : : : : : : : : : : : 97 D30 Tangent approximation for Brownian boundary-crossing. : : 99 D31{D42 Commentary : : : : : : : : : : : : : : : : : : : : : : : 100 E Simple Combinatorics 106 E1 Introduction. : : : : : : : : : : : : : : : : : : : : : : : : : : 106 E2 Poissonization. : : : : : : : : : : : : : : : : : : : : : : : : : 107 E3 Example: The birthday problem. : : : : : : : : : : : : : : : 108 E4 Example: K-matches. : : : : : : : : : : : : : : : : : : : : : 109 E5 Example: Unequal probabilities.: : : : : : : : : : : : : : : : 109 E6 Example: Marsaglia random number test. : : : : : : : : : : 110 E7 Several types of coincidence. : : : : : : : : : : : : : : : : : : 110 E8 Example: Similar bridge hands. : : : : : : : : : : : : : : : : 111 E9 Example: Matching K-sets. : : : : : : : : : : : : : : : : : : 112 E10 Example: Nearby pairs. : : : : : : : : : : : : : : : : : : : : 112 E11 Example: Basic coupon-collectors problem. : : : : : : : : : 113 E12 Example: Time until most boxes have at least one ball.: : : 113 E13 Example: Time until all boxes have at least (K+1) balls. : 114 E14 Example: Unequal probabilities.: : : : : : : : : : : : : : : : 114 E15 Abstract versions of CCP. : : : : : : : : : : : : : : : : : : : 114 E16 Example: Counting regular graphs. : : : : : : : : : : : : : : 115 E17{E22 Commentary : : : : : : : : : : : : : : : : : : : : : : : 116 CONTENTS vii F Combinatorics for Processes 118 F1 Birthday problem for Markov chains. : : : : : : : : : : : : : 118 F2 Example: Simple random walk on ZK. : : : : : : : : : : : : 119 F3 Example: Random walks with large step.: : : : : : : : : : : 119 F4 Example: Simple random walk on the K-cube. : : : : : : : 120 F5 Example: Another card shu(cid:15)e. : : : : : : : : : : : : : : : : 120 F6 Matching problems. : : : : : : : : : : : : : : : : : : : : : : 120 F7 Matching blocks. : : : : : : : : : : : : : : : : : : : : : : : : 122 F8 Example: Matching blocks: the i.i.d. case. : : : : : : : : : : 122 F9 Example: Matching blocks: the Markov case. : : : : : : : : 123 F10 Birthday problem for blocks. : : : : : : : : : : : : : : : : : 124 F11 Covering problems. : : : : : : : : : : : : : : : : : : : : : : : 124 F12 Covering problems for random walks. : : : : : : : : : : : : : 125 F13 Example: Random walk on Zd modulo N. : : : : : : : : : : 126 F14 Example: Simple random walk on the K-cube. : : : : : : : 126 F15 Covering problem for i.i.d. blocks. : : : : : : : : : : : : : : 127 F16 Example: Dispersal of many walks. : : : : : : : : : : : : : : 127 F17 Example: M/M/ combinatorics. : : : : : : : : : : : : : : 128 1 F18{F21 Commentary : : : : : : : : : : : : : : : : : : : : : : : 129 G Exponential Combinatorial Extrema 131 G1 Introduction. : : : : : : : : : : : : : : : : : : : : : : : : : : 131 G2 Example: Cliques in random graphs. : : : : : : : : : : : : : 132 G3 Example: Covering problem on the K-cube. : : : : : : : : : 133 G4 Example: Optimum partitioning of numbers. : : : : : : : : 134 G5 Exponential sums. : : : : : : : : : : : : : : : : : : : : : : : 135 G6 Example: First-passage percolation on the binary tree. : : : 136 G7 Example: Percolation on the K-cube.: : : : : : : : : : : : : 138 G8 Example: Bayesian binary strings. : : : : : : : : : : : : : : 139 G9 Example: Common cycle partitions in random permutations. 140 G10 Conditioning on maxima. : : : : : : : : : : : : : : : : : : : 141 G11 Example: Common subsequences in fair coin-tossing. : : : : 141 G12 Example: Anticliques in sparse random graphs. : : : : : : : 142 G13 The harmonic mean formula. : : : : : : : : : : : : : : : : : 143 G14 Example: Partitioning sparse random graphs. : : : : : : : : 143 G15 Tree-indexed processes. : : : : : : : : : : : : : : : : : : : : 145 G16 Example: An additive process. : : : : : : : : : : : : : : : : 145 G17 Example: An extremal process. : : : : : : : : : : : : : : : : 146 G18{G22 Commentary : : : : : : : : : : : : : : : : : : : : : : : 147 H Stochastic Geometry 149 H1 Example: Holes and clusters in random scatter. : : : : : : : 149 H2 The Poisson line process. : : : : : : : : : : : : : : : : : : : 151 H3 A clump size calculation. : : : : : : : : : : : : : : : : : : : 152 H4 Example: Empty squares in random scatter. : : : : : : : : : 154 viii CONTENTS H5 Example: Empty rectangles in random scatter. : : : : : : : 156 H6 Example: Overlapping random squares. : : : : : : : : : : : 157 H7 Example: Covering K times.: : : : : : : : : : : : : : : : : : 159 H8 Example: Several types of particle. : : : : : : : : : : : : : : 159 H9 Example: Non-uniform distributions. : : : : : : : : : : : : : 160 H10 Example: Monochrome squares on colored lattice. : : : : : : 161 H11 Example: Caps and great circles. : : : : : : : : : : : : : : : 161 H12 Example: Covering the line with intervals of random length. 162 H13 Example: Clusters in 1-dimensional Poisson processes. : : : 164 H14{H21 Commentary : : : : : : : : : : : : : : : : : : : : : : : 165 I Multi-Dimensional Di(cid:11)usions 167 I1 Background.: : : : : : : : : : : : : : : : : : : : : : : : : : : 167 I2 The heuristic. : : : : : : : : : : : : : : : : : : : : : : : : : : 169 I3 Potential function. : : : : : : : : : : : : : : : : : : : : : : : 169 I4 Reversible di(cid:11)usions. : : : : : : : : : : : : : : : : : : : : : : 169 I5 Ornstein-Uhlenbeck processes. : : : : : : : : : : : : : : : : : 170 I6 Brownian motion on surface of sphere. : : : : : : : : : : : : 170 I7 Local approximations. : : : : : : : : : : : : : : : : : : : : : 170 I8 Example: Hitting times to small balls. : : : : : : : : : : : : 171 I9 Example: Near misses of moving particles. : : : : : : : : : : 171 I10 Example: A simple aggregation-disaggregation model. : : : 173 I11 Example: Extremes for di(cid:11)usions controlled by potentials. : 173 I12 Example: Escape from potential wells. : : : : : : : : : : : : 176 I13 Physical di(cid:11)usions: Kramers’ equation. : : : : : : : : : : : : 177 I14 Example: Extreme values. : : : : : : : : : : : : : : : : : : : 178 I15 Example: Escape from potential well.: : : : : : : : : : : : : 180 I16 Example: Lower boundaries for transient Brownian motion. 182 I17 Example: Brownian motion on surface of sphere. : : : : : : 183 I18 Rice’s formula for conditionally locally Brownian processes. 185 I19 Example: Rough 2 processes. : : : : : : : : : : : : : : : : 186 X I20{I29 Commentary : : : : : : : : : : : : : : : : : : : : : : : 186 J Random Fields 190 J1 Spatial processes. : : : : : : : : : : : : : : : : : : : : : : : : 190 J2 In analysis of 1-parameter processes. : : : : : : : : : : : : : 190 J3 Gaussian (cid:12)elds and white noise. : : : : : : : : : : : : : : : : 190 J4 Analogues of the Kolmogorov-Smirnov test. : : : : : : : : : 191 J5 The heuristic. : : : : : : : : : : : : : : : : : : : : : : : : : : 192 J6 Discrete processes. : : : : : : : : : : : : : : : : : : : : : : : 192 J7 Example: Smooth Gaussian (cid:12)elds. : : : : : : : : : : : : : : 193 J8 Example: 2-dimensional shot noise. : : : : : : : : : : : : : : 195 J9 Uncorrelated orthogonal increments Gaussian processes. : : 195 J10 Example: Product Ornstein-Uhlenbeck processes. : : : : : : 196 J11 An arti(cid:12)cial example. : : : : : : : : : : : : : : : : : : : : : 197 CONTENTS ix J12 Maxima of (cid:22)-Brownian sheets. : : : : : : : : : : : : : : : : 198 J13 1-parameter Brownian bridge. : : : : : : : : : : : : : : : : : 198 J14 Example: Stationary Brownian bridge processes. : : : : : 200 (cid:2) J15 Example: Range of Brownian bridge. : : : : : : : : : : : : : 201 J16 Example: Multidimensional Kolmogorov-Smirnov.: : : : : : 202 J17 Example: Rectangle-indexed sheets. : : : : : : : : : : : : : 204 J18 Isotropic Gaussian processes. : : : : : : : : : : : : : : : : : 205 J19 Slepian’s inequality. : : : : : : : : : : : : : : : : : : : : : : 206 J20 Bounds from the harmonic mean. : : : : : : : : : : : : : : : 207 J21 Example: Hemispherical caps. : : : : : : : : : : : : : : : : : 208 J22 Example: Half-plane indexed sheets. : : : : : : : : : : : : : 209 J23 The power formula. : : : : : : : : : : : : : : : : : : : : : : : 212 J24 Self-normalized Gaussian (cid:12)elds. : : : : : : : : : : : : : : : : 212 J25 Example: Self-normalized Brownian motion increments. : : 212 J26 Example: Self-normalized Brownian bridge increments. : : : 213 J27 Example: Upturns in Brownian bridge with drift. : : : : : : 214 J28 Example: 2-parameter LIL. : : : : : : : : : : : : : : : : : : 215 J29{J37 Commentary : : : : : : : : : : : : : : : : : : : : : : : 216 K Brownian Motion: Local Distributions 220 K1 Modulus of continuity. : : : : : : : : : : : : : : : : : : : : : 220 K2 Example: The Chung-Erdos-Sirao test. : : : : : : : : : : : : 221 K3 Example: The asymptotic distribution of W. : : : : : : : : 221 K4 Example: Spikes in Brownian motion. : : : : : : : : : : : : 224 K5 Example: Small increments. : : : : : : : : : : : : : : : : : : 225 K6 Example: Integral tests for small increments. : : : : : : : : 228 K7 Example: Local maxima and points of increase. : : : : : : : 230 K8 Example:Self-intersectionsofd-dimensionalBrownianmotion.233 K9{K17 Commentary : : : : : : : : : : : : : : : : : : : : : : : 234 L Miscellaneous Examples 237 L1 Example: Meetings of empirical distribution functions. : : : 237 L2 Example: Maximal k-spacing. : : : : : : : : : : : : : : : : : 238 L3 Example: Increasing runs in i.i.d. sequences. : : : : : : : : : 239 L4 Example: Growing arcs on a circle. : : : : : : : : : : : : : : 239 L5 Example: The LIL for symmetric stable processes. : : : : : 241 L6 Example: Min-max of process.: : : : : : : : : : : : : : : : : 242 L7 2-dimensional random walk : : : : : : : : : : : : : : : : : : 243 L8 Example: Random walk on Z2 modulo N. : : : : : : : : : : 244 L9 Example: Covering problems for 2-dimensional walks. : : : 244 x CONTENTS M The Eigenvalue Method 246 M1 Introduction. : : : : : : : : : : : : : : : : : : : : : : : : : : 246 M2 The asymptotic geometric clump principle. : : : : : : : : : 247 M3 Example: Runs in subsets of Markov chains. : : : : : : : : : 248 M4 Example: Coincident Markov chains. : : : : : : : : : : : : : 248 M5 Example: Alternating runs in i.i.d. sequences. : : : : : : : : 248 M6 Example: Longest busy period in M/G/1 queue. : : : : : : 250 M7 Example: Longest interior sojourn of a di(cid:11)usion. : : : : : : 250 M8 Example: Boundary crossing for di(cid:11)usions.: : : : : : : : : : 251 Postscript 252 Bibliography 253