Probability Abstracts 61

1666. A SAMPLE-PATHS APPROACH TO NOISE-INDUCED SYNCHRONIZATION: STOCHASTIC RESONANCE IN A DOUBLE-WELL POTENTIAL

Nils Berglund and Barbara Gentz

Additive white noise may significantly increase the response of bistable
systems to a periodic driving signal. We consider two classes of double-well
potentials, symmetric and asymmetric, modulated periodically in time with
period $1/\eps$, where $\eps$ is a moderately (not exponentially) small
parameter. We show that the response of the system changes drastically when the
noise intensity $\sigma$ crosses a threshold value. Below the threshold, paths
are concentrated near one potential well, and have an exponentially small
probability to jump to the other well. Above the threshold, transitions between
the wells occur with probability exponentially close to 1/2 in the symmetric
case, and exponentially close to 1 in the asymmetric case. The transition zones
are localised in time near the points of minimal barrier height. We give a
mathematically rigorous description of the behaviour of individual paths, which
allows us, in particular, to determine the power-law dependence of the critical
noise intensity on $\eps$ and on the minimal barrier height, as well as the
asymptotics of the transition and non-transition probabilities.

berglund@wias-berlin.de

• This article is available from the xxx mathematics archive as math.PR/0012267.

1667. MICROSCOPIC SHAPE OF SHOCKS IN A DOMAIN GROWTH MODEL

Marton Balazs

Considering the hydrodynamical limit of some interacting particle systems
leads to hyperbolic differential equation for the conserved quantities, e.g.
the inviscid Burgers equation for the simple exclusion process. The physical
solutions of these partial differential equations develop discontinuities,
called shocks. The microscopic structure of these shocks is of much interest
and far from being well understood. We introduce a domain growth model in which
we find a stationary (in time) product measure for the model, as seen from a
defect tracer or second class particle, travelling with the shock. We also show
that under some natural assumptions valid for a wider class of domain growth
models, no other model has stationary product measure as seen from the moving
defect tracer.

balazs@math.bme.hu

• This article is available from the xxx mathematics archive as math.PR/0101124.

1668. WINTERBOTTOM CONSTRUCTION FOR FINITE RANGE FERROMAGNETIC MODELS: AN L_1 APPROACH

T. Bodineau, D. Ioffe and Y. Velenik

We provide a rigorous microscopic derivation of the thermodynamic description
of equilibrium crystal shapes in the presence of a substrate, first studied by
Winterbottom. We consider finite range ferromagnetic Ising models with pair
interactions in dimensions greater or equal to 3, and model the substrate by a
finite-range boundary magnetic field acting on the spins close to the bottom
wall of the box.

velenik@cmi.univ-mrs.fr

• This article is available from the xxx mathematics archive as math.PR/0101174.

1669. EXPLICIT CRITERIA FOR SEVERAL TYPES OF ERGODICITY

Mu-Fa Chen

The explicit criteria for several types of ergodicity of one-dimensional
diffusions or birth-death processes have been found out recently in a
surprisingly short period. One of the criteria is for exponential ergodicity of
birth-death processes. This problem has been opened for a long time in the
study of Markov chains. The survey article explains in details the idea which
leads to solve the problem just mentioned. It is interesting that the problem
is connected with several branches of mathematics. Some open problems for the
further study are also proposed.

mfchen@email.bnu.edu.cn

• This article is available from the xxx mathematics archive as math.PR/0101227.

1670. YANG-MILLS MEASURE ON COMPACT SURFACES

Thierry Levy

We construct and study the Yang-Mills measure in two dimensions. According to
the informal description given by the physicists, it is a probability measure
on the space of connections modulo gauge transformations on a principal bundle
with compact structure group. We are interested in the case where the base
space of this bundle is a compact orientable surface.
  The construction of the measure in a discrete setting, where the base space
of the fiber bundle is replaced by a graph traced on a surface, is quite well
understood thanks to the work of E. Witten. In contrast, the continuum limit of
this construction, which should allow to put a genuine manifold as base space,
still remains problematic.
  This work presents a complete and unified approach of the discrete theory and
of its continuum limit. We give a geometrically consistent definition of the
Yang-Mills measure, under the form of a random holonomy along a wide, intrinsic
and natural class of loops. This definition allows us to study combinatorial
properties of the measure, like its Markovian behaviour under the surgery of
surfaces, as well as properties specific to the continuous setting, for
example, some of its microscopic properties. In particular, we clarify the
links between the Yang-Mills measure and the white noise and show that there is
a major difference between the Abelian and semi-simple theories. We prove that
it is possible to construct a white noise using the measure as a starting point
and vice versa in the Abelian case but we show a result of asymptotic
independence in the semi-simple case which suggests that it is impossible to
extract a white noise from the measure.

thierry.levy@math.u-psud.fr

• This article is available from the xxx mathematics archive as math.PR/0101239.

1671. SHARP ESTIMATES FOR BROWNIAN NON-INTERSECTION PROBABILITIES

Greg Lawler, Oded Schramm, Wendelin Werner

This paper gives an accessible (but still technical) self-contained proof to
the fact that the intersection probabilities for planar Brownian motion are
given in terms of the intersection exponents, up to a bounded multiplicative
error, and some closely related results. While most of the results are already
known, the proofs are somewhat new, and the paper can serve as a source for the
estimates used in our paper on the analyticity of the Brownian intersection
exponents (math.PR/0005295).

wendelin.werner@math.u-psud.fr

• This article is available from the xxx mathematics archive as math.PR/0101247.

1672. EIGENVALUES, INEQUALITIES AND ERGODIC THEORY

Mu-Fa Chen

This paper surveys the main results obtained during the period 1992-1999 on
three aspects mentioned at the title. The first result is a new and general
variational formula for the lower bound of spectral gap (i.e., the first
non-trivial eigenvalue) of elliptic operators in Euclidean space, Laplacian on
Riemannian manifolds or Markov chains (\S 1). Here, a probabilistic
method-coupling method is adopted. The new formula is a dual of the classical
variational formula. The last formula is actually equivalent to Poincar\'e
inequality. To which, there are closely related logarithmic Sobolev inequality,
Nash inequality, Liggett inequality and so on. These inequalities are treated
in a unified way by using Cheeger's method which comes from Riemannian
geometry. This consists of \S 2. The results on these two aspects are mainly
completed by the author joint with F. Y. Wang. Furthermore, a diagram of the
inequalities and the traditional three types of ergodicity is presented (\S 3).
The diagram extends the ergodic theory of Markov processes. The details of the
methods used in the paper will be explained in a subsequent paper under the
same title.

mfchen@email.bnu.edu.cn

• This article is available from the xxx mathematics archive as math.PR/0101257.

1673. ON FIRST EXIT TIMES FOR HOMOGENEOUS DIFFUSION PROCESSES

N.Dokuchaev

It is given an effective upper estimate of expectation of |T_1-T_2|, where
T_1 and T_2 are the first exit times from a region for two vector diffusion
processes.

dokuchaev@pobox.spbu.ru

• This article is available from the xxx mathematics archive as math.PR/0102099.

1674. THE SHAPE THEOREM FOR THE FROG MODEL

O.S.M.Alves ; S.Yu.Popov ; F.P.Machado 

In this work we prove a shape theorem for a growing set of Simple Random
Walks (SRWs), known as frog model. The dynamics of this process is described as
follows: There are some active particles, which perform independent SRWs, and
sleeping particles, which do not move. When a sleeping particle is hit by an
active particle, it becomes active too. We prove that the set of the original
positions of all the active particles, rescaled by the elapsed time, converges
to some compact convex set. In some specific cases we are able to identify (at
least partially) this set.

