BOLYAI SOCIETY MATHEMATICAL STUDIES, 9
Random Walks

EDITED BY
Pal Revesz, Alfred Renyi Institute of Mathematics, Hungarian Academy of Sciences
Balint Toth, Technical University Budapest, Institute of Mathematics

(C) BOLYAI JÁNOS MATEMATIKAI TARSULAT
Budapest, Hungary, 1999

1991 Mathematics Subject Classification
Primary: 60J15, 60J65
Secondary: 60F05, 60F10, 60F15, 60F17, 60G17, 60G18, 60J45, 60J55, 60J85, 60K35, 60K40

ISBN: 963 8022 91 4 ISSN: 1217--4696

Contents

Contents   ...   3
Introduction   ...   5
R. C. Bradley: Can a theorem of Csaki and Fischer provide a key to Ibragimov's conjecture?   ...   11
E. Csaki, A. Foldes, P. Revesz, Z. Shi: On the excursions of two-dimensional random walk and Wiener process   ...   43
M. Csorgo: Random walking around financial mathematics   ...   59
B. Davis: Reinforced and perturbed random walks   ...   113
N. Gantert, O. Zeitouni: Large deviations for one-dimensional random walk in random environment -- a survey   ...   127
J. Gravner, D. Griffeath: Scaling laws for a class of critical cellular automaton growth rules   ...   167
Y. Hu, M. Yor: Asymptotic studies of brownian functionals   ...   187
G. Lawler: Geometric and fractal properties of brownian motion and random walk paths in two and three dimensions   ...   219
S. G. Mohanty: Combinatorial aspects of some random walks   ...   259
G. Pap, M. Voit: Rates of convergence for the central limit theorems for random walks related with the Hankel transform   ...   275
P. Revesz: Critical branching Wiener process   ...   299
B. Toth: Self-interacting random motions -- A survey   ...   349

Preface

The present volume surveys recent developments in the area of random walks. This most classical area of probability theory has recently witnessed the emergence of a host of new and surprising techniques and exciting links to various other branches of mathematics and science.

The volume provides a written record of the highly successful International Workshop on Random Walks held in Budapest between July 13 and 24, 1998 under the auspices of the newly established Paul Erdõs Summer Research Center of Mathematics.

About fifty registered participants took part in the workshop. The following main speakers presented two- to four-hour lecture series: Richard Bradley (Bloomington, IN), Miklós Csörgõ (Ottawa), Burgess Davis (West Lafayette, IN), Paul Deheuvels (Paris), David Griffeath (Madison, WI), Janko Gravner (Davis, CA), James Kuelbs (Madison, WI), Gregory Lawler (Durham, NC), Yuval Peres (Jerusalem), Pál Révész (Budapest), Bálint Tóth (Budapest), Mark Yor (Paris). Most other participants contributed one-hour lectures.

Eight out of the ten lecture series presented at the workshop are represented by survey articles in this volume. The written versions of four additional lectures, discussing topics of particular interest, are also included. All papers were thoroughly refereed.

As an appetizer, we offer a brief review of the volume.

In the first paper of this collection, Richard C. Bradley presents a thorough panoramic survey of existing classical and more recent results on central limit theorems and invariance principles for partial sums of strictly stationary random variables under various mixing conditions. The main emphasis of the paper is on a possibly promising attempt to the proof of the famous conjecture of I. A. Ibragimov, stating essentially that for a sequence of strictly stationary and phi-mixing random variables finiteness of the second moment alone guarantees the validity of the CLT. A certain theorem of Péter Csáki and János Fischer play a central role in the outlined approach. No doubt, this paper (and its exhaustive list of references) is a self contained rich source of information and ideas for the researcher working in the field of general limit theorems of probability and statistics.

Endre Csáki, Antónia Földes, Pál Révész and Zhan Shi prove new results about the asymptotic behaviour of excursions of the two-dimensional random walk and Brownian motion. It is known (from earlier work of Csáki et al.) that for 2-d random walk, asymptotically as n to infinity, the two longest excursions span essentially the whole time interval [0,n]. In the present paper the authors investigate the asymptotics of the total time spanned by the remaining excursions, i.e., how big (or how small) is the gap between n and the total span of the two longest excursions. The answer is given in terms of upper-upper, upper-lower, lower-upper and lower-lower function classes.

Financial mathematics is one of the particularly active areas of present-day stochastics. In his paper, Miklós Csörgõ gives a comprehensive survey of this major field. One of the great merits of this paper is that the relevant mathematics is presented in its historical context. The paper is an enjoyable reading for the educated mathematician working in any field. After giving a self-contained background on stochastic analysis (Itô calculus included), the author turns to the problem of fair pricing of financial derivatives and the Black-Scholes formulas. In the last two sections of the paper, technically more advanced topics are presented, such as estimating the volatility parameter in the BS formula and strong (pathwise) approximation of the logarithm of integral functionals of various geometric (exponential) stochastic processes.

The so-called reinforced random walks form a natural family of random walks with long-term pathwise self-interaction. In its classical formulation: a nearest neighbour walk on Zd chooses its next position always with probability proportional to a weight linearly increasing with the number of previous visits at the edge to be used. (To our knowledge the problem has its origins in unpublished work of P. Diaconis.) The first natural question to ask is the problem of recurrence/transience of such a random walk, and generalizations with other (non-linearly varying) weight functions. Burgess Davis presents a survey of the actual state of knowledge about these problems in a wide context of 1-d reinforced random walks. (The recurrence problem in higher dimensions is almost completely open.)

Models of random walks in random environments (RWRE) have been mathematically rigorously investigated since the mid-seventies. In one space dimension the questions of recurrence, almost sure asymptotic speed (law of large numbers) and fluctuations around this (limit theorems) have been elucidated in a satisfactory way in, by now classical, papers by F. Solomon; H. Kesten, S. Kozlov and F. Spitzer; Ya. G. Sinai, to mention only some of the most influential ones. Nina Gantert and Ofer Zeitouni review recent results on the large deviation behaviour of the 1-d RWRE model. They present precise asymptotics of the probability of rare events of the form P (Xn/n in A) in the non-typical situation when this probability decays to zero. It turns out that the RWRE exhibits a wide range of non-trivial large deviation behaviours, and different regimes occur.

Lattice growth models governed by some deterministic or stochastic local rule exhibit surprisingly rich structural behaviour. Beside the mathematical beauty and difficulty, the wide range of natural phenomena modeled by these cellular automata make these topics of central interest in modern probability theory. The major problems addressed are related to the long-time asymptotics of the growing object: asymptotic shape, fluctuations around it etc. Janko Gravner and David Griffeath survey recent results concerning the so-called monotone solidification cellular automaton models. These are models governed by a certain class of deterministic growth rules. Randomness comes with the initial conditions of the evolution. Typical questions addressed are: scaling laws of the first passage time to the origin, asymptotic shapes, ability of the dynamics to overcome pollution of the lattice etc. In addition to the theorems valid for classes of growth rules, concrete explicit examples are also presented together with graphical representation of simulations.

Yueyun Hu and Marc Yor review results about the long-time asymptotics of some additive functionals of Brownian motion. The additive functionals considered are typically of the form Integral from 0to t  :  f(Bs) ds or Integral from 0to t  :  Integral from 0to s  :  f(Bs- Bu)  du  ds where Bt denotes d-dimensional standard Brownian motion and f:  Rd  ->  R is a locally integrable function. The first of these two functionals is related to the occupation time measure (in 1-d, local time), the second one to the so-called self intersection local time of the Brownian motion -- the natural object of study in this context. Some polymer measures, i.e., models of self-repelling random motions, are also considered in the paper. Although mainly of survey nature, the paper also contains some new asymptotic results.

Gregory F. Lawler's paper is a `state of the art report' on the critical exponents and fractal geometry of Brownian motion paths. It turns out that critical exponents that describe the decay rate of certain rare events on the one hand and topological and metric characteristics (e.g. Hausdorff dimension) of certain random sets defined by the Brownian motion path on the other hand, are very closely related. Typical examples for the exponents arising are the so-called intersection exponents (e.g., in 2-d, the probability that two independent random walk paths do not intersect up to time t decays as t-zeta, with zeta = 2/8 conjectured). Typical examples of random sets defined by the BM path are: the set of cut-points, the set of frontier points, etc. Considerable progress made in the last few years is reported in the present survey. Besides the intrinsic mathematical interest these results have physical relevance, too, as the 2-d theory seems to be strongly related to the conformal invariance of critical phenomena in 2-d statistical physics.

Sri Gopal Mohanty surveys the combinatorial background of one-dimensional random walk in the transient case, with special regard to the transient behaviour of a birth--death process and coincidence probabilities.

The classical Berry--Esseen inequality provides an upper bound on the rate of convergence in the central limit theorem, relating the Linfinity distance of probability distribution functions to their Fourier transforms. Similar inequalities, related to other integral transforms and providing upper bounds on the convergence rate in other types of limit theorems (exhibiting, e.g., spherical symmetry rather than Euclidean) have been developed in recent years. The main purpose of Gyula Pap and Michael Voit in their present article is to prove Berry--Esseen-type inequalities related to the Hankel transform on [0,infinity), with parameter alpha in [-1/2, infinity). The inequalities proved also lead to upper bounds on the rate of convergence in limit theorems, with so-called Reyleigh distribution nualpha as limit. Applications to limit theorems for certain birth and death processes are also presented.

In the last twenty years there has been a growing interest in the d-dimensional branching Wiener process, especially in the critical case. Pál Révész surveys recent results in this area, at least in the simplest case. In fact that case is studied when the particles are branching only in discrete times 1, 2, ... and the number of offspring of each particle is either 0 or 2, with probability 1/2 and 1/2, respectively. Clearly this process is dying out, with probability 1, after a finite time. However if the process lives through a long enough time then the number of living particles is large. The paper investigates the asymptotic distribution of the particles in the d-dimensional Euclidean space.

Finally, in the last article of this volume Bálint Tóth surveys results on late-time asymptotic behaviour of self-interacting random walks (SIRW) and on the construction of a new type of stochastic process called true self-repelling motion. One of the typical examples is the so-called exponentially self-repelling (or myopic self-avoiding) random walk. A wide range of limit theorems is presented, with unusual scaling behaviour. E.g., for the myopic self-avoiding walk in 1-d, the overdiffusive scaling rate of (time)2/3is found, in accordance with the physicists' predictions. A continuous stochastic process with striking phenomenological (`physical') and analytic features (such as local self-repellence, 2/3 scaling exponent, non-trivial local variation of order 3/2) is also constructed. This construction provides an example of a true polymer measure in 1-d.

Acknowledgements

Initiated by the many Hungarian friends and collaborators of Paul Erdõs (1913--1996), the Paul Erdõs Summer Research Center of Mathematics was inaugurated at the Alfréd Rényi Institute of Mathematics in Budapest (formerly the Mathematical Institute of the Hungarian Academy of Sciences) in March 1998. One of the first events organized under the auspices of the Erdõs Center was the workshop on Random Walks, a subject which owes several fundamental discoveries to Uncle Paul.

The following Hungarian and US institutions provided generous support to run the Erdõs Center: the Hungarian Ministry of Culture and Education, the János Bolyai Mathematical Society, the Hungarian Academy of Sciences, DIMACS (New Jersey), Microsoft Research, and Lucent Technologies.

The organizers are grateful to the above mentioned general sponsors of the Erdõs Center and to the Hungarian Banking and Capital Market Supervision, special sponsor of our workshop.

We wish to thank all participants for their contribution to the success of this event. And above all, we wish to thank the contributors to the present volume for creating this exciting collection.

Pál Révész and Bálint Tóth