Probability Abstracts 22

Click here to see the list of all abstract titles.

358. ON THE LAW OF THE ITERATED LOGARITHM FOR CANONICAL U-STATISTICS AND PROCESSES

Miguel A. Arcones and Evarist Gin\'e

The law of the iterated logarithm for canonical
or completely degenerate $U$--statistics with square
integrable kernel $h$ is proved, for
$\scriptstyle{h}$ taking values in $\bf R$,
${\bf R}^d$ and,
in general, in a type 2 separable Banach space. The LIL is also
obtained for $U$--processes indexed by canonical
Vapnik--\v Cervonenkis classes of functions with square integrable
envelope. In more generality, an equicontinuity condition equivalent
to the LIL property is given, and a first look is taken at
reducing the a.s. convergence in the LIL to convergence in
probability. Some of these results are
then applied to obtain the a.s. exact order of the remainder term
in the linearization of the product limit estimator for truncated
data; a consequence for density estimation is also included.

gine@uconnvm.uconn.edu  (plain tex file available)

359. ON THE MARKOV CHAIN FOR THE MOVE-TO-ROOT RULE FOR BINARY SEARCH TREES

Robert P. Dobrow and James Allen Fill

The move-to-root (MTR) heuristic is a self-organizing rule which 
attempts to keep a binary search tree in near-optimal form. It is
a tree analogue of the move-to-front (MTF) scheme for self-organizing
lists. Both heuristics can be modeled as Markov chains. We show that
the MTR chain can be derived by lumping the MTF chain and give exact
formulas for the transition probabilities and stationary
distribution for MTR. We also derive the eigenvalues and their 
multiplicites for MTR.

dobrow@cam.nist.gov   jimfill@jhuvm.hcf.jhu.edu

360. RATES OF CONVERGENCE FOR THE MOVE-TO-ROOT MARKOV CHAIN FOR BINARY SEARCH TREES

Robert P. Dobrow and James Allen Fill

The move-to-root heuristic is a self-organizing rule which attempts 
to keep a binary search tree in near-optimal form. It is a tree
analogue of the move-to-front scheme (also known as the weighted
random-to-top card shuffle or Tsetlin library) for self-organizing
lists. We study convergence of the move-to-root Markov chain to
its stationary distribution and show that move-to-root converges
two to four times faster than move-to-front for many examples.
We also discuss asymptotics for expected search cost. For equal
weights, $c n / \ln n$ steps are necessary and sufficient to drive
maximum relative error to 0.

dobrow@cam.nist.gov   jimfill@jhuvm.hcf.jhu.edu

361. THE MOVE-TO-FRONT RULE FOR SELF-ORGANIZING LISTS WITH MARKOV DEPENDENT REQUESTS

Robert P. Dobrow and James Allen Fill

We consider the move-to-front self-organizing linear search
heuristic where the sequence of record requests is a Markov
chain. Formulas are derived for the transition probabilities
and stationary distribution of the permutation chain. The 
spectral structure of the chain is presented explicitly. Bounds
on the discrepancy from stationarity for the permutation
chain are computed in terms of the corresponding discrepancy for
the request chain, both for separation and for total variation
distance.

dobrow@cam.nist.gov   jimfill@jhuvm.hcf.jhu.edu

362. SEMIMARTINGALE REFLECTING BROWNIAN MOTIONS IN THE ORTHANT

R. J. Williams
    
This paper surveys recent work on  semimartingale 
reflecting Brownian motions in the
orthant. These diffusion processes have been proposed as approximate
models of multiclass open queueing networks in heavy traffic.
The topics covered by this survey are 
the problems of existence and uniqueness, 
recurrence classification and
stationary distributions for these diffusions.
 
williams@math.ucsd.edu (postscript file available)

363. CORRECTED NORMAL APPROXIMATION FOR THE PROBABILITY OF RUIN WITHIN FINITE TIME

Vsevolod K. Malinovskii

A  new  refinement  of  the  normal-type  approximation   for   the
probability of ruin before time $t$ in the framework of  Andersen's
risk   model  is  suggested.  This  approximation is proved to be a
refinement  of  the  classical  normal-type  approximation  and  is
deduced   from   von   Bahr's  representation of  ruin  probability
in  terms  of  ladder  height distributions.  The  proof  is  based
on a technique developed  to  obtain  the Edgeworth-type expansions
in the framework of stopped random sequences.