fmachado@ime.usp.br

• This article is available from the xxx mathematics archive as math.PR/0102182.

1675. MIXING TIMES OF LOZENGE TILING AND CARD SHUFFLING MARKOV CHAINS

David Bruce Wilson

We show how to combine Fourier analysis with coupling arguments to bound the
mixing times of a variety of Markov chains. The mixing time is the number of
steps a Markov chain takes to approach its equilibrium distribution. One
application is to a class of Markov chains introduced by Luby, Randall, and
Sinclair to generate random tilings of regions by lozenges. For an L X L region
we bound the mixing time by O(L^4 log L), which improves on the previous bound
of O(L^7), and we show the new bound to be essentially tight. In another
application we resolve a few questions raised by Diaconis and Saloff-Coste, by
lower bounding the mixing time of various card-shuffling Markov chains. Our
lower bounds are within a constant factor of their upper bounds. When we use
our methods to modify a path-coupling analysis of Bubley and Dyer, we obtain an
O(n^3 log n) upper bound on the mixing time of the Karzanov-Khachiyan Markov
chain for linear extensions.

dbwilson@microsoft.com

• This article is available from the xxx mathematics archive as math.PR/0102193.

1676. ANCHORED EXPANSION AND RANDOM WALK

Balint Virag

This paper studies anchored expansion, a non-uniform version of the strong
isoperimetric inequality. We show that every graph with i-anchored expansion
contains a subgraph with isoperimetric (Cheeger) constant at least i. We prove
a conjecture by Benjamini, Lyons and Schramm (1999) that in such graphs the
random walk escapes with a positive lim inf speed. We also show that anchored
expansion implies a heat-kernel decay bound of order exp(-c n^1/3).

balint@math.mit.edu

• This article is available from the xxx mathematics archive as math.PR/0102199.

1677. FAST GRAPHS FOR THE RANDOM WALKER

Balint Virag

Consider the time T_oz when the random walk on a weighted graph started at
the vertex o first hits the vertex set z. We present lower bounds for T_oz in
terms of the volume of z and the graph distance between o and z. The bounds are
for expected value and large deviations, and are asymptotically sharp. We
deduce rate of escape results for random walks on infinite graphs of
exponential or polynomial growth, and resolve a conjecture of Benjamini and
Peres.

balint@math.mit.edu

• This article is available from the xxx mathematics archive as math.PR/0102200.

1678. ON DECIDING STABILITY OF CONSTRAINED HOMOGENEOUS RANDOM WALKS AND QUEUEING SYSTEMS

David Gamarnik

We investigate stability  of some  scheduling policies in  
queueing systems. To the day no algorithmic characterization 
exists for checking stability of a given policy in a given 
queueing system. In this paper we propose  a certain 
\emph{generalized priority} policy and prove that the 
stability of this policy is algorithmically undecidable. We 
also prove that stability of a homogeneous random walk in 
${\cal Z}_+^d$ is undecidable. To the best of our knowledge 
this is the first undecidability result in the area of 
stability of queueing systems and random walks in 
${\cal Z}_+^d$. We conjecture that  stability of other 
common policies like First-In-First-Out and priority 
policy is also an undecidable problem.

gamarnik@watson.ibm.com

• To see a preprint or other information provided by the author click here.

1679. ON ARONSON'S UPPER BOUNDS FOR HEAT KERNELS

Richard F. Bass

Let L be a uniformly elliptic operator in divergence
form on R^d and let p(t,x,y) be the fundamental solution 
to the heat equation for L. We give a new proof of 
Aronson's upper bound: 
p(t,x,y)\leq c_1t^{-d/2}\exp(-c_2|x-y|^2/t)
The proof is partially probabilistic.

bass@math.uconn.edu

• To see a preprint or other information provided by the author click here.

1680. PINCHING AND TWISTING MARKOV PROCESSES

Steven N. Evans and Richard B. Sowers

We develop a technique for ``partially collapsing'' 
one Markov processes to produce another.  The state space
of the new Markov process is obtained by a pinching 
operation that identifies points of the original state 
space via an equivalence relation.  
To ensure that the new process is Markovian we need to
introduce a randomised twist according to an appropriate 
probability kernel. Informally, this twist randomises 
over the uncollapsed region of the state space when the 
process leaves the collapsed region.  The Markovianity of 
the new process is ensured by suitable intertwining 
relations between the semigroup of the original process and
the pinching and twising operations. 
We construct the new Markov process, identify its resolvent
and transition function and, under some natural assumptions,
exhibit a core for its generator.  We also investigate
its excursion decomposition. We apply our theory to a 
number of examples, including Walsh's spider and a process 
similar to one introduced by Sowers in studying stochastic 
averaging of PDE.

evans@stat.berkeley.edu   r-sowers@math.uiuc.edu

• To see a preprint or other information provided by the author click here.
• Or here.
• Or here.

1681. LIMITS OF ON/OFF HIERARCHICAL PRODUCT MODELS FOR DATA TRANSMISSIONS

Sidney Resnick and Gennady Samorodnitsky

A hierarchical product model seeks to model network 
traffic as a product of independent on/off processes. 
Previous studies have assumed a Markovian structure for 
component processes amounting to assuming that exponential
distributions govern on and off periods but this is not in
good agreement with traffic measurements. However, if the
number of factor processes grows and input rates 
are stabilized by allowing the on period distribution to 
change suitably, a limiting on/of process can be 
obtained which has exponentially distributed on 
periods and whose off periods are equal in 
distribution to the busy period of an M/G/ queue. 
We give a fairly complete study of the possible 
limits of the product process as the number of 
factors grow and offer various characterizations 
of the approximating processes. We also study 
the dependence structure of the approximations.

sid@orie.cornell.edu     gennady@orie.cornell.edu

• To see a preprint or other information provided by the author click here.

1682. A CONDITIONAL ENTROPY POWER INEQUALITY FOR DEPENDENT VARIABLES

Oliver Johnson

We provide a condition under which a version of Shannon's 
Entropy Power Inequality will hold for dependent variables. 
We provide information inequalities extending those found 
in the independent case. 

otj1000@cam.ac.uk

• To see a preprint or other information provided by the author click here.

1683. ON THE EXPLOSION OF THE L0CAL TIMES OF BROWNIAN SHEET ALONG LINES

Davar Khoshnevisan, Pal Revesz and Zhan Shi

One can view a 2-parameter Brownian sheet
${ W(s,t); s,t  \ge 0}$  as a stream of interacting
Brownian motions ${ W(s,.); s \le 0 }$. Given this
view point, we aim to continue the analysis of
Walsh (1978) on the local times of the stream
$W(s,.)$, near time $s=0$. Oue main result is a kind of maximal
inequality that, in particular, verifies the following
conjecture of Khoshnevisan (1995): as s goes to 0,
the local times of W(s,.) explode almost surely.
Two other applications of this maximal inequality are presented,
one to a capacity estimate in classical Wiener space, and
one to a uniform ratio ergodic theorem  in Wiener space. The latter
readily implies a quasi-sure ergodic theorem. We also
present a sharp Holder condition
for the local times of the mentioned Brownian streams
that refines earlier results of (Lacey 1990; R\'ev\'esz 1985;
Walsh 1978).

davar@math.utah.edu

• To see a preprint or other information provided by the author click here.

1684. DIFFERENT TREES HAVE DISTINCT PHYLOGENETIC INVARIANTS

Steven N. Evans and Xiaowen Zhou

