Probability Abstracts 11

Click here to see the list of all abstract titles.

187. CRITICAL RANDOM WALK IN RANDOM ENVIRONMENT ON TREES (AND SOME MEAN ZERO, FINITE VARIANCE RANDOM WALK ESTIMATES)

Robin Pemantle and Yuval Peres

We study the behavior of Random Walk in Random Environment (RWRE)
on trees in the critical case left open in previous work.  
Representing the random walk by an electrical network, we make the
natural assumption (see Pemantle (1992)) that the ratios of 
resistances of neighboring edges of a tree $\Gamma$ are i.i.d.
random variables whose logarithms have mean zero and finite
variance.  Then the resulting RWRE is transient if simple random
walk on $\Gamma$ is transient, but not vice versa.  Perhaps surprisingly,  
when the RWRE is transient there is typically a single (random)
infinite path along which the resistances are summable.  In order
to prove quantitative versions of these assertions, we establish
some general results on tree-indexed random walks.  These results
rely on comparison inequalities for percolation processes on trees
and on some new estimates of boundary crossing probabilities for 
ordinary mean-zero finite variance random walks in one dimension,
which are of independent interest.  

peres@math.yale.edu (Latex file available)

188. TREE INDEXED RANDOM WALKS ON GROUPS AND FIRST-PASSAGE PERCOLATION

Itai Benjamini  and  Yuval Peres

Suppose that i.i.d. random variables are attached to the edges of an
infinite tree.  When the tree is large enough, the partial sums
$S_{\sigma}$ along some of its infinite paths will exhibit nontypical
behavior for an ordinary random walk.  For instance, when the
variables are random signs there exists a path in the tree along
which the partial sums are bounded \underbar{iff} the tree boundary
has positive Hausdorff dimension; more precisely, the critical
dimension for having, with positive probability, a path with
$S_{\sigma}$ confined to $\{1,2,\dots,k-1\}$ is\newline
$-\log\cos\frac{\pi}{k}$.  If the labeling variables are positive
then first passage percolation is obtained and we estimate its speed.
 Finally, if the labeling variables take values in a group then
properties of the group are reflected in the sample-path behavior of
the resulting tree-indexed walk.  Our main result here is that a
Green's function criterion for recurrence is valid for groups of
polynomial growth but fails for all groups with nontrivial Poisson
boundary.

peres@math.yale.edu (Plain Tex file available)

189. NOWHERE DIFFERENTIABLE FUNCTIONS CONSTRUCTED FROM PROBABILISTIC POINT OF VIEW

Norio Kono

 Since Weierstrass gave an example of nowhere differentiable 
functions, many people have investigated various type of nowhere 
differentiable functins. We will construct a class of 
nowhere differentiable functions based on i.i.d.
(independent identically distributed) 
random variables and we shall prove nowhere differentability 
by making use of a notion of local times following Berman's idea. 

kono@platon.kula.kyoto-u.ac.jp (Latex file available)

190. THE RATE OF CONVERGENCE OF THE MEAN LENGTH OF THE LONGEST COMMON SUBSEQUENCE

Kenneth S. Alexander

     Given two i.i.d. sequences of n letters from a finite alphabet, one can
consider the length of the longest sequence which is a subsequence of both
the given sequences.  It is known that EL_n grows like cn for some c in
[0,1].  In this paper it is shown that cn >=  EL_n >= cn - K(n log n)^1/2
for an explicit numerical constant K which does not depend on the
distribution of the letters.  In simulations, where n = 100,000 is feasible,
and EL_n/n can be determined from a single such trial with 95% confidence to
within .0055, these results show that c can then be determined with 95%
confidence to within .022, for an arbitrary letter distribution.
     The method is similar to one previously applied to first-passage
percolation--see abstract #118 in this series.
 
alexandr@mtha.usc.edu

191. FLUCTUATIONS IN THE BOUNDARY OF THE WET REGION FOR FIRST-PASSAGE PERCOLATION IN TWO AND THREE DIMENSIONS

Kenneth S. Alexander

     For first-passage percolation on the integer lattice in dimension d = 2
or 3, let B(t) denote the union of all cubes x + [-1/2,1/2]^d  for which the
passage time from 0 to x is at most t.  It is known that, under a moment
condition on the passage time, B(t)/t converges a.s. to a nonrandom convex
set B.  It is shown that the discrepancy between B(t) and tB is O(t^1/2 log
t) a.s., in the sense that B(t) is contained between (t  -  O(t^1/2 log t))B
and (t  +  O(t^1/2 log t))B for sufficiently large t.  Such bounds are
already known for the growth of B(t) along an axis only (see abstract #118 in
this series), but the methods needed here are completely different, more
resembling the proof (Ann. Probab. 18 1547-1562) of a power-law lower bound
for the off-axis connectivity function of subcritical bond percolation.

