Brownian motion and random walk perturbed at extrema

Let b _t be Brownian motion. We show there is a unique adapted process x _t which satisfies dx _t = db _t except when x _t is at a maximum or a minimum, when it receives a push, the magnitudes and directions of the pushes being the parameters of the process. For some ranges of the parameters this is already known. We show that if a random walk close to b _t is perturbed properly, its paths are close to those of x _t . Received: 15 October 1997 / Revised version: 18 May 1998     

A new inductive approach to the lace expansion for self-avoiding walks

Summary. We introduce a new inductive approach to the lace expansion, and apply it to prove Gaussian behaviour for the weakly self-avoiding walk on ℤ ^d where loops of length m are penalised by a factor e ^{−β/m p} (0<β≪1) when: (1) d>4, p≥0; (2) d≤4, . In particular, we derive results first obtained by Brydges and Spencer (and revisited by other authors) for the case d>4, p=0. In addition, we prove a local central limit theorem, with the exception of the case d>4, p=0. Received: 29 October 1997 / In revised form: 15 January 1998     

Two renewal theorems for general random walks tending to infinity

Summary. Necessary and sufficient conditions for the existence of moments of the first passage time of a random walk S _n into [x, ∞) for fixed x≧ 0, and the last exit time of the walk from (−∞, x], are given under the condition that S _n →∞ a.s. The methods, which are quite different from those applied in the previously studied case of a positive mean for the increments of S _n , are further developed to obtain the “order of magnitude” as x→∞ of the moments of the first passage and last exit times, when these are finite. A number of other conditions of interest in renewal theory are also discussed, and some results for the first time for which the random walk remains above the level x on K consecutive occasions, which has applications in option pricing, are given. Received: 18 September 1995/In revised form: 28 February 1996     

The central limit theorem for Markov chains with normal transition operators, started at a point

The central limit theorem and the invariance principle, proved by Kipnis and Varadhan for reversible stationary ergodic Markov chains with respect to the stationary law, are established with respect to the law of the chain started at a fixed point, almost surely, under a slight reinforcing of their spectral assumption. The result is valid also for stationary ergodic chains whose transition operator is normal. Received: 28 March 2000 / Revised version: 25 July 2000 /?Published online: 15 February 2001     

Biased random walks on directed trees

Summary. We define directed rooted labeled and unlabeled trees and find measures on the space of directed rooted unlabeled trees which are invariant with respect to transition probabilities corresponding to a biased random walk on a directed rooted labeled tree. We use these to calculate the speed of a biased random walk on directed rooted labeled trees. The results are mainly applied to directed trees with recurrent subtrees, where the random walker cannot escape. Received: 12 March 1997/ In revised form: 11 December 1997     

Restricted random walks on a graph

The problem of a restricted random walk on graphs, which keeps track of the number of immediate reversal steps, is considered by using a transfer matrix formulation. A closed-form expression is obtained for the generating function of the number ofn-step walks withr reversal steps for walks on any graph. In the case of graphs of a uniform valence, we show that our result has a probabilistic meaning, and deduce explicit expressions for the generating function in terms of the eigenvalues of the adjacency matrix. Applications to periodic lattices and the complete graph are given.Supported in part by National Science Foundation Grant DMR-9614170.     

Anisotropic branching random walks on homogeneous trees

Symmetric branching random walk on a homogeneous tree exhibits a weak survival phase: For parameter values in a certain interval, the population survives forever with positive probability, but, with probability one, eventually vacates every finite subset of the tree. In this phase, particle trails must converge to the geometric boundaryΩ of the tree. The random subset Λ of the boundary consisting of all ends of the tree in which the population survives, called the limit set of the process, is shown to have Hausdorff dimension no larger than one half the Hausdorff dimension of the entire geometric boundary. Moreover, there is strict inequality at the phase separation point between weak and strong survival except when the branching random walk is isotropic. It is further shown that in all cases there is a distinguished probability measure μ supported by Ω such that the Hausdorff dimension of Λ∩Ω_μ, where Ω_μ is the set of μ-generic points of Ω, converges to one half the Hausdorff dimension of Ω_μ at the phase separation point. Exact formulas are obtained for the Hausdorff dimensions of Λ and Λ∩Ω_μ, and it is shown that the log Hausdorff dimension of Λ has critical exponent 1/2 at the phase separation point. Received: 30 June 1998 / Revised version: 10 March 1999     

Slowdown estimates and central limit theorem for random walks in random environment

This work is concerned with asymptotic properties of multi-dimensional random walks in random environment. Under Kalikow’s condition, we show a central limit theorem for random walks in random environment on ℤ ^d , when d≥2. We also derive tail estimates on the probability of slowdowns. These latter estimates are of special interest due to the natural interplay between slowdowns and the presence of traps in the medium. The tail behavior of the renewal time constructed in [25] plays an important role in the investigation of both problems. This article also improves the previous work of the author [24], concerning estimates of probabilities of slowdowns for walks which are neutral or biased to the right. Received May 31, 1999 / final version received January 18, 2000?Published online April 19, 2000     

Biased random walks on Galton–Watson trees