The method of invariants is an approach to the problem of 
reconstructing the phylogenetic tree of a collection of $m$
taxa using nucleotide sequence data.  Models for the 
collection of probabilities of the $4^m$ possible vectors 
of bases at a given site will have unknown parameters that 
describe the random mechanism by which substitution
occurs along the branches of a possible phylogenetic tree.
An invariant is a polynomial in these probabilities that, 
for a given phylogeny, is zero for all choices of the 
substitution mechanism parameters.  We show for a widely 
used, general class of substitution mechanisms that given 
two different trees there is always a polynomial that is an
invariant for one tree but not an invariant for the other. 
Thus estimates of invariants can always be used to 
discriminate between competing phylogenies.

evans@stat.berkeley.edu  zhou@math.ubc.ca

• To see a preprint or other information provided by the author click here.
• Or here.

1685. STRONG CLUMPING OF SUPER-BROWNIAN MOTION IN A STABLE CATALYTIC MEDIUM

Donald A. Dawson, Klaus Fleischmann and Peter Moerters

A typical feature of the long time behaviour of continuous
super-Brownian motion in a stable catalytic medium is the 
development of large mass clumps or clusters at spatially 
rare sites. We describe this phenomenon by means of a 
functional limit law under renormalisation. The limiting 
process is a Poisson point field of mass clumps with no 
spatial motion component and with infinite variance. The 
mass of each cluster evolves independently according to a 
continuous process trapped at mass zero, which we describe
explicitly by means of a Brownian snake construction in a
random medium. We also determine the survival probability 
and asymptotic size of the clumps.

peter@mathematik.uni-kl.de

• To see a preprint or other information provided by the author click here.
• Or here.

1686. STABLE PROCESSES HAVE THORNS

Krzysztof Burdzy and Tadeusz Kulczycki

Symmetric stable processes have thorn points similar to cone
points on Brownian paths. We give an integral criterion
for those functions which describe thorn shapes
for which thorn points exist. For example, thorn
points exist if the thorn width r units from its tip
is equal to r |\log r|^\beta and \beta is greater than
-1/(d + \alpha - 1). Here d is the dimension of the
space and \alpha is the index of the stable process.

burdzy@math.washington.edu   tkulczyc@kac.im.pwr.wroc.pl

• To see a preprint or other information provided by the author click here.

1687. RUSSIAN OPTIONS FOR A DIFUSSION WITH NEGATIVE JUMPS

Ernesto Mordecki and Walter Moreira

Closed solutions to the problem of pricing a Russian option
when the underlying process is a diffusion with negative
jumps are obtained. More precisely, the underlying process
is assumed to have the form of a Wiener process with drift
and negative mixed--exponentially distributed jumps driven
by a Poisson process. This results generalize those of
Shepp and Shiryaev (1993) for the Wiener process and
Gerber, Michaud and Shiu (1995) for pure--jumps process.

mordecki@cmat.edu.uy  walterm@cmat.edu.uy

• To see a preprint or other information provided by the author click here.

1688. IMPROVED INCLUSION-EXCLUSION IDENTITIES AND BONFERRONI INEQUALITIES WITH APPLICATIONS TO RELIABILITY ANALYSIS OF COHERENT SYSTEMS

Klaus Dohmen