malinov@prob.mian.su   malinov@mian.su

364. EXISTENCE, UNIQUENESS AND INVARIANT MEASURES FOR STOCHASTIC SEMILINEAR EQUATIONS ON HILBERT SPACES

A.Chojnowska-Michalik and B.Goldys

A class of stochastic evolution equations with additive noise and weakly 
continuous drift is considered. We show existence, uniqueness, compactness 
and smoothing properties of the corresponding transition semigroup in $L^p$
spaces and Sobolev spaces $W^{1,p}$ which are built on invariant measure 
of the corresponding Ornstein-Uhlenbeck process. As a consequence we prove 
uniqueness of martingale solutions to the stochastic equation and existence 
of a unique invariant measure equivalent to invariant measure of 
Ornstein-Uhlenbeck process. It is shown also that the density of this measure 
is in $W^{1,p}$ for all p.

beng@hydra.maths.unsw.edu.au

365. EVEN AND ODD CONTINUOUS ADDITIVE FUNCTIONALS

P.J. Fitzsimmons

We study notions of ``even'' and ``odd,'' with respect to a family of
time-reversal involutions, for the continuous additive functionals of a
symmetric Markov diffusion.  These notions are related to Fukushima's
decomposition, to the Lyons-Zheng forward-backward martingale
decomposition, and to Nakao's stochastic integral.  Somewhat surprisingly,
the class of locally zero-energy continuous additive functionals coincides
with the class of even continuous additive functionals.  These ideas are
applied to a study of Girsanov
transformations which yield dual pairs of nonsymmetric diffusions.

pfitzsim@ucsd.edu    (plainTeX file available)

366. OCCUPATION TIME DISTRIBUTIONS FOR LEVY BRIDGES AND EXCURSIONS

P.J. Fitzsimmons and R.K. Getoor

Let $X$ be a one-dimensional L\'evy process.  It is shown that under the
bridge law for $X$ starting from 0 and ending at 0 at time $t$, the amount
of time $X$ spends positive has a uniform distribution on $[0,t]$.  (This
result has also bee proved recently by F. Knight.)  When 0 is a regular
point, this uniform distribution result leads to an explicit expression for
the Laplace transform of the joint distribution of the pair $(R,A_R)$,
where $R$ is the length of an excursion of $X$ from 0, and $A_R$ is the
total time $X$ spends positive during the excursion.  More concrete
expressions are obtained for stable processes by specialization.  In
particular, a formula determining the distribution of $A_R/R$ is given in
the stable case.

pfitzsim@ucsd.edu      (plainTeX file available)

367. ONE-DIMENSIONAL MOVING BOUNDARIES HITTING-TIMES ESTIMATES AND BEURLING'S PROJECTION THEOREM ON HARMONIC MEASURE

Wendelin Werner

We prove some elementary intuitive estimates on moving-boundaries hitting 
times by one-dimensional Brownian motion. These results imply Beurling's
radial projection Theorem on harmonic measure in a disc, and give an alternative
approach to this problem.

W.J.J.Werner@statslab.cam.ac.uk

368. AN UPPER BOUND OF THE DISCONNECTION EXPONENT FOR TWO-DIMENSIONAL BROWNIAN MOTION

Wendelin Werner 

We derive an upper bound for the disconnection exponent $\gamma$ for 
two-dimensional Brownian motion. More precisely, we show that 
$\gamma < 1/2 - (\log 2)^2/(2 \pi^2) < 0.47567$. This shows in particular 
that $\gamma$ is not equal to its trivial upper bound (i.e. 1/2). We also 
derive similar estimates of disconnection exponents for several planar 
Brownian motions.

W.J.J.Werner@statslab.cam.ac.uk

369. COMPARING FLEMING--VIOT AND DAWSON--WATANABE PROCESSES

S.N. Ethier and Stephen M. Krone

   Fleming--Viot processes and Dawson--Watanabe processes are two 