Summary. We consider random walks with a bias toward the root on the family tree T of a supercritical Galton–Watson branching process and show that the speed is positive whenever the walk is transient. The corresponding harmonic measures are carried by subsets of the boundary of dimension smaller than that of the whole boundary. When the bias is directed away from the root and the extinction probability is positive, the speed may be zero even though the walk is transient; the critical bias for positive speed is determined. Received: 7 July 1995 / In revised form: 9 January 1996     

On the distributions of the lengths of the longest monotone subsequences in random words

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. (In the limit as k→∞ these become the corresponding distributions for permutations on N letters.) We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating unction gives the distribution of the smallest eigenvalue in the k×k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N→∞ limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k×k hermitian matrices of trace zero. Received: 9 September 1999 / Revised version: 24 May 2000 / Published online: 24 January 2001     

A central limit theorem for stationary random fields

Summary. We prove a central limit theorem for strictly stationary random fields under a projective assumption. Our criterion is similar to projective criteria for stationary sequences derived from Gordin's theorem about approximating martingales. However our approach is completely different, for we establish our result by adapting Lindeberg's method. The criterion that it provides is weaker than martingale-type conditions, and moreover we obtain as a straightforward consequence, central limit theorems for α-mixing or φ-mixing random fields. Received: 19 February 1997 / In revised form: 2 September 1997     

The problem of the most visited site in random environment

We prove that the process of the most visited site of Sinai's simple random walk in random environment is transient. The rate of escape is characterized via an integral criterion. Our method also applies to a class of recurrent diffusion processes with random potentials. It is interesting to note that the corresponding problem for the usual symmetric Bernoulli walk or for Brownian motion remains open. Received: 17 April 1998     

The high temperature case for the random K-sat problem

We give a completely rigorous proof that the replica-symmetric solution holds at high enough temperature for the random K-sat problem. The most notable feature of this problem is that the order parameter of the system is a function and not a number. Received: 21 April 1998 / Revised version: 24 April 2000 / Published online: 21 December 2000     

Zeno's walk: A random walk with refinements

Summary. A self-modifying random walk on is derived from an ordinary random walk on the integers by interpolating a new vertex into each edge as it is crossed. This process converges almost surely to a random variable which is totally singular with respect to Lebesgue measure, and which is supported on a subset of having Hausdorff dimension less than , which we calculate by a theorem of Billingsley. By generating function techniques we then calculate the exponential rate of convergence of the process to its limit point, which may be taken as a bound for the convergence of the measure in the Wasserstein metric. We describe how the process may viewed as a random walk on the space of monotone piecewise linear functions, where moves are taken by successive compositions with a randomly chosen such function. Received: 20 November 1995 / In revised form: 14 May 1996     

An explicit upper bound for Weil-Petersson volumes of the moduli spaces of punctured Riemann surfaces

An explicit upper bound for the Weil-Petersson volumes of punctured Riemann surfaces is obtained using Penner's combinatorial integration scheme from [4]. It is shown that for a fixed number of punctures n and for genus g increasing, while this limit is exactly equal to two for n=1. Received: 17 May 2000 / Revised version: 9 August 2000 / Published online: 23 July 2001     

Homogenization of divergence-form operators with lower-order terms in random media

The probabilistic machinery (Central Limit Theorem, Feynman-Kac formula and Girsanov Theorem) is used to study the homogenization property for PDE with second-order partial differential operator in divergence-form whose coefficients are stationary, ergodic random fields. Furthermore, we use the theory of Dirichlet forms, so that the only conditions required on the coefficients are non-degeneracy and boundedness. Received: 27 August 1999 / Revised version: 27 October 2000 / Published online: 26 April 2001     

Entropy conditions for subsequences of random variables with applications to empirical processes

We introduce new entropy concepts measuring the size of a given class of increasing sequences of positive integers. Under the assumption that the entropy function of is not too large, many strong limit theorems will continue to hold uniformly over all sequences in . We demonstrate this fact by extending the Chung-Smirnov law of the iterated logarithm on empirical distribution functions for independent identically distributed random variables as well as for stationary strongly mixing sequences to hold uniformly over all sequences in . We prove a similar result for sequences (n _k ω) mod 1 where the sequence (n _k ) of real numbers satisfies a Hadamard gap condition. Authors’ addresses: István Berkes, Department of Statistics, Technical University Graz, Steyrergasse 17/IV, A-8010 Graz, Austria; Walter Philipp, Department of Statistics, University of Illinois, 725 S. Wright Street, Champaign, IL 61820, USA; Robert F. Tichy, Department of Analysis and Computational Number Theory, Technical University Graz, Steyrergasse 30, A-8010 Graz, Austria     

On the regularity of the distribution of the maximum of one-parameter Gaussian processes

The main result in this paper states that if a one-parameter Gaussian process has C ^2k paths and satisfies a non-degeneracy condition, then the distribution of its maximum on a compact interval is of class C ^k . The methods leading to this theorem permit also to give bounds on the successive derivatives of the distribution of the maximum and to study their asymptotic behaviour as the level tends to infinity. Received: 14 May 1999 / Revised version: 18 October 1999 / Published online: 14 December 2000     

Measure concentration for a class of random processes

Summary.   Let X={X _i } _{i =−∞} ^∞ be a stationary random process with a countable alphabet and distribution q. Let q ^∞(·|x _{− k} ⁰) denote the conditional distribution of X ^∞=(X ₁,X ₂,…,X _n ,…) given the k-length past: