Hammersley's interacting particle process and longest increasing subsequences

Summary In a famous paper [8] Hammersley investigated the lengthL _n of the longest increasing subsequence of a randomn-permutation. Implicit in that paper is a certain one-dimensional continuous-space interacting particle process. By studying a hydrodynamical limit for Hammersley's process we show by fairly “soft” arguments that limn ^′1/2 EL _n =2. This is a known result, but previous proofs [14, 11] relied on hard analysis of combinatorial asymptotics. Research supported by NSF Grant MCS 92-24857 and the Miller Institute for Basic Research in Science Research supported by NSF Grant DMS92-04864     

On the conditioned exit measures of super Brownian motion

In this paper we present a martingale related to the exit measures of super Brownian motion. By changing measure with this martingale in the canonical way we have a new process associated with the conditioned exit measure. This measure is shown to be identical to a measure generated by a non-homogeneous branching particle system with immigration of mass. An application is given to the problem of conditioning the exit measure to hit a number of specified points on the boundary of a domain. The results are similar in flavor to the “immortal particle” picture of conditioned super Brownian motion but more general, as the change of measure is given by a martingale which need not arise from a single harmonic function. Received: 27 August 1998 / Revised version: 8 January 1999     

Rates of convergence of random walk on distance regular graphs

When run on any non-bipartite q-distance regular graph from a family containing graphs of arbitrarily large diameter d, we show that d steps are necessary and sufficient to drive simple random walk to the uniform distribution in total variation distance, and that a sharp cutoff phenomenon occurs. For most examples, we determine the set on which the variation distance is achieved, and the precise rate at which it decays. The upper bound argument uses spectral methods – combining the usual Cauchy-Schwarz bound on variation distance with a bound on the tail probability of a first-hitting time, derived from its generating function. Received: 2 April 1997 / Revised version: 10 May 1998     

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     

N/V-limit for stochastic dynamics in continuous particle systems

We provide an N/V-limit for the infinite particle, infinite volume stochastic dynamics associated with Gibbs states in continuous particle systems on ℝ ^d ,d≥1. Starting point is an N-particle stochastic dynamic with singular interaction and reflecting boundary condition in a subset Λ⊂ℝ ^d with finite volume (Lebesgue measure) V=|Λ|<∞. The aim is to approximate the infinite particle, infinite volume stochastic dynamic by the above N-particle dynamic in Λ as N→∞ and V→∞ such that N/V→ρ, where ρ is the particle density. First we derive an improved Ruelle bound for the canonical correlation functions under an appropriate relation between N and V. Then tightness is shown by using the Lyons–Zheng decomposition. The equilibrium measures of the accumulation points are identified as infinite volume canonical Gibbs measures by an integration by parts formula and the accumulation points themselves are identified as infinite particle, infinite volume stochastic dynamics via the associated martingale problem. Assuming a property closely related to Markov uniqueness and weaker than essential self-adjointness, via Mosco convergence techniques we can identify the accumulation points as Markov processes and show uniqueness. I.e., all accumulation corresponding to one invariant canonical Gibbs measure coincide. The proofs work for general repulsive interaction potentials ϕ of Ruelle type and all temperatures, densities, and dimensions d≥1, respectively. ϕ may have a nontrivial negative part and infinite range as e.g. the Lennard–Jones potential. Additionally, our result provides as a by-product an approximation of grand canonical Gibbs measures by finite volume canonical Gibbs measures with empty boundary condition.     

Recurrence and ergodicity of interacting particle systems

Many interacting particle systems with short range interactions are not ergodic, but converge weakly towards a mixture of their ergodic invariant measures. The question arises whether a.s.the process eventually stays close to one of these ergodic states, or if it changes between the attainable ergodic states infinitely often (“recurrence”). Under the assumption that there exists a convergence–determining class of distributions that is (strongly) preserved under the dynamics, we show that the system is in fact recurrent in the above sense. We apply our method to several interacting particle systems, obtaining new or improved recurrence results. In addition, we answer a question raised by Ed Perkins concerning the change of the locally predominant type in a model of mutually catalytic branching. Received: 22 January 1999 / Revised version: 24 May 1999     

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     

On a modification of the classical risk process

In this paper, we present the classical risk process with two-step premium function. This means that the gross risk premium rate changes if the insurer’s surplus reaches a certain threshold level. The formula for the infinite-time ruin probability is obtained. The asymptotic behaviour of the ruin probability in the case where the claim size distribution has a light tail is considered as well.     

Martin–Kuramochi boundary and reflecting symmetric diffusion

In this paper, we will give sufficient conditions for the existence of the reflecting diffusion process on a locally compact space. In constructing reflecting diffusion process, we consider the corresponding Martin–Kuramochi boundary as the reflecting barrier and introduce the notion of strong (ℰ, u)-Caccioppoli set. Our method covers reflecting diffusion processes with diffusion coefficient degenerating on the boundary. Received: 23 June 1997 / Revised version: 28 September 1991/ Published online: 14 June 2000     

Partial regularity for variational integrals with (s,\mu ,q)–Growth

We introduce integrands of –type, which are, roughly speaking, of lower (upper) growth rate ) satisfying in addition for some . Then, if , we prove partial –regularity of local minimizers by the way including integrands f being controlled by some N–function and also integrands of anisotropic power growth. Moreover, we extend the known results up to a certain limit and present examples which are not covered by the standard theory. Received: 17 February 2000 / Accepted: 23 January 2001 / Published online: 4 May 2001     

Positivity of the self-diffusion matrix of interacting Brownian particles with hard core

We prove the positivity of the self-diffusion matrix of interacting Brownian particles with hard core when the dimension of the space is greater than or equal to 2. Here the self-diffusion matrix is a coefficient matrix of the diffusive limit of a tagged particle. We will do this for all activities, z>0, of Gibbs measures; in particular, for large z– the case of high density particles. A typical example of such a particle system is an infinite amount of hard core Brownian balls. Received: 22 September 1997 / Revised version: 15 January 1998     

Impact of Bursty Traffic on Queues

The impact of bursty traffic on queues is investigated in this paper. We consider a discrete-time single server queue with an infinite storage room, that releases customers at the constant rate of c customers/slot. The queue is fed by an M/G/∞ process. The M/G/∞ process can be seen as a process resulting from the superposition of infinitely many ‘sessions’: sessions become active according to a Poisson process; a station stays active for a random time, with probability distribution G, after which it becomes inactive. The number of customers entering the queue in the time-interval [t, t + 1) is then defined as the number of active sessions at time t (t = 0,1, ...) or, equivalently, as the number of busy servers at time t in an M/G/∞ queue, thereby explaining the terminology. The M/G/∞ process enjoys several attractive features: First, it can display various forms of dependencies, the extent of which being governed by the service time distribution G. The heavier the tail of G, the more bursty the M/G/∞ process. Second, this process arises naturally in teletraffic as the limiting case for the aggregation of on/off sources [27]. Third, it has been shown to be a good model for various types of network traffic, including telnet/ftp connections [37] and variable-bit-rate (VBR) video traffic [24]. Last but not least, it is amenable to queueing analysis due to its very strong structural properties. In this paper, we compute an asymptotic lower bound for the tail distribution of the queue length. This bound suggests that the queueing delays will dramatically increase as the burstiness of the M/G/∞ input process increases. More specifically, if the tail of G is heavy, implying a bursty input process, then the tail of the queue length will also be heavy. This result is in sharp contrast with the exponential decay rate of the tail distribution of the queue length in presence of ‘non-bursty’ traffic (e.g. Poisson-like traffic). This revised version was published online in August 2006 with corrections to the Cover Date.     

Interacting Fisher–Wright diffusions in a catalytic medium

We study the longtime behaviour of interacting systems in a randomly fluctuating (space–time) medium and focus on models from population genetics. There are two prototypes of spatial models in population genetics: spatial branching processes and interacting Fisher–Wright diffusions. Quite a bit is known on spatial branching processes where the local branching rate is proportional to a random environment (catalytic medium). Here we introduce a model of interacting Fisher–Wright diffusions where the local resampling rate (or genetic drift) is proportional to a catalytic medium. For a particular choice of the medium, we investigate the longtime behaviour in the case of nearest neighbour migration on the d-dimensional lattice. While in classical homogeneous systems the longtime behaviour exhibits a dichotomy along the transience/recurrence properties of the migration, now a more complicated behaviour arises. It turns out that resampling models in catalytic media show phenomena that are new even compared with branching in catalytic medium. Received: 15 November 1999 / Revised version: 16 June 2000 / Published online: 6 April 2001     

On the partition function of a directed polymer in a Gaussian random environment

 The purpose of this work is the study of the partition function of a -dimensional lattice directed polymer in a Gaussian random environment being the inverse of temperature). In the low-dimensional cases , we prove that for all , the renormalized partition function converges to 0 and the correlation of two independent configurations does not converge to 0. In the high dimensional case (), a lower tail of has been obtained for small . Furthermore, we express some thermodynamic quantities in terms of the path measure alone. Received: 8 June 2001 / Revised version: 8 February 2002 / Published online: 22 August 2002 Mathematics Subject Classification (2000): 60K37, 82D30 Key words or phrases: Directed polymer in random environment – Gaussian environment – partition function     

On the long time behavior of the stochastic heat equation

We consider the stochastic heat equation in one space dimension and compute – for a particular choice of the initial datum – the exact long time asymptotic. In the Carmona-Molchanov approach to intermittence in non stationary random media this corresponds to the identification of the sample Lyapunov exponent. Equivalently, by interpreting the solution as the partition function of a directed polymer in a random environment, we obtain a weak law of large numbers for the quenched free energy. The result agrees with the one obtained in the physical literature via the replica method. The proof is based on a representation of the solution in terms of the weakly asymmetric exclusion process. Received: 11 November 1997 / Revised version: 31 July 1998     

Stationary backward stochastic differential equations and associated partial differential equations

By replacing the final condition for backward stochastic differential equations (in short: BSDEs) by a stationarity condition on the solution process we introduce a new class of BSDEs. In a natural manner we associate to such BSDEs the periodic solution of second order partial differential equations with periodic structure. Received: 11 October 1996 / Revised version: 15 February 1999     

Stochastic oscillatory integrals with quadratic phase function and Jacobi equations

An evaluation of a stochastic oscillatory integral with quadratic phase function and analytic amplitude function is given by using solutions of Jacobi equations. The evaluation will be obtained as an application of real change of variable formulas and holomorphic prolongations of analytic functions on a real Wiener space. On the way we shall see how a Jacobi equation appears in the evaluation by using the Malliavin calculus. Received: 27 July 1998 / Revised version: 14 October 1998     

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     

A particle approximation of the solution of the Kushner–Stratonovitch equation

We construct a sequence of branching particle systems α _n convergent in measure to the solution of the Kushner–Stratonovitch equation. The algorithm based on this result can be used to solve numerically the filtering problem. We prove that the rate of convergence of the algorithm is of order n ^?. This paper is the third in a sequence, and represents the most efficient algorithm we have identified so far. Received: 4 February 1997 / Revised version: 26 October 1998