classes of ``superprocesses'' that have received a great deal of 
attention in recent years.  These  processes have many properties in
common.  In this paper, we prove a result that helps to explain why 
this is so.  It allows one to prove certain theorems for one class
when they are true for the other.  More specifically, we show that product
moments of a Fleming--Viot process can be bounded above by
the corresponding moments of the Dawson--Watanabe process with the
same ``underlying particle motion,'' and vice versa except for a
multiplicative constant. As an application, we establish existence and
continuity properties of local time for certain Fleming--Viot processes. 

krone@cms.wisc.edu  (Tex file available)

370. THE COMPLEX ZEROS OF RANDOM POLYNOMIALS

Larry A. Shepp and Robert J. Vanderbei

Mark Kac gave an explicit formula for the expectation of the number,
$\nu_n(\Omega)$, of zeros of a random polynomial,
$$	P_n(z) = \sum_{j=0}^{n-1} \eta_j z^j ,$$
in any measurable subset $\Omega$ of the {\em reals}.
Here, $\eta_0, \ldots,
\eta_{n-1}$ are independent standard normal random variables.
In fact, for each $n>1$,
he obtained an explicit intensity function $g_n$ for which
$$	\Exp \nu_n(\Omega) = \int_\Omega g_n(x) dx .$$
Here, we extend this formula to obtain an explicit formula for the
expected number of zeros in any measurable subset $\Omega$ of the 
complex plane $\complexs$.  Namely, we show that
$$	\Exp \nu_n(\Omega) = \int_\Omega h_n(x,y) dxdy 
		      + \int_{\Omega \cap \reals} g_n(x) dx ,$$
where $h_n$ is an explicit intensity function.  We also study the
asymptotics of $h_n$ showing that for large $n$ its mass lies close to,
and is uniformly distributed around, the unit circle.

rvdb@princeton.edu

371. ASYMPTOTIC EXIT LOCATION DISTRIBUTIONS IN THE STOCHASTIC EXIT PROBLEM

Robert S. Maier and Daniel L. Stein

Consider a two-dimensional continuous-time dynamical system, with an
attracting fixed point $S$.  If the deterministic dynamics are perturbed by
white noise (random perturbations) of strength $\epsilon$, the system state
as a function of time will define a diffusion process.  This process will
eventually leave the domain of attraction $\Omega$ of $S$.

We analyse the case when, as $\epsilon \to 0$, the exit location on the
boundary of $\Omega$ (assumed to be smooth) is increasingly concentrated
near a saddle point $H$ of the deterministic dynamics.  We show using
formal methods (matched asymptotic expansions, rather than rigorous
analysis) that the asymptotic form of the exit location distribution on the
boundary is generically non-Gaussian and asymmetric, and classify the
possible limiting distributions.

Our classification is a `sub-large deviations' result in that it allows one
to distinguish, in the $\epsilon \to 0$ limit, between behaviors that are
indistinguishable from the point of view of conventional
(Wentzell-Friedlin) large deviations theory.  A key role in the
classification is played by a parameter $\mu$, equal to the ratio
$|\lambda_s(H)|/\lambda_u(H)$ of the stable and unstable eigenvalues of the
linearized deterministic flow at the saddle point $H$.  If $\mu<1$ then the
exit location distribution is generically asymptotic as $\epsilon \to 0$ to
a Weibull distribution with shape parameter $2/\mu$, on the
$O(\epsilon^{\mu/2})$ lengthscale near $H$.  If $\mu>1$ it is generically
asymptotic to a distribution on the $O(\epsilon^{1/2})$ lengthscale, whose
moments we compute.

The asymmetry of the limiting exit location distributions is attributable
to the generic presence of a `classically forbidden' region: a wedge-shaped
subset of $\Omega$ with the saddle point $H$ as vertex, which is reached
from $S$, in the $\epsilon \to 0$ limit, only via `bent' (non-smooth)
fluctuational paths that first pass through the vicinity of $H$.  As a
consequence we expect that the Wentzell-Freidlin quasipotential function,
which governs the frequency of fluctuations to the vicinity of any point in
$\Omega$, will generally fail to be twice differentiable at $H$.

rsm@math.arizona.edu

372. SECOND CLASS PARTICLES IN THE RAREFACTION FAN

P. A. Ferrari, C. Kipnis

We consider the one dimensional totally asymmetric nearest neighbors simple
exclusion process with drift to the right starting with the configuration
``all one'' to the left and ``all zero'' to the right of the origin. We prove
that a second class particle initially added at the origin chooses randomly
one of the characteristics with the uniform law on the directions and then
moves at constant speed along the chosen one. The result extends to the case
of a product initial distribution with densities $\rho>\lambda$ to the left and
right of the origin respectively. Furthermore we show that, with a positive
probability, two second class particles in the rarefaction fan never meet.

pablo@ime.usp.br

373. SUPERDIFFUSIONS AND REMOVABLE BOUNDARY SINGULARITIES FOR QUASILINEAR PARTIAL DIFFERENTIAL EQUATIONS

E.B.Dynkin and S.E.Kuznetsov 

	To every second order elliptic differential operator  L  and to every
number 1<a<2 or a=2  there corresponds a measure-valued Markov
process  X  called the  (L,a)-superdiffusion. Suppose that
 A  is a closed subset of  the d-dimensional Euclidean space E. It is
known that the following three statements are equivalent:

(1) the range of X does not hit  A ;

(2) if  Lu=u^a  in  E\ A , then  u=0   [in other words,  A  is a
removable singularity for all solutions of equation  Lu=u^a];

(3)  C_{2,a'}(A)=0  where  1/a+1a'=1  and  C_{r,q}  is the
so-called Bessel capacity.   

The equivalence of (2) and (3) has been established by Baras and
Pierre in 1984 and the equivalence of (1) and (2) has
been proved by Dynkin in 1991.  
 
	In this paper, we consider subsets  A  of the boundary  B  of
a bounded domain  D  and  we establish (assuming that B is
smooth) the equivalence of the following three statements:

	(a) the range of X in D does not hit A;

	(b) if Lu=u^a in D and if u tends to 0 as x tends to any point
p of B\A , then  u=0 ;

	(c) C_{2/a,a'}(A)=0 where C is the Bessel capacity on B.

	This implies the positive answer to two conjectures posed by Dynkin a
few years ago.  (The conjectures have already been confirmed for  a=2  and
L=Laplacian in a recent paper of  Le Gall.)  

	By using a combination of probabilistic and analytic arguments we not
only prove  the equivalence of (a)-(c) but also give a new, simplified proof of
the equivalence of (1)-(3).

ebd1@cornell.edu

374. ITERATED LAW OF ITERATED LOGARITHM

Krzysztof Burdzy and Jaime San Martin

Let $L^\eps_t$ be the amount of local time accumulated 
by Brownian motion on the curve
$(1-\eps) \sqrt{2 s \log \log s}$ between times $1$
and $t$. Then for small $\eps > 0$,
$$\limsup_{t\to\infty} 
L^\eps_t / \sqrt{2 t \log \log t} = 2 \eps + o(\eps).$$
For $\eps = 0$ we have
$$\limsup_{t\to\infty} 
L^0_t / \sqrt{ t / \log \log t} \log \log \log t
= (3/2) \sqrt{2}.$$

burdzy@math.washington.edu (plain TeX file available)

375. CORRELATED SPIN GLASSES ON TREES

Ed Waymire and Stan Williams   

Random polymer models on trees were introduced in
Derrida and Spohn (1988) as a framework in which 
one can compute phase transitions in the free energy 
of a spin glass.  The corresponding problem on the 
square lattice is a major unsolved problem in the 
statistical physics of spin glasses, even in the case
of mean field interactions. In the case of mean field 
random polymers on trees connections with two important
classes of random measures, namely independent random
cascades and independent branching random walks, have 
been previously exploited in Collet and Koukiou (1992) and
in Chauvin and Rouault (1994), respectively.  In this paper
we first re-visit the phase transition problem in the mean 
field case and provide a very simple computation of the free 
energy based on a combination of the size-biased technique 
introduced in Waymire and Williams (1993) for random cascades,
and a branching random walk computation given in Biggins (1976).
We then extend the computation to the case in which the mean
field hypothesis is replaced by certain correlations.  Previous
results of the authors are used to demonstrate a surprising 
symmetry-breaking phenomena associated with this phase transition.

waymire@MATH.ORST.EDU  (plain tex file or hard copy available)