Many problems in combinatorics, number theory, probability 
theory, reliability theory and statistics can be solved by 
applying a unifying method, which is known as the principle of 
inclusion-exclusion. The principle of inclusion-exclusion
expresses the indicator function of a union of finitely
many sets or events as an alternating sum of indicator 
functions of their intersections. The associated truncation 
inequalities are known to the statistical community as 
Bonferroni inequalities, although they were first discovered
by Ch. Jordan in 1927. The present monograph, which is the 
author's Habilitation Thesis, deals with several 
improvements of the classical Bonferroni inequalities such 
that (i) the new inequalities are sharper than their 
classical counterparts and (ii) fewer terms need to be 
evaluated when computing bounds. The results are stated 
within the general theory of abstract tubes, which recently 
has been initiated in a seminal paper by Daniel Naiman and 
Henry Wynn. The results are applied to network and system 
reliability analysis, and in this way several known results
are rediscovered in a concise way. 
The thesis is organized as follows: Chapter 1 serves as an 
introduction and overview. In Chapter 2 we introduce some 
terminology on graphs and partially ordered sets that will 
be repeatedly used in later chapters. In Chapter 3 we bring 
in some relevant structures and establish several 
improvements of the classical inclusion-exclusion identity. 
Several results from the literature such as the semilattice
sieve of Narushima (1974, 1982) and the tree sieve of Naiman
and Wynn (1992) are rediscovered in a unified way. In 
Chapter 4 we give a detailed survey of the recent theory of 
abstract tubes, which was initiated by Naiman and Wynn (1992,
1997), and establish some improved Bonferroni inequalities
based on the results of this theory. The chapter concludes
with a new Bonferroni-Galambos type inequality based on
chordal graphs, itself subsuming several other inequalities.
In Chapter 5, the results are applied to reliability 
analysis of coherent systems such as communication networks,
k-out-of-n systems and consecutive k-out-of-n systems. Among 
other things we rediscover Shier's recursive algorithm and 
semilattice expression for the reliability of a coherent 
system (1988, 1991) and establish some related Bonferroni
inequalities. We then turn out attention to reliability 
covering problems and identify a comprehensive class of 
hypergraphs for which coverage probability can be computed 
in polynomial time. In Chapter 6, which is devoted to 
miscellaneous topics, we give a new and simplified proof of
Whitney's broken circuit theorem on the chromatic polynomial 
of a graph and establish some new Bonferroni inequalities on
that polynomial. The results are then extended to a new two-
variable polynomial that generalizes both the chromatic 
polynomial and the independence polynomial of a graph. 
We finally draw similar conclusions for the Tutte polynomial,
the characteristic polynomial and the beta invariant of a 
matroid, the Euler characteristic of an abstract simplicial
complex and the Möbius function of a partially ordered set.

dohmen@informatik.unibw-muenchen.de

• To see a preprint or other information provided by the author click here.

1689. AN INFORMATION-THEORETIC CENTRAL LIMIT THEOREM FOR FINITELY SUSCEPTIBLE FKG SYSTEMS

Oliver Johnson

We adapt arguments concerning entropy-theoretic convergence
to the case of FKG random variables. FKG systems are chosen
since their dependence structure is controlled through 
covariance alone, though in the sequel we use many of
the same arguments for weakly dependent random variables. 
As in previous work of Barron and Johnson, we consider 
random variables perturbed by small normals, since the FKG 
property gives us control of the resulting densities. We 
need to impose a finite susceptibility condition -- that is, 
the covariance of one random variable and the sum of all 
the random variables should remain finite.

otj1000@cam.ac.uk

• To see a preprint or other information provided by the author click here.

1690. BROWNIAN INTERSECTION LOCAL TIMES: UPPER TAIL ASYMPTOTICS AND THICK POINTS

Wolfgang Koenig and Peter Moerters

We equip the intersection of $p$ independent Brownian 
paths in $\R^d$, $d\ge 2$, with the natural measure 
$\ell$ defined by projecting the intersection local 
time measure via one of the Brownian motions onto the 
set of intersection points. Given a bounded domain 
$U\subset\R^d$ we show that, as $a\uparrow\infty$, 
the probability of the event $\{\ell(U)>a\}$ decays 
with an exponential rate of $a^{1/p}\theta$, where 
$\theta$ is described in terms of a variational problem.
In the important special case when $U$ is the unit ball 
in $\R^3$ and $p=2$, we characterize $\theta$ in terms 
of an ordinary differential equation. We apply our 
results to the problem of finding the Hausdorff 
dimension spectrum for the thick points of the 
intersection of two independent Brownian paths in $\R^3$.

koenig@math.tu-berlin.de   peter@mathematik.uni-kl.de

• To see a preprint or other information provided by the author click here.
• Or here.