alexandr@mtha.usc.edu

192. ON ESTIMATING A CONVEX SET

N.H. Bingham

     To estimate an unknown compact convex set $K$ in the plane, given an iid
sample $X_1,\ldots,X_n$ drawn uniformly from $K$.  We form the sample convex
hull $K_n$, and consider (i) the Hausdorff distance $\Delta_n$ between $K$ and
$K_n$, (ii) the time $\T_\epsilon$ before $\Delta_n$ is less than $\epsilon$.
We find the orders of magnitude of these, in the smooth and polygonal cases,
observing a threshold phenomenon in the first but not the second.

n.h.bingham@vax.rhbnc.ac.uk

193. THE CRITICAL CONTACT PROCESS ON A HOMOGENEOUS TREE

G. Morrow, R. Schinazi and Y. Zhang

We prove that the expected number of particles of the critical
contact process on a homogeneous tree is bounded above. This is the
first graph for which the behavior of the expected number of particles
of the critical contact process is known. As an easy corollary of
our result we get that the critical contact process dies out
on any homogeneous tree. This completes the work of R. Pemantle.

schinazi@vision.uccs.edu   (file in plain Tex)

194. LYAPUNOV FUNCTIONS FOR SEMIMARTINGALE REFLECTING BROWNIAN MOTIONS

Paul Dupuis and Ruth J. Williams

We prove that a sufficient condition for a semimartingale
reflecting Brownian motion in an orthant (SRBM) to be
positive recurrent is that all solutions of an associated
deterministic Skorokhod problem are attracted to the
origin. To prove this result, we  construct a
Lyapunov function for the SRBM.

rjwilliams@ucsd.bitnet (hard copy available)

195. CURRENT FLUCTUATIONS FOR THE ASYMMETRIC SIMPLE EXCLUSION PROCESS

P.A. Ferrari, L.R.G. Fontes

We compute the diffusion coefficient of the current
of particles through a fixed point in the one dimensional nearest neighbors 
asymmetric simple exclusion process in equilibrium.
We find $D= \vert p-q \vert \rho(1-\rho) \vert 1-2\rho \vert$, where $p$ is
the rate at which the particles jump to the right, $q$ is the jump rate to the
left and $\rho$ is the density of particles. Notice that $D$ cancels if $p=q$
or $\rho = 1/2$. A law of large numbers and central limit theorems are also
proven. Analogous results are obtained for the current of particles through a
position travelling  at a deterministic velocity $r$. As a corollary we get
that the equilibrium density fluctuations at time $t$ are a translation of the
fluctuations at time $0$. We also show that the current fluctuations at time
$t$ are given, in the scale $t^{1/2}$, by the initial density of particles in
an interval of length $\vert (p-q)(1-2\rho) \vert t$.  The process is
isomorphic to a growth interface process. Our result means that the growth 
fluctuations depend on the general inclination of the surface. In particular 
they vanish for interfaces roughly perpendicular to the observed growth 
direction.

pablo@ime.usp.br  lrenato@ime.usp.br (plain tex file available)

196. ON DOMAIN MONOTONICITY OF THE NEUMANN HEAT KERNEL

Richard F. Bass and Krzysztof Burdzy

Let $p^D(t,x,y)$ denote the Neumann heat kernel for $D$. This is
the fundamental solution for the heat equation with Neumann
boundary conditions, or equivalently, the transition density
of reflecting Brownian motion in $D$. Chavel raised the problem
of giving conditions on $D_1\subset D_2$ so that $p^{D_1}(t,x,y)
\geq p^{D_2}(t,x,y)$ for all $x,y \in D_1$ and all $t>0$. 
A number of papers have appeared establishing this result provided 
additional assumptions are made. And it has been conjectured that 
this result holds whenever $D_1$ and $D_2$ are convex. 
In this paper we show that this conjecture is false. A first 
counterexample shows that it is not true, even if $D_1$ has a 
closure contained in the interior of $D_2$, both $D_1$ and $D_2$ are 
bounded, strictly convex,  and smooth.  The second example shows that 
the conjecture is not true, even for sufficiently small $t$ unless 
one assumes that the closure of $D_1$ is contained in the interior of $D_2$.

bass@math.washington.edu or burdzy@math.washington.edu  (AMSTeX file available)