Probability Abstracts 27
This document contains abstracts 489-519.
They have been mailed on June 23, 1995.
Click here to see the
list of all abstract titles.
489. A CRITICAL PHENOMENON IN A BROADCAST PROCESS
William Evans, Claire Kenyon, Yuval Peres and Leonard Schulman
Suppose that random spins (+1 or -1) are assigned to the
vertices of an infinite rooted tree T in a Markovian way,
so that along each edge the spin is flipped with a fixed probability,
denoted (1-u)/2.
In the usual Ising model, one conditions on the spins at the
boundary of a finite subtree being all 1, and studies whether
this has a lasting effect on the spin at the root, as the subtree
tends to all of T. (The flipping probability is a function of temperature.)
Lyons (1989, 1990) showed that the critical value of u in the Ising model
equals the critical percolation probability, which is the reciprocal of the
``branching number'' of T. From an information theory perspective,
it is natural to ask whether the spin at the root can be reconstructed,
with probability bounded away from 1/2, from the spins on the (free)
boundaries of large subtrees. We show that on any tree, the critical parameter
u for this reconstruction problem is the square root of the critical
percolation probability.
peres@stat.berkeley.edu (hard copy available) kenyon@cs.berkeley.edu
490. TAIL ESTIMATES FOR ONE-DIMENSIONAL RANDOM WALK IN RANDOM ENVIRONMENT
Amir Dembo, Yuval Peres and Ofer Zeitouni
Suppose that the integers are assigned i.i.d. random variables ${p_x}$
which serve as an environment. This environment defines a walk ${X_k}$
(called a RWRE) which, when at $x$, moves one step to the right with
probability $p_x$, and to the left with probability $1-p_x$.
Solomon (1975) determined the almost-sure asymptotic speed of an RWRE.
For certain environment distributions where the drifts $2p_x-1$ can
take both positive and negative values, we show that the chance of the
RWRE deviating below this speed has a polynomial rate of decay, and
determine the exponent in this power law; for environments which allow
only positive and zero drifts, we show that these large-deviation
probabilities decay like $\exp(-C n^{1/3})$. This differs sharply from
the rates derived by Greven and den-Hollander (1994) for large deviation
probabilities conditioned on the environment.
dembo@ee.technion.ac.il peres@stat.berkeley.edu zeitouni@ee.technion.ac.il
491. IMPLICIT SCHEME FOR STOCHASTIC PARABOLIC PARTIAL
DIFFERENTIAL EQUATIONS DRIVEN BY SPACE-TIME WHITE NOISE
Istvan Gy\"ongy and David Nualart
We extend Rothe's method of solving linear parabolic PDEs to the
case of nonlinear SPDEs driven by space-time white noise.
When the nonlinear terms are
Lipschtiz functions we prove almost sure convergence of
the approximations uniformly in time and
space. When the nonlinear drift term is only measurable
we obtain this convergence in probability,
by using Malliavin calculus.
david@porthos.bio.ub.es
492. LARGE DEVIATIONS FOR PERFORMANCE ANALYSIS:
QUEUES, COMMUNICATION, AND COMPUTING
Adam Shwartz and Alan Weiss
The book provides an introduction to the theory of large deviations,
concentrating on continuous time discrete state Markov processes. Applications
we develop cover large areas of the theory of communication networks:
circuit-switched transmission, packet transmission, multiple access channels,
and the M/M/1 queue. Issues of performance and computation are covered also.
The level is suitable for advanced undergraduate and graduate students in
engineering and applied mathematics. The book is also a reference resource for
mathematicians, researchers, and engineers.
For a table of contents, synopsis, suggestion for courses, and ordering info:
see the first "url" below.
The table of contents, Chapters 0 and 1 are available (ftp) there as the
Unix-compressed PostScript file bookintro.ps.Z . You can also ftp
directly using the second "url" below.
adam@ee.technion.ac.il
493. SURVIVAL OF DISCRETE TIME GROWTH MODELS, WITH APPLICATIONS
TO ORIENTED PERCOLATION
Thomas M. Liggett
We prove survival for a class of discrete time Markov processes whose states are
finite sets of integers. As applications, we obtain upper bounds for the
critical values of various two dimensional oriented percolation models. The
technique of proof is generally that used to prove that the critical value
of the basic one dimensional contact process is at most 2. However, the fact
that our processes evolve in discrete time requires that we make substantial
changes in the way this technique is used. When applied to oriented percolation
on the two dimensional square lattice, our result gives the following bounds:
$p_c\leq \frac 23$ for bond percloation, and $p_c\leq 3/4$ for site percolation.
tml@math.ucla.edu (To appear in the Annals of Applied Probability; hard copy
available.)
494. MULTIPLE TRANSITION POINTS FOR THE CONTACT PROCESS ON THE BINARY TREE
Thomas M. Liggett
The contact process on $Z^d$ is known to have only two fundamental types of
behavior: survival and extinction. Recently, Pemantle discovered that the
phase structure for the contact process on a tree can be more complex. There
are three possible types of behavior: strong survival, weak survival, and
extinction. He proved that all three occur on homogeneous trees in which
each vertex has $d+1$ neighbors, provided that $d\geq 3$, but he left open
the boundary case $d=2$. In this paper, we prove that weak survival does
occur for appropriate values of the parameter in this case as well. In doing so, we extend and
develop techniques for obtaining upper and lower bounds for the critical
values associated with strong and weak survival of the contact process on
more general graphs.
tml@math.ucla.edu (Hard copy available.)
495. CUTPOINTS AND EXCHANGEABLE EVENTS FOR RANDOM WALKS
Nicholas James and Yuval Peres
For a transient Markov chain $(S_{n})$ call $S_{n}$ a CUTPOINT
if there is no possible transition from $S_i$ to $S_j$ for $i<n<j$.
We show that a transient random walk of bounded stepsize on an integer
lattice has infinitely many cutpoints almost surely, and furthermore
these may be found on appropriate "cut-spheres".
We also modify an argument of Lawler (1991) to show the existence of
cutpoints for any symmetric random walk of bounded stepsize on a finitely
generated group, unless the group has polynomial growth of small degree.
Considering an event to be a set of trajectories, call an event
EXCHANGEABLE if it is invariant under finite permutations. Being
transient, the walk visits each state finitely often, and this gives
a collection of random variables called the OCCUPATION NUMBERS which
are all measurable with respect to the exchangeable $\sigma$-field.
If the walk has cutpoints we show the occupation numbers
generate the exchangeable $\sigma$-field, which answers a question
posed by Kaimanovich and Vershik.
peres@stat.Berkeley.EDU
496. ON THE EXISTENCE AND APPLICATION OF CONTINUOUS-TIME
THRESHOLD AUTOREGRESSIONS OF ORDER TWO
P. J. Brockwell and R. J. Williams
A continuous-time threshold autoregressive process of order two (CTAR(2))
is constructed as the first component of the unique (in law) weak solution
of a stochastic differential equation. The Cameron-Martin-Girsanov
formula and a random time-change are used to overcome the difficulties
associated with possible discontinuities and degeneracies in the
coefficients of the stochastic differential equation. A sequence of
approximating processes which are well-suited to numerical calculations is
shown to converge in distribution to a solution of this equation, provided
the initial state vector has finite second moments. The approximating
sequence is used to fit a CTAR(2) model to percentage relative daily
changes in the Australian All Ordinaries Index of share prices by
maximization of the ``Gaussian likelihood''. The advantages of non-linear
relative to linear time series models are briefly discussed and illustrated
by means of the forecasting performance of the model fitted to the All
Ordinaries Index.
williams@math.ucsd.edu (Hard copy or postscript file available)
497. THE MARKET MODEL OF INTEREST RATES DYNAMICS
Alan Brace, Dariusz Gatarek and Marek Musiela
A class of term structure models with volatility of lognormal
type is analysed in the general HJM framework, leading to stochastic partial
differential equations. The
corresponding forward rates do not explode, are positive and
mean reverting. Pricing of caps and floors is consistent with
the market practice of using the Black futures formula.
Swaptions are priced with closed formulae, that reduce (with an extra
assumption) to exactly the Black swaption formulae when yield and volatility
are flat. A two-factor version of the model is calibrated to the UK market price
of caps and swaptions and to the historically estimated correlation between the
forward rates.
gatarek@solution.maths.unsw.edu.au (hard copy available)
498. HOMOGENIZATION ON NESTED FRACTALS
Takashi Kumagai and Shigeo Kusuoka
We study the homogenization problem on nested fractals. Let $X_t$ be the
continuous time Markov chain on the pre-nested fractal given by putting
i.i.d. random resistors on each cells. It is proved that under some
conditions, $\alpha^{-n} X_{t_E^n t}$ converges in law to a constant
time change of the Brownian motion on the fractal as $n \to \infty$, where
$\alpha$ is the contraction rate and $t_E$ is a time scale constant. As the
Brownian motion on fractals is not a semi-martingale, we need a different
approach from the well-developed martingale method.
kumagai@math.nagoya-u.ac.jp
499. DEVIATION INEQUALITIES FOR CONTINUOUS MARTINGALES
Davar Khoshnevisan
This is a short note containing
upper and lower Gaussian estimates for
the tails of a continuous martingale, M_t,
which possesses a finite moment generating
function. The key idea here is in the lower
bound in that in order to be able to get
the "correct" estimates, one needs to compare
M_t appropriately to its quadratic variation,
<M>_t.
davar@math.utah.edu (TeX file available)
500. MULTIWAY TREES OF MAXIMUM AND MINIMUM PROBABILITY UNDER THE
RANDOM PERMUTATION MODEL
Robert P. Dobrow and James Allen Fill
Multiway trees, also known as $m$-ary search trees,
are data structures generalizing binary search trees.
A common probability model for analyzing the behavior
of these structures is the random permutation model.
The probability mass function $Q$ on the set of
$m$-ary search trees under the random permutation
model is the distribution induced by sequentially
inserting the records of a uniformly random permutation
into an initially empty $m$-ary search tree. We study
some basic properties of $Q$. In particular, we determine
exact and asymptotic expressions for the maximum and
minimum values of $Q$ and identify and count the trees
achieving those values.
dobrow@cam.nist.gov
501. THE NUMBER OF $m$-ARY SEARCH TREES ON $n$ KEYS
James Allen Fill and Robert P. Dobrow
Problems associated with $m$-ary trees have been studied
by computer scientists and combinatorialists. It is well
known that a simple generalization of the Catalan numbers
counts the number of $m$-ary trees on $n$ nodes. In this
paper we consider $\tau_{m,n}$, the number of $m$-ary trees
on {\em $n$ keys}, a quantity that arises in studying the space
of $m$-ary search trees under the uniform probability model.
We prove an exact formula for $\tau_{m,n}$, both by
analytic and combinatorial means. We use uniform local
approximations for sums of i.i.d. random variables to
study the asymptotic development of $\tau_{m,n}$ for fixed
$m$ as $n \rightarrow \infty$.
dobrow@cam.nist.gov
502. ON THE ULITIMATE VALUE OF LOCAL TIME OF ONE-DIMENSIONAL
SUPER-BROWNIAN MOTION
Ingemar Kaj and Paavo Salminen
We study the random field of local time picked up over the entire life of a
super-Brownian motion on the real line. The finite dimensional distributions
of the field are characterized via their Laplace transforms by unique solutions
of certain boundary-value differential equations. In some cases the one-
dimensional distributions can be found explicitly, giving some insight into how
super-Brownian motion behaves before extinction or local extinction.
ingemar.kaj@math.uu.se
503. EXPONENTIALLY FAST RELAXATION OF STOCHASTIC ISING
MODELS ON THE LATTICE SIERPINSKI GASKET
Nobuo Yoshida
Ferromagnetic Ising models on the lattice Sierpinski gasket are
considered. We first show that the Gibbs state has an exponentially
strong mixing property at any temperature. Using this, we then prove that
a stochastic Ising model with attractive flip rate relaxes to equilibrium
exponentially fast. This in particular implies the existence of the
spectral gap.
nobuo@kusm.kyoto-u.ac.jp
504. LEVY-GROMOV"S ISOPERIMETRIC INEQUALITY FOR AN INFINITE
DIMENSIONAL DIFFUSION GENERATOR
D. Bakry and M. Ledoux
We establish, by simple semigroup arguments, a
L\'evy-Gromov isoperimetric inequality for the invariant measure
of an infinite dimensional diffusion generator of positive curvature
with isoperimetric model the Gaussian measure. This produces in particular
a new proof of the Gaussian isoperimetric inequality.
The distributions of Lipschitz functions actually appear
as contractions of the canonical Gaussian measure. These isoperimetric
inequalities strengthen furthermore the classical logarithmic Sobolev
inequalities in this context. A local version
for the heat kernel measure is also proved, which may then be extended
into an isoperimetric inequality for the Wiener measure on the paths of a
Riemannian manifold with Ricci curvature bounded below.
ledoux@cict.fr hard copy available
505. A CRITICAL CASE FOR BROWNIAN SLOW POINTS
Richard F. Bass and Krzysztof Burdzy
Let $X_t$ be a Brownian motion and let $S(c)$ be the set of
reals $r\geq 0$ such that $|X_{r+t}-X_r|\leq c\sqrt t$, $ 0\leq t\leq h$,
for some $h = h(r) >0$. It is known that $S(c)$ is empty if $c<1$
and nonempty if $c>1$, a.s. In this paper we prove that $S(1)$ is empty a.s.
bass@math.washington.edu (plain Tex file available)
- To see some information provided by the author
click here.
506. MCKEAN-VLASOV LIMIT FOR INTERACTING RANDOM PROCESSES
IN RANDOM MEDIA
Paolo Dai Pra and Frank den Hollander
We apply large deviation theory to particle systems with a random
mean-field interaction in the McKean-Vlasov limit. In particular,
we describe large deviations and normal fluctuations around the
McKean-Vlasov equation. The randomness in the interaction gives rise
to new phenomena, which are illustrated for the Kuramoto-model (random
oscillators) and the Curie-Weiss model (random magnets).
daipra@pdmat1.unipd.it, denholla@sci.kun.nl
(LaTeX-file and hard copy available)
507. TWO PROBLEMS ABOUT RANDOM WALK IN A RANDOM FIELD OF TRAPS
F. den Hollander, M.V. Menshikov and S.E. Volkov
This paper is about simple random walk on $Z^d (d \geq 3)$ in a
random field of traps whose density tends to zero at infinity.
We distinguish between the quenched problem (when the traps are
fixed) and the annealed problem (when the traps are updated
each unit of time). Our goal is not only to find a criterion for
zero vs. positive probability of survival, but also to show three
different methods that can be applied in this area. These methods
are based on Lyapunov functions, capacity resp. mean hitting time.
denholla@sci.kun.nl, menshikov@llrs.math.msu.su, volkov@llrd.math.msu.su
(LaTeX-file and hard copy available)
508. CENTRAL LIMIT THEOREM FOR THE EDWARDS MODEL
R. van der Hofstad, F. den Hollander, W. K\"onig
The Edwards model in one dimension is a transformed path measure
for standard Brownian motion discouraging self-intersections. We
prove a central limit theorem for the endpoint of the path, extending
a law of large numbers proved by Westwater (1984). The scaled variance
is characterized in terms of the largest eigenvalue of a one-parameter
family of differential operators, introduced and analyzed in van der
Hofstad and den Hollander (1995). Interestingly, the scaled variance
turns out to be independent of the strength of self-repellence and
to be strictly smaller than one.
hofstad@math.ruu.nl, denholla@sci.kun.nl, koenig@sci.kun.nl
(LaTeX-file and hard copy available)
509. A MULTICLASS CLOSED QUEUEING NETWORK WITH UNCONVENTIONAL HEAVY
TRAFFIC BEHAVIOR
J. M. Harrison and R. J. Williams
We consider a multiclass closed queueing network model analogous to the open
network models of Rybko-Stolyar and Lu-Kumar. The closed network has two
single-server stations and a fixed customer population of size $n$.
Customers are routed in cyclic fashion through four distinct classes, two of
which are served at each station, and each server uses a preemptive-resume
priority discipline. The service time distribution for each
customer class is exponential, and attention is focused on
the critical case where all four classes have the same mean service time.
Letting $n$ approach infinity, we prove a heavy traffic limit
theorem that is unconventional in three regards. First, in our heavy traffic
scaling of both queue length processes and cumulative idleness processes, time
is compressed by a factor of $n$ rather than the factor of $n^2$ occurring in
conventional theory. Second, the spatial scaling applied to some components of
the queue length and idleness processes is that associated with the central
limit theorem, but the scaling applied to other components is that associated
with the law of large numbers. Thus, in the language of queueing theory, our
heavy traffic limit theorem involves a mixture of Brownian scaling and fluid
scaling. Finally, the limit process that we obtain is not an ordinary
reflected Brownian motion, as in conventional heavy traffic
theorems, although it is related to or derived from Brownian
motion.
williams@math.ucsd.edu (postscript file or hard copy available)
510. THE DIMENSION OF THE FRONTIER OF PLANAR BROWNIAN MOTION
Gregory F. Lawler
Let $B$ be a two dimensional Brownian motion and let the frontier
of $B[0,1]$ be defined as the set of all points in $B[0,1]$ that
are in the closure of the unbounded connected compoent of its
complement. We prove that the Hausdorff dimension of the frontier
equals $2(1 - \alpha)$ where $\alpha$ is an exponent for Brownian
motion called the two-sided disconnection exponent. In particular,
using an estimate on $\alpha$ due to Werner, the Hausdorff
dimension is greater than $1.012$.
jose@math.duke.edu
- To see some information provided by the author
click here.
511. NONINTERSECTING PLANAR BROWNIAN MOITONS
Gregory F. Lawler
Let $B^1,B^2$ be independent Brownian motions in $R^2$ starting
at distinct points on the unit circle. Let $T_r^j$ be the first
time that the $j$th Brownain motion reaches distance $r$ and
let $D_r$ be the event
\[ D_r = \{B^1[0,T_{e^r}^1] \cap B^2[0,T_{e^r}^2] = \emptyset \} . \]
We construct a measure on pairs of paths by considering the limit
of the measure induced by Brownian motions conditioned on the event
$D_r$. This gives a measure on pairs of paths starting at the
origin conditioned so that their paths do not intersect.
jose@math.duke.edu
- To see some information provided by the author
click here.
512. UNIFORM LARGE AND MODERATE DEVIATIONS FOR FUNCTIONAL EMPIRICAL
PROCESSES
Amir Dembo and Tim Zajic
For $\{ X_i \}_{i \geq 1}$ a sequence of i.i.d. random variables
taking values in a Polish space $\Sigma$ with distribution $\mu$,
we obtain large and moderate deviation principles for the processes
$\{ n^{-1} \sum_{i=1}^{[nt]} \delta_{X_i} ; t \geq 0 \}_{n \geq 1}$
and $\{ n^{-1/2} \sum_{i=1}^{[nt]} (\delta_{X_i} - \mu) ; t \geq 0
\}_{n \geq 1}$, respectively. Given a class of bounded functions
$\cal F$ on $\Sigma$, we then consider the above processes as taking
values in the Banach space of bounded functionals over $\cal F$ and
obtain the corresponding (uniform over $\cal F$) large and moderate
deviation principles. Among the corollaries considered are functional
laws of the iterated logarithm.
dembo@ee.technion.ac.il (LaTeX and Postscript files available)
513. ON THE SECOND BOREL-CANTELLI LEMMA FOR STRONGLY MIXING
SEQUENCES OF EVENTS
Dirk Tasche
Assume a given sequence of events to be strongly mixing at a polynomial
or exponential rate. We show that the conclusion of the Second
Borel-Cantelli Lemma holds if the series of the probabilities of
the events diverges at a certain rate depending on the mixing rate
of the events. An application to necessary moment conditions for the
Strong Law of Large Numbers is given.
dt@math.tu-berlin.de (LaTeX file available)
514. QUITE WEAK BERNOULLI WITH EXPONENTIAL RATE AND PERCOLATION
FOR RANDOM FIELDS
Robert Burton and Jeffrey Steif
We show that certain random fields
are Quite Weak Bernoulli with Exponential Rate using ideas from percolation.
We also show that this type of mixing condition implies in
general a central limit theorem.
burton@math.orst.edu steif@math.chalmers.se
515. THE VARIATIONAL PRINCIPLE FOR GIBBS STATES FAILS ON TREES
Robert Burton, Charles Pfister and Jeffrey Steif
We show how the variational principle for Gibbs States (which
says that for the $d$--dimensional cubic lattice,
the set of translation invariant Gibbs States is the same as the set
of translation invariant measures which maximize entropy minus energy
and moreover that this quantity corresponds to the pressure) fails
for nearest neighbor finite state statistical mechanical systems on the
homogeneous 3--ary tree. Given an interaction there is a
unique measure $\mu$ maximizing entropy minus energy, and we give necessary and
sufficient conditions so that it is a Gibbs State for that interaction, and
that the maximum is equal to the pressure.
In the case of a 2--state system, these conditions define
a 2--dimensional manifold of the natural 3--dimensional
parameter space of interactions, so that
generically in the interactions the entropy minus energy for $\mu$ is strictly
less than the pressure and $\mu$ is not a Gibbs State (for those parameter
values).
burton@math.orst.edu CPFISTER@eldpa.epfl.ch steif@math.chalmers.se
516. WEAK BERNOULLI IN ONE AND HIGHER DIMENSIONS
Robert Burton and Jeffrey Steif
We propose a notion of Weak Bernoulli in all dimensions which
generalizes the usual definition in 1--dimension. The key idea is the concept
of a ``coupling surface''. We relate this
notion to previously studied properties and discuss a number of possible
variants in 1--dimension. We also show that the Ising Model, at
low temperature, is Weak Bernoulli with an explicit description of the
coupling surface.
burton@math.orst.edu steif@math.chalmers.se
517. ON THE CONTINUITY OF THE CRITICAL VALUE FOR LONG RANGE PERCOLATION
IN THE EXPONENTIAL CASE
Ronald Meester and Jeffrey Steif
We show that for a long range percolation model with exponentially
decaying connections,
the limit of critical values of any sequence of long
range percolation models approaching the original model from below is the
critical value for the original long range percolation model. As an interesting
corollary, this implies that
if a long range percolation model with exponential connections
is supercritical, then it still percolates even if all long bonds are removed.
We also show that the percolation probability is continuous (in a certain
sense) in the supercritical regime for long range percolation models with
exponential connections.
meester@math.ruu.nl steif@math.chalmers.se
518. CONSISTENT ESTIMATION OF JOINT DISTRIBUTIONS FOR SUFFICIENTLY
MIXING RANDOM FIELDS
Jeffrey Steif
The joint distribution of a $d$-dimensional
random field restricted to a box of size
$k$ can be estimated by looking at a realization in a box of size
$n > > k$ and computing the empirical distribution. This is done by
sliding a box of size $k$ around in the box of size $n$ and
computing frequencies. We show that when $k=k(n)$ grows as a
function of $n$, then the total variation distance between this
empirical distribution and the true distribution goes to 0 a.s. as $n\to\infty$
provided $k(n)^d\le (\log n^d)/(H+\e)$ (where $H$ is the entropy of the
random field) and providing the random field satisfies a condition called Quite
Weak Bernoulli with Exponential Rate. This class of processes, studied
previously,
includes the plus state for the Ising Model at both sufficiently low and
high temperatures. Marton and Shields have proved such results
in 1 dimension and this paper is an attempt to extend their results to
some extent to higher dimensions.
steif@math.chalmers.se
519. A PHASE TRANSITION SPEED ESTIMATE IN STEFAN PROBLEM
Weian Zheng
We give an estimate to the time needed for a phase transition
to be completed in Stefan problem. Our method is to compare the
density of diffusion process
associated to Stefan problem with that of Brownian motion.
wzheng@math.uci.edu (LaTeX file available)
