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     

Anomalous behaviour for the random corrections to the cumulants of random walks in fluctuating random media

The Central Limit Theorem for a model of discrete-time random walks on the lattice ℤ^ν in a fluctuating random environment was proved for almost-all realizations of the space-time nvironment, for all ν > 1 in [BMP1] and for all ν≥ 1 in [BBMP]. In [BMP1] it was proved that the random correction to the average of the random walk for ν≥ 3 is finite. In the present paper we consider the cases ν = 1,2 and prove the Central Limit Theorem as T→∞ for the random correction to the first two cumulants. The rescaling factor for theaverage is for ν = 1 and (ln T), for ν=2; for the covariance it is , ν = 1,2. Received: 25 November 1999 / Revised version: 7 June 2000 / Published online: 15 February 2001     

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     

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     

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     

On the Metrical Theory of Continued Fraction Mixing Fibred Systems and Its Application to Jacobi-Perron Algorithm

 We study the metrical theory of fibred systems, in particular, in the case of continued fraction mixing systems. We get the limit distribution of the largest value of a continued fraction mixing stationary stochastic process with infinite expectation and some related results. These are analogous to J. Galambos, W. Philipp, and H. G. Diamond–J. D. Vaaler theorems for the regular continued fractions. As an application, we see that these theorems hold for Jacobi-Perron algorithm. Received September 30, 2001; in revised form January 8, 2002     

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     

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     

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     

Inégalités de concentration pour les processus empiriques de classes de parties

We propose new concentration inequalities for maxima of set-indexed empirical processes. Our approach is based either on entropy inequalities or on martingale methods. The improvements we get concern the rate function which is exactly the large deviations rate function of a binomial law in most of the cases. Received: 11 January 2000 / Revised version: 12 May 2000 / Published online: 14 December 2000     

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     

Explaining the Gentzen–Takeuti reduction steps: a second-order system

Using the concept of notations for infinitary derivations we give an explanation of Takeuti's reduction steps on finite derivations (used in his consistency proof for Π¹ ₁-CA) in terms of the more perspicious infinitary approach from [BS88]. Received: 27 April 1999 / Published online: 21 March 2001     

Bogomolov inequality for Higgs parabolic bundles

We show that over some smooth projective varieties every semistable Higgs logarithmic vector bundle is semistable in the ordinary sense, hence satisfies Bogomolov inequality. More generaly, we prove that semistable Higgs parabolic vector bundles of rank two over smooth projective varieties of dimension ≥ 2 satisfy the “parabolic” 'Bogomolov inequality Received: 1 March 1999 / Revised version: 11 June 1999     

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     

One-sided local large deviation and renewal theorems in the case of infinite mean

Summary. If {S _n ,n≧0} is an integer-valued random walk such that S _n /a _n converges in distribution to a stable law of index α∈ (0,1) as n→∞, then Gnedenko’s local limit theorem provides a useful estimate for P{S _n =r} for values of r such that r/a _n is bounded. The main point of this paper is to show that, under certain circumstances, there is another estimate which is valid when r/a _n → +∞, in other words to establish a large deviation local limit theorem. We also give an asymptotic bound for P{S _n =r} which is valid under weaker assumptions. This last result is then used in establishing some local versions of generalized renewal theorems. Received: 9 August 1995 / In revised form: 29 September 1996     

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     

Malliavin calculus and asymptotic expansion for martingales

Summary. We present an asymptotic expansion of the distribution of a random variable which admits a stochastic expansion around a continuous martingale. The emphasis is put on the use of the Malliavin calculus; the uniform nondegeneracy of the Malliavin covariance under certain truncation plays an essential role as the Cramér condition did in the case of independent observations. Applications to statistics are presented. Received: 5 September 1995 / In revised form: 20 October 1996     

Large deviation principles for Euclidean functionals and other nearly additive processes

We prove a large deviation principle for a process indexed by cubes of the multidimensional integer lattice or Euclidean space, under approximate additivity and regularity hypotheses. The rate function is the convex dual of the limiting logarithmic moment generating function. In some applications the rate function can be expressed in terms of relative entropy. The general result applies to processes in Euclidean combinatorial optimization, statistical mechanics, and computational geometry. Examples include the length of the minimal tour (the traveling salesman problem), the length of the minimal matching graph, the length of the minimal spanning tree, the length of the k-nearest neighbors graph, and the free energy of a short-range spin glass model. Received: 3 April 1999 / Revised version: 23 June 1999 / Published online: 8 May 2001     

Natural deduction with general elimination rules

The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates. Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001