Probability Abstracts 81

This document contains abstracts 2616-2737. They have been mailed on June 30, 2004.

2616. FUNCTIONAL LIMIT THEOREMS FOR MULTIPARAMETER FRACTIONAL BROWNIAN MOTION 

Anatoliy Malyarenko

  We prove a general functional limit theorem for multiparameter fractional
Brownian motion. The functional law of the iterated logarithm, functional
L\'{e}vy's modulus of continuity and many other results are its particular
cases. Applications to approximation theory are discussed.

2617. THE CONTACT PROCESS WITH ADDED EDGES 

Paul Jung

  We show that the critical value for the contact process on a transitive graph
G with finitely many edges added to it is the same as the critical value for
the contact process on G.

2618. EXPLICIT REPRESENTATION OF FINITE PREDICTOR COEFFICIENTS AND ITS APPLICATIONS 

Akihiko Inoue and Yukio Kasahara

  We consider the finite-past predictor coefficients of stationary time series,
and establish an explicit representation for them, in terms of the MA and AR
coefficients. The proof involves the alternate iteration of projection
operators associated with the infinite past and the infinite future. We provide
several applications, which include rates of convergence of the finite
predictor coefficients, an equality of Baxter-type for long memory processes,
and a simple representation of the partial autocorrelation function (PACF). We
use the last result to obtain the precise asymptotic behavior of PACF with
remainder, for the fractional ARIMA processes.

2619. SEMI-ADDITIVE FUNCTIONALS AND COCYCLES IN THE CONTEXT OF SELF-SIMILARITY 

Vladas Pipiras, Murad S.Taqqu

  Self-similar symmetric $\alpha$-stable, $\alpha\in(0,2)$, mixed moving
averages can be related to nonsingular flows. By using this relation and the
structure of the underlying flows, one can decompose self-similar mixed moving
averages into distinct classes and then examine the processes in each of these
classes separately. The relation between processes and flows involves
semi-additive functionals. We establish a general result about semi-additive
functionals related to cocycles, and identify the presence of a new
semi-additive functional in the relation between processes and flows. This new
functional is useful for finding the kernel function of self-similar mixed
moving averages generated by a given flow. It also sheds new light on previous
results on the subject.

2620. INTEGRAL REPRESENTATIONS OF PERIODIC AND CYCLIC FRACTIONAL STABLE MOTIONS 

Vladas Pipiras and Murad S.Taqqu

  Stable non-Gaussian self-similar mixed moving averages can be decomposed into
several components. Two of these are the periodic and cyclic fractional stable
motions which are the subject of this study. We focus on the structure of their
integral representations and show that the periodic fractional stable motions
have, in fact, a canonical representation. We study several examples and
discuss questions of uniqueness, namely how to determine whether two given
integral representations of periodic or cyclic fractional stable motions give
rise to the same process.

2621. EXCURSION DECOMPOSITIONS FOR $\SLE$ AND WATTS' CROSSING FORMULA 

Julien Dubedat

  It is known that Schramm-Loewner Evolutions (SLEs) have a.s. frontier points
if $\kappa>4$ and a.s. cutpoints if $4<\kappa<8$. If $\kappa>4$, an appropriate
version of $\SLE(\kappa)$ has a renewal property: it starts afresh after
visiting its frontier. Thus one can give an excursion decomposition for this
particular $\SLE(\kappa)$ ``away from its frontier''. For $4<\kappa<8$, there
is a two-sided analogue of this situation: a particular version of
$\SLE(\kappa)$ has a renewal property w.r.t its cutpoints; one studies
excursion decompositions of this $\SLE$ ``away from its cutpoints''. For
$\kappa=6$, this overlaps Vir\'ag's results on ``Brownian beads''. As a
by-product of this construction, one proves Watts' formula, which describes the
probability of a double crossing in a rectangle for critical plane percolation.

2622. THE SPACE REQUIREMENT OF M-ARY SEARCH TREES: DISTRIBUTIONAL ASYMPTOTICS FOR M >= 27 

James Allen Fill and Nevin Kapur

  We study the space requirement of $m$-ary search trees under the random
permutation model when $m \geq 27$ is fixed. Chauvin and Pouyanne have shown
recently that $X_n$, the space requirement of an $m$-ary search tree on $n$
keys, equals $\mu (n+1) + 2\Re{[\Lambda n^{\lambda_2}]} + \epsilon_n
n^{\Re{\lambda_2}}$, where $\mu$ and $\lambda_2$ are certain constants,
$\Lambda$ is a complex-valued random variable, and $\epsilon_n \to 0$ a.s. and
in $L^2$ as $n \to \infty$. Using the contraction method, we identify the
distribution of $\Lambda$.

2623. MODERATE DEVIATION PRINCIPLE FOR EXPONENTIALLY ERGODIC MARKOV CHAIN 

B. Delyon, A. Juditsky, R. Liptser

  For ${1/2}<\alpha<1$, we propose the MDP analysis for family $$
S^\alpha_n=\frac{1}{n^\alpha}\sum_{i=1}^nH(X_{i-1}), n\ge 1, $$ where
$(X_n)_{n\ge 0}$ be a homogeneous ergodic Markov chain, $X_n\in \mathbb{R}^d$,
when the spectrum of operator $P_x$ is continuous. The vector-valued function
$H$ is not assumed to be bounded but the Lipschitz continuity of $H$ is
required. The main helpful tools in our approach are Poisson equation and
Stochastic Exponential; the first enables to replace the original family by
$\frac{1}{n^\alpha}M_n$ with a martingale $M_n$ while the second to avoid the
direct Laplace transform analysis.

2624. THE MIXING TIME FOR SIMPLE EXCLUSION 

Ben Morris

  We obtain a tight bound of $O(L^2 \log k)$ for the mixing time of the
exclusion process in $Z^d/LZ^d$ with $k \leq 1/2 L^d$ particles. Previously the
best bound, based on the log Sobolev constant determined by Yau, was not tight
for small $k$. When dependence on the dimension $d$ is considered, our bounds
are an improvement for all $k$. We also get bounds for the relaxation time that
are lower-order in $d$ than previous estimates: our bound of $O(L^2 \log d$
improves on the earlier bound $O(L^2 d)$, obtained by Quastel. Our proof is
based on an auxiliary Markov chain we call the chameleon process, which may be
of independent interest.

2625. SPECTRAL GAP FOR THE ZERO RANGE PROCESS WITH CONSTANT RATE 

Ben Morris

  We solve an open problem concerning the relaxation time (inverse spectral
gap) of the zero range process in $Z^d/LZ^d$ with constant rate, proving an
upper bound of $O((\rho + 1)^2 L^2)$, where $\rho$ is the density of particles.

2626. SELF-SIMILAR FRAGMENTATIONS DERIVED FROM THE STABLE TREE I: SPLITTING AT HEIGHTS 

Gregory Marc Miermont

  The basic object we consider is a certain model of continuum random tree,
called the stable tree. We construct a fragmentation process $(F^-(t), t>=0)$
out of this tree by removing the vertices located under height $t$. Thanks to a
self-similarity property of the stable tree, we show that the fragmentation
process is also self-similar. The semigroup and other features of the
fragmentation are given explicitly. Asymptotic results are given, as well as a
couple of related results on continuous-state branching processes.

2627. SELF-SIMILAR FRAGMENTATIONS DERIVED FROM THE STABLE TREE II: SPLITTING AT NODES 

Gregory Marc Miermont

  We study a natural fragmentation process of the so-called stable tree
introduced by Duquesne and Le Gall, which consists in removing the nodes of the
tree according to a certain procedure that makes the fragmentation self-similar
with positive index. Explicit formulas for the semigroup are given, and we
provide asymptotic results. We also give an alternative construction of this
fragmentation, using paths of Levy processes, hence echoing the two alternative
constructions of the standard additive coalescent by fragmenting the Brownian
continuum random tree or using Brownian paths, respectively due to
Aldous-Pitman and Bertoin.

2628. A STOCHASTIC FLOW ARISING IN THE STUDY OF LOCAL TIMES 

Jon Warren

  A stochastic flow of homeomorphisms of the real line previously studied by
Bass and Burdzy is shown to arise in describing a Brownian motion conditional
on knowing its local times on hitting a fixed level. This makes it possible to
connect Ray-Knight type results for the flow with the classical Ray-Knight
theorems for Brownian motion.

2629. POISSON STATISTICS FOR THE LARGEST EIGENVALUES OF WIGNER RANDOM MATRICES WITH HEAVY TAILS 

Alexander Soshnikov

  We study large Wigner random matrices in the case when the marginal
distributions of matrix entries have heavy tails. We prove that the largest
eigenvalues of such matrices have Poisson statistics.

2630. STRONG APPROXIMATION FOR THE SUPERMARKET MODEL 

Malwina J. Luczak and James Norris

  We prove three strong approximation theorems for the `supermarket' or `join
the shortest queue' model -- a law of large numbers, a jump process
approximation and a central limit theorem. The estimates are carried through
rather explicitly. This allows us to estimate each of the infinitely many
components of the process in its own scale and to exhibit a cut-off in the set
of active components which grows slowly with the number of servers.

2631. REPULSION OF AN EVOLVING SURFACE ON RANDOM WALLS 

L.R.G. Fontes, M. Vachkovskaia, A. Yambartsev

  We consider the motion of a discrete random surface interacting by exclusion
with a random wall. Two cases are considered: rarefied walls and walls of
random height. The dynamics is given by the serial harness process. In the
first case, we prove that the process delocalizes iff the mean number of visits
to the set of sites where the wall is present by a random walk is infinite.
When the surface delocalizes, bounds on its average speed are obtained. In the
case of walls of random height, we study the effect of the distribution of the
wall heights on the repulsion speed.

2632. LIMIT SHAPES FOR RANDOM SQUARE YOUNG TABLEAUX AND PLANE PARTITIONS 

Boris Pittel and Dan Romik

  Our main result is a limit shape theorem for the two-dimensional surface
defined by a uniform random n-by-n square Young tableau. The analysis leads to
a calculus of variations minimization problem that resembles the minimization
problems studied by Logan-Shepp, Vershik-Kerov, and Cohn-Larsen-Propp. Our
solution involves methods from the theory of singular integral equations, and
sheds light on the somewhat mysterious derivations in these works. An extension
to rectangular diagrams, using the same ideas but involving some nontrivial
computations, is also given.
  We give several applications of the main result. First, we show that the
location of a particular entry in the tableau is in the limit governed by a
semicircle distribution.
  Next, we derive a result on the length of the longest increasing subsequence
in segments of a minimal Erdos-Szekeres permutation, namely a permutation of
the numbers 1,2,...,n^2 whose longest monotone subsequence is of length n (and
hence minimal by the Erdos-Szekeres theorem).
  Finally, we prove a limit shape theorem for the surface defined by a random
plane partition of a very large integer over a large square (and more generally
rectangular) diagram.

2633. SPECTRAL CHARACTERISATION OF AGEING: THE REM-LIKE TRAP MODEL 

A.Bovier, A.Faggionato

  We review the ageing phenomenon in the context of simplest trap model,
Bouchaud's REM-like trap model from a spectral theoretic point of view. We show
that the generator of the dynamics of this model can be diagonalised exactly.
Using this result, we derive closed expressions for correlation functions in
terms of complex contour integrals that permit an easy investigation into their
large time asymptotics in the thermodynamic limit. We also give a `grand
canonical' representation of the model in terms of the Markov process on a
Poisson point process . In this context we analyse the dynamics on various time
scales.

2634. NON-ARCHIMEDEAN VALUED QUASI-INVARIANT DESCENDING AT INFINITY MEASURES 

S. V. Ludkovsky

  The article is devoted to the investigation of particular classes of
quasi-invariant descending at infinity measures on linear spaces over
non-Archimedean fields such that measures are with values in non-Archimedean
fields also. Their applications to stochastic processes and partial
pseudo-differential equations are given.

2635. THE MAXIMALITY PRINCIPLE REVISITED: ON CERTAIN OPTIMAL STOPPING PROBLEMS 

Jan Obloj

  We investigate the optimal stopping problems involving the supremum of a
diffusion. The starting point is the link between works of Peskir and
Meilijson, which we describe in a unified manner. The description developped
follows mainly the work of Peskir and relies on the maximality principle which
links the existence and form of the solution to an optimal stopping problem
with a special solution of a certain differential equaiton. We also discuss the
so-called optimal Skorokhod embedding problem and provide an explicit solution
for a large class of measures.

2636. DEFORMATIONS OF CONVOLUTION SEMIGROUPS ON COMMUTATIVE HYPERGROUPS 

Margit R\"osler, Michael Voit

  It was recently shown by the authors that deformations of hypergroup
convolutions w.r.t. positive semicharacters can be used to explain
probabilistic connections between the Gelfand pairs (SL(d,C), SU(d)) and
Hermitian matrices. We here study connections between general convolution
semigroups on commutative hypergroups and their deformations.
 We are able to develop a satisfying theory, if the underlying positive
semicharacter has some growth property. We present several examples which
indicate that this growth condition holds in many interesting cases.

2637. MOMENTS AND TAILS IN MONOTONE-SEPARABLE STOCHASTIC NETWORKS 

Francois Baccelli and Serguei Foss

  A network belongs to the monotone separable class if its state variables are
homogeneous and monotone functions of the epochs of the arrival process.
 This framework, which was first introduced to derive the stability region for
stochastic networks with stationary and ergodic driving sequences, is
revisited. It contains several classical queueing network models, including
generalized Jackson networks, max-plus networks, polling systems, multiserver
queues, and various classes of stochastic Petri nets. Our purpose is the
analysis of the tails of the stationary state variables in the particular case
of i.i.d. driving sequences. For this, we establish general comparison
relationships between networks of this class and the GI/GI/1/\infty queue.
 We first use this to show that two classical results of the asymptotic theory
for GI/GI/1/\infty queues can be directly extended to this framework.
 The first one concerns the existence of moments for the stationary state
variables. We establish that for all \alpha\geq 1, the (\alpha+1)-moment
condition for service times is necessary and sufficient for the existence of
the \alpha-moment for the stationary maximal dater (typically the time to empty
the network when stopping further arrivals) in any network of this class. The
second one is a direct extension of Veraverbeke's tail asymptotic for the
stationary waiting times in the GI/GI/1/\infty queue.

2638. A REPRESENTATION OF GIBBS MEASURE FOR THE RANDOM ENERGY MODEL 

Marie F. Kratz and Pierre Picco

  In this work we consider a problem related to the equilibrium statistical
mechanics of spin glasses, namely the study of the Gibbs measure of the random
energy model. For solving this problem, new results of independent interest on
sums of spacings for i.i.d. Gaussian random variables are presented.
 Then we give a precise description of the support of the Gibbs measure below
the critical temperature.

2639. PERFECT SAMPLING USING BOUNDING CHAINS 

Mark Huber

  Bounding chains are a technique that offers three benefits to Markov chain
practitioners: a theoretical bound on the mixing time of the chain under
restricted conditions, experimental bounds on the mixing time of the chain that
are provably accurate and construction of perfect sampling algorithms when used
in conjunction with protocols such as coupling from the past.
 Perfect sampling algorithms generate variates exactly from the target
distribution without the need to know the mixing time of a Markov chain at all.
We present here the basic theory and use of bounding chains for several chains
from the literature, analyzing the running time when possible. We present
bounding chains for the transposition chain on permutations, the hard core gas
model, proper colorings of a graph, the antiferromagnetic Potts model and sink
free orientations of a graph.

2640. A HOMING PROBLEM FOR DIFFUSION PROCESSES WITH CONTROL-DEPENDENT VARIANCE 

Mario Lefebvre

  Controlled one-dimensional diffusion processes, with infinitesimal variance
 (instead of the infinitesimal mean) depending on the control variable, are
considered in an interval located on the positive half-line. The process is
controlled until it reaches either end of the interval. The aim is to minimize
the expected value of a cost criterion with quadratic control costs on the way
and a final cost equal to zero (resp. a large constant) if the process exits
the interval through its left (resp. right) end point.
 Explicit expressions are obtained both for the optimal value of the control
variable and the value function when the infinitesimal parameters of the
processes are proportional to a power of the state variable.

2641. CONVERGENCE RATE OF LINEAR TWO-TIME-SCALE STOCHASTIC APPROXIMATION 

Vijay R. Konda and John N. Tsitsiklis

  We study the rate of convergence of linear two-time-scale stochastic
approximation methods. We consider two-time-scale linear iterations driven by
i.i.d. noise, prove some results on their asymptotic covariance and establish
asymptotic normality. The well-known result [Polyak, B. T. (1990). Automat.
 Remote Contr. 51 937-946; Ruppert, D. (1988). Technical Report 781, Cornell
 Univ.] on the optimality of Polyak-Ruppert averaging techniques specialized to
linear stochastic approximation is established as a consequence of the general
results in this paper.

2642. INVARIANT STATES AND RATES OF CONVERGENCE FOR A CRITICAL FLUID MODEL OF A PROCESSOR SHARING QUEUE 

Amber L. Puha and Ruth J. Williams

  This paper contains an asymptotic analysis of a fluid model for a heavily
loaded processor sharing queue. Specifically, we consider the behavior of
solutions of critical fluid models as time approaches \infty. The main theorems
of the paper provide sufficient conditions for a fluid model solution to
converge to an invariant state and, under slightly more restrictive
assumptions, provide a rate of convergence. These results are used in a related
work by Gromoll for establishing a heavy traffic diffusion approximation for a
processor sharing queue.

2643. DUAL FORMULATION OF THE UTILITY MAXIMIZATION PROBLEM: THE CASE OF NONSMOOTH UTILITY 

B. Bouchard, N. Touzi and A. Zeghal

  We study the dual formulation of the utility maximization problem in
incomplete markets when the utility function is finitely valued on the whole
real line. We extend the existing results in this literature in two directions.
 First, we allow for nonsmooth utility functions, so as to include the
shortfall minimization problems in our framework. Second, we allow for the
presence of some given liability or a random endowment. In particular, these
results provide a dual formulation of the utility indifference valuation rule.

2644. ON OVERLOAD IN A STORAGE MODEL, WITH A SELF-SIMILAR AND INFINITELY DIVISIBLE INPUT 

J. M. P. Albin and Gennady Samorodnitsky

  Let {X(t)}_{t\ge0} be a locally bounded and infinitely divisible stochastic
process, with no Gaussian component, that is self-similar with index H>0.
 Pick constants \gamma >H and c>0. Let \nu be the L\'evy measure on
R^{[0,\infty)} of X, and suppose that R(u)\equiv\nu({y\inR^{[0,\infty)}:supt\ge
0y(t)/(1+ct^{\gamma})>u}) is suitably ``heavy tailed'' as u\to\infty (e.g.,
subexponential with positive decrease). For the ``storage process'' Y(t)\equiv
sup_{s\ge t}(X(s)-X(t)-c(s-t)^{\gamma}), we show that
P{sup_{s\in[0,t(u)]}Y(s)>u}\sim P{Y(\hat t(u))>u} as u\to\infty, when 0\le \hat
t(u)\le t(u) do not grow too fast with u [e.g., t(u)=o(u^{1/\gamma})].

2645. SPANNING TREE SIZE IN RANDOM BINARY SEARCH TREES 

Alois Panholzer and Helmut Prodinger

  This paper deals with the size of the spanning tree of p randomly chosen
nodes in a binary search tree. It is shown via generating functions methods,
that for fixed p, the (normalized) spanning tree size converges in law to the
Normal distribution. The special case p=2 reproves the recent result
 (obtained by the contraction method by Mahmoud and Neininger [Ann. Appl.
 Probab. 13 (2003) 253-276]), that the distribution of distances in random
binary search trees has a Gaussian limit law. In the proof we use the fact that
the spanning tree size is closely related to the number of passes in Multiple
Quickselect. This parameter, in particular, its first two moments, was studied
earlier by Panholzer and Prodinger [Random Structures Algorithms
 13 (1998) 189-209]. Here we show also that this normalized parameter has for
fixed p-order statistics a Gaussian limit law. For p=1 this gives the
well-known result that the depth of a randomly selected node in a random binary
search tree converges in law to the Normal distribution.

2646. OPTIMAL INVESTMENT WITH RANDOM ENDOWMENTS IN INCOMPLETE MARKETS 

Julien Hugonnier and Dmitry Kramkov

  In this paper, we study the problem of expected utility maximization of an
agent who, in addition to an initial capital, receives random endowments at
maturity. Contrary to previous studies, we treat as the variables of the
optimization problem not only the initial capital but also the number of units
of the random endowments. We show that this approach leads to a dual problem,
whose solution is always attained in the space of random variables. In
particular, this technique does not require the use of finitely additive
measures and the related assumption that the endowments are bounded.

2647. ON THE MINIMAL TRAVEL TIME NEEDED TO COLLECT N ITEMS ON A CIRCLE 

Nelly Litvak and Willem R. van Zwet

  Consider n items located randomly on a circle of length 1. The locations of
the items are assumed to be independent and uniformly distributed on
 [0,1). A picker starts at point 0 and has to collect all n items by moving
along the circle at unit speed in either direction. In this paper we study the
minimal travel time of the picker. We obtain upper bounds and analyze the exact
travel time distribution. Further, we derive closed-form limiting results when
n tends to infinity. We determine the behavior of the limiting distribution in
a positive neighborhood of zero. The limiting random variable is closely
related to exponential functionals associated with a Poisson process. These
functionals occur in many areas and have been intensively studied in recent
literature.

2648. OPTIMAL HOEFFDING BOUNDS FOR DISCRETE REVERSIBLE MARKOV CHAINS 

Carlos A. Leon and Francois Perron

  We build optimal exponential bounds for the probabilities of large deviations
of sums \sum_{k=1}^nf(X_k) where (X_k) is a finite reversible Markov chain and
f is an arbitrary bounded function. These bounds depend only on the stationary
mean E_{\pi}f, the end-points of the support of f, the sample size n and the
second largest eigenvalue \lambda of the transition matrix.

2649. THE TAIL OF THE STATIONARY DISTRIBUTION OF A RANDOM COEFFICIENT AR(Q) MODEL 

Claudia Kluppelberg and Serguei Pergamenchtchikov

  We investigate a stationary random coefficient autoregressive process.
 Using renewal type arguments tailor-made for such processes, we show that the
stationary distribution has a power-law tail. When the model is normal, we show
that the model is in distribution equivalent to an autoregressive process with
ARCH errors. Hence, we obtain the tail behavior of any such model of arbitrary
order.

2650. DIFFUSION APPROXIMATION FOR A PROCESSOR SHARING QUEUE IN HEAVY TRAFFIC 

H. Christian Gromoll

  Consider a single server queue with renewal arrivals and i.i.d. service times
in which the server operates under a processor sharing service discipline.
 To describe the evolution of this system, we use a measure valued process that
keeps track of the residual service times of all jobs in the system at any
given time. From this measure valued process, one can recover the traditional
performance processes, including queue length and workload.
 We show that under mild assumptions, including standard heavy traffic
assumptions, the (suitably rescaled) measure valued processes corresponding to
a sequence of processor sharing queues converge in distribution to a measure
valued diffusion process. The limiting process is characterized as the image
under an appropriate lifting map, of a one-dimensional reflected Brownian
motion.
 As an immediate consequence, one obtains a diffusion approximation for the
queue length process of a processor sharing queue.

2651. PROBABILISTIC ANALYSIS FOR RANDOMIZED GAME TREE EVALUATION 

T\"amur Ali Khan, Ralph Neininger

  We give a probabilistic analysis for the randomized game tree evaluation
algorithm of Snir. We first show that there exists an input such that the
running time, measured as the number of external nodes read by the algorithm,
on that input is maximal in stochastic order among all possible inputs. For
this worst case input we identify the exact expectation of the number of
external nodes read by the algorithm, give the asymptotic order of the variance
including the leading constant, provide a limit law for an appropriate
normalization as well as a tail bound estimating large deviations. Our tail
bound improves upon the exponent of an earlier bound due to Karp and Zhang,
where subgaussian tails were shown based on an approach using multitype
branching processes and Azuma's inequality. Our approach rests on a direct,
inductive estimate of the moment generating function.

2652. INFINITE CANONICAL SUPER-BROWNIAN MOTION AND SCALING LIMITS 

Remco van der Hofstad

  We construct a measure valued Markov process which we call infinite canonical
super-Brownian motion, and which corresponds to the canonical measure of
super-Brownian motion conditioned on non-extinction. Infinite canonical
super-Brownian motion is a natural candidate for the scaling limit of various
random branching objects on $\Z^d$ when these objects are (a) critical; (b)
mean-field and (c) infinite. We prove that ICSBM is the scaling limit of the
spread-out oriented percolation incipient infinite cluster above 4 dimensions
and of incipient infinite branching random walk in any dimension. We conjecture
that it also arises as the scaling limit in various other models above the
upper-critical dimension, such as the incipient infinite lattice tree above 8
dimensions, the incipient infinite cluster for unoriented percolation, uniform
spanning trees above 4 dimensions, and invasion percolation above 6 dimensions.
This paper also serves as a survey of recent results linking super-Brownian to
scaling limits in statistical mechanics.

2653. RADEMACHER PROCESSES AND BOUNDING THE RISK OF FUNCTION LEARNING 

Vladimir Koltchinskii, Dmitry Panchenko

  We construct data dependent bounds on the risk in function learning problems.
The bounds are based on the local norms of the Rademacher process indexed by
the underlying function class and they do not require prior knowledge about the
distribution of the training examples or any specific properties of the
function class.

2654. SOME LOCAL MEASURES OF COMPLEXITY OF CONVEX HULLS AND GENERALIZATION BOUNDS 

Olivier Bousquet, Vladimir Koltchinskii, Dmitry Panchenko

  We investigate measures of complexity of function classes based on continuity
moduli of Gaussian and Rademacher processes. For Gaussian processes, we obtain
bounds on the continuity modulus on the convex hull of a function class in
terms of the same quantity for the class itself. We also obtain new bounds on
generalization error in terms of localized Rademacher complexities. This allows
us to prove new results about generalization performance for convex hulls in
terms of characteristics of the base class. As a byproduct, we obtain a simple
proof of some of the known bounds on the entropy of convex hulls.

2655. A NOTE ON TALAGRAND'S CONCENTRATION INEQUALITY FOR EMPIRICAL PROCESSES 

Dmitry Panchenko

  In this paper we revisit Talagrand's proof of concentration inequality for
empirical processes. We give a different shorter proof of the main technical
lemma that garantees the existence of a certain kernel. Our proof provides the
almost optimal value of the constant involved in the statement of this lemma.

2656. SOME EXTENSIONS OF AN INEQUALITY OF VAPNIK AND CHERVONENKIS 

Dmitry Panchenko

  The inequality of Vapnik and Chervonenkis controls the expectation of the
function by its sample average uniformly over a VC-major class of functions
taking into account the size of the expectation. Using Talagrand's kernel
method we prove a similar result for the classes of functions for which
Dudley's uniform entropy integral or bracketing entropy integral is finite.

2657. EMPIRICAL MARGIN DISTRIBUTIONS AND BOUNDING THE GENERALIZATION ERROR OF COMBINED CLASSIFIERS 

Vladimir Koltchinskii, Dmitry Panchenko

  We prove new probabilistic upper bounds on generalization error of complex
classifiers that are combinations of simple classifiers. Such combinations
could be implemented by neural networks or by voting methods of combining the
classifiers, such as boosting and bagging. The bounds are in terms of the
empirical distribution of the margin of the combined classifier. They are based
on the methods of the theory of Gaussian and empirical processes (comparison
inequalities, symmetrization method, concentration inequalities) and they
improve previous results of Bartlett (1998) on bounding the generalization
error of neural networks in terms of l_1-norms of the weights of neurons and of
Schapire, Freund, Bartlett and Lee (1998) on bounding the generalization error
of boosting. We also obtain rates of convergence in Levy distance of empirical
margin distribution to the true margin distribution uniformly over the classes
of classifiers and prove the optimality of these rates.

2658. BOUNDING THE GENERALIZATION ERROR OF CONVEX COMBINATIONS OF CLASSIFIERS: BALANCING THE DIMENSIONALITY AND THE MARGINS 

Vladimir Koltchinskii, Dmitry Panchenko, Fernando Lozano

  A problem of bounding the generalization error of a classifier f in H, where
H is a "base" class of functions (classifiers), is considered. This problem
frequently occurs in computer learning, where efficient algorithms of combining
simple classifiers into a complex one (such as boosting and bagging) have
attracted a lot of attention. Using Talagrand's concentration inequalities for
empirical processes, we obtain new sharper bounds on the generalization error
of combined classifiers that take into account both the empirical distribution
of "classification margins'' and an "approximate dimension" of the classifiers
and study the performance of these bounds in several experiments with learning
algorithms.

2659. SYMMETRIZATION APPROACH TO CONCENTRATION INEQUALITIES FOR EMPIRICAL PROCESSES 

Dmitry Panchenko

  We introduce a symmetrization technique that allows us to translate a problem
of controlling the deviation of some functionals on a product space from their
mean into a problem of controlling the deviation between two independent copies
of the functional. As an application we give a new easy proof of Talagrand's
concentration inequality for empirical processes, where besides symmetrization
we use only Talagrand's concentration inequality on the discrete cube
{-1,+1}^n. As another application of this technique we prove new
Vapnik-Chervonenkis type inequalities. For example, for VC-classes of functions
we prove a classical inequality of Vapnik and Chervonenkis only with
normalization by the sum of variance and sample variance.

2660. DEVIATION INEQUALITY FOR MONOTONIC BOOLEAN FUNCTIONS WITH APPLICATION TO A NUMBER OF K-CYCLES IN A RANDOM GRAPH 

Dmitry Panchenko

  Using Talagrand's concentration inequality on the discrete cube {0,1}^m we
show that given a real-valued function Z(x)on {0,1}^m that satisfies certain
monotonicity conditions one can control the deviations of Z(x) above its median
by a local Lipschitz norm of Z(x) at the point x. As one application, we give a
simple proof of a nearly optimal deviation inequality for the number of
k-cycles in a random graph.

2661. COMPLEXITIES OF CONVEX COMBINATIONS AND BOUNDING THE GENERALIZATION ERROR IN CLASSIFICATION 

Vladimir Koltchinskii, Dmitry Panchenko

  We introduce and study several measures of complexity of functions from the
convex hull of a given base class. These complexity measures take into account
the sparsity of the weights of a convex combination as well as certain
clustering properties of the base functions involved in it. We prove new upper
confidence bounds on generalization error of ensemble (voting) classification
algorithms that utilize the new complexity measures along with the empirical
distributions of classification margins, providing a better explanation of
generalization performance of large margin classification methods.

2662. BOUNDS FOR DILUTED MEAN-FIELDS SPIN GLASS MODELS 

Dmitry Panchenko, Michel Talagrand

  In an important recent paper, \cite{FL}, S. Franz and M. Leone prove rigorous
lower bounds for the free energy of the diluted $p$-spin model and the $K$-sat
model at any temperature. We show that the results for these two models are
consequences of a single general principle. Our calculations are significantly
simpler than those of \cite{FL}, even in the replica-symmetric case.

2663. A CENTRAL LIMIT THEOREM FOR WEIGHTED AVERAGES OF SPINS IN THE HIGH TEMPERATURE REGION OF THE SHERRINGTON-KIRKPATRICK MODEL 

Dmitry Panchenko

  In this paper we prove that in the high temperature region of the
Sherrington-Kirkpatrick model for a typical realization of the disorder the
weighted average of spins $\sum_{i\leq N} t_i \sigma_i$ will be approximately
Gaussian provided that $\max_{i\leq N}|t_i|/\sum_{i\leq N} t_i^2$ is small.

2664. A NOTE ON THE FREE ENERGY OF THE COUPLED SYSTEM IN THE SHERRINGTON-KIRKPATRICK MODEL 

Dmitry Panchenko

  In this paper we consider a system of spins that consists of two
configurations $\vsi^1,\vsi^2\in\Sigma_N=\{-1,+1\}^N$ with Gaussian
Hamiltonians $H_N^1(\vsi^1)$ and $H_N^2(\vsi^2)$ correspondingly, and these
configurations are coupled on the set where their overlap is fixed
$\{R_{1,2}=N^{-1}\sum_{i=1}^N \sigma_i^1\sigma_i^2 = u_N\}.$ We prove the
existence of the thermodynamic limit of the free energy of this system given
that $\lim_{N\to\infty}u_N = u\in[-1,1]$ and give the analogue of the
Aizenman-Sims-Starr variational principle that describes this limit via random
overlap structures.

2665. FREE ENERGY IN THE SHERRINGTON-KIRKPATRICK MODEL WITH THE CONSTRAINT ON THE AVERAGE OF SPINS 

Dmitry Panchenko

  In his recent paper Michel Talagrand gave a rigorous proof of the Parisi
formula for the free energy of the Sherrington-Kirkpatrick model. In the
present paper we utilize the methodology developed by Talagrand to compute the
thermodynamic limit of the free energy of the set of configurations with the
fixed average of spins $N^{-1}\sum_{i\leq N} \sigma_i = u_N$ as $u_N\to
u\in[-1,1].$ As a corollary we will show that the Gibbs' measure is
concentrated on the configurations whose average of spins belongs to a
neighborhood of a certain set described as a subdifferential of the Parisi
formula.

2666. FREE ENERGY IN THE GENERALIZED SHERRINGTON-KIRKPATRICK MEAN FIELD MODEL 

Dmitry Panchenko

  Recently Michel Talagrand gave a rigorous proof of the Parisi formula in the
Sherrington-Kirkpatrick model. In this paper we build upon the methodology
developed by Talagrand and extend his result to a more general class of mean
field models with spins distributed according to an arbitrary probability
measure on the bounded subset of the real line and with external field term
given by an arbitrary bounded function of the spin.

2667. COEXISTENCE FOR RICHARDSON TYPE COMPETING SPATIAL GROWTH MODELS 

Christopher Hoffman

  We study a large family of competing spatial growth models. In these the
vertices in Z^d can take on three possible states {0,1,2}. Vertices in states 1
and 2 remain in their states forever, while vertices in state 0 which are
adjacent to a vertex in state 1 (or state 2) can switch to state 1 (or state
2). We think of the vertices in states 1 and 2 as infected with one of two
infections while the vertices in state 0 are considered uninfected. In this way
these models are variants of the Richardson model. We start the models with a
single vertex in state 1 and a single vertex is in state 2. We show that with
positive probability state 1 reaches an infinite number of vertices and state 2
also reaches an infinite number of vertices. This extends results and proves a
conjecture of Haggstrom and Pemantle. The key tool is applying the ergodic
theorem to stationary first passage percolation.

2668. PERTE D'INFORMATION DANS LES TRANSFORMATIONS DU JEU DE PILE OU FACE 

Jean Brossard, Christophe Leuridan

  Let $(\epsilon_n)_{n \in {\bf Z}}$ be a sequence of independent Bernoulli
random variables with common law $(\delta_{-1}+\delta_{1})/2$, and $(H_n)_{n
\in {\bf Z}}$ a predictable process (in the natural filtration of
$(\epsilon_n)_{n \in {\bf Z}}$), taking values in $\{-1,1\}$. Then
$(H_n\epsilon_n)_{n \in {\bf Z}}$ is a new heads and tails sequence and its
filtration is included in the filtration of $(\epsilon_n)_{n \in {\bf Z}}$. The
purpose of this paper is to give conditions for the equality of these
filtrations and to describe the loss of information when they are not equal. We
are interseted especially in the homogeneous transformations (that are
transformations commuting with time-translation). We study in great details
homogeneous transformations of finite length, where $H_n$ is a fixed fonction
of $(\epsilon_{n-d},...,\epsilon_{n-1})$.

2669. STRONG APPROXIMATIONS OF THREE-DIMENSIONAL WIENER SAUSAGES 

Endre Cs\'aki, Yueyun Hu

  In this paper we prove that the centered three-dimensional Wiener sausage can
be strongly approximated by a one-dimensional Brownian motion running at a
suitable time clock. The strong approximation gives all possible laws of
iterated logarithm as well as the convergence in law in terms of process for
the normalized Wiener sausage. The proof relies on Le Gall's estimates between
the Wiener sausage and the Brownian intersection local times.

2670. REDUCTIONS OF HIDDEN INFORMATION SOURCES 

Nihat Ay and James P. Crutchfield

  In all but special circumstances, measurements of time-dependent processes
reflect internal structures and correlations only indirectly. Building
predictive models of such hidden information sources requires discovering, in
some way, the internal states and mechanisms. Unfortunately, there are often
many possible models that are observationally equivalent. Here we show that the
situation is not as arbitrary as one would think. We show that generators of
hidden stochastic processes can be reduced to a minimal form and compare this
reduced representation to that provided by computational mechanics--the
epsilon-machine. On the way to developing deeper, measure-theoretic foundations
for the latter, we introduce a new two-step reduction process. The first step
(internal-event reduction) produces the smallest observationally equivalent
sigma-algebra and the second (internal-state reduction) removes sigma-algebra
components that are redundant for optimal prediction. For several classes of
stochastic dynamical systems these reductions produce representations that are
equivalent to epsilon-machines.

2671. ASYMPTOTIC LAWS FOR REGENERATIVE COMPOSITIONS: GAMMA SUBORDINATORS AND THE LIKE 

A. Gnedin, J. Pitman and M. Yor

  For $\widetilde{\cal R} = 1 - \exp(- {\cal R})$ a random closed set obtained
by exponential transformation of the closed range ${\cal R}$ of a subordinator,
a regenerative composition of generic positive integer $n$ is defined by
recording the sizes of clusters of $n$ uniform random points as they are
separated by the points of $\widetilde{\cal R}$. We focus on the number of
parts $K_n$ of the composition when $\widetilde{\cal R}$ is derived from a
gamma subordinator. We prove logarithmic asymptotics of the moments and central
limit theorems for $K_n$ and other functionals of the composition such as the
number of singletons, doubletons, etc. This study complements our previous work
on asymptotics of these functionals when the tail of the L\'evy measure is
regularly varying at $0+$.

2672. ASYMPTOTICS OF A TWO-DIMENSIONAL STICKY RANDOM WALK 

Jean B\'erard

  We study the asymptotic behavior of a Markov chain on $\mathbb{Z}^2$ that
corresponds to the two-dimensional marginals of a reinforcement process on
$\mathbb{Z}^{\mathbb{N}}$. Three distinct asymptotic regimes are identified,
depending on the scaling of the reinforcement parameter $\Delta$ with respect
to the number of steps performed by the chain.

2673. MEMORY LOSS PROPERTY FOR PRODUCTS OF RANDOM MATRICES IN THE $(\MAX,+)$ ALGEBRA 

Glenn Merlet

  Products of random matrices in the $(\max,+)$ algebra are used as a model for
a class of discrete event dynamical systems. J. Mairesse proved that such a
system couples in finite times with a unique stationary regime if and only if
it has a memory loss property. We prove that the memory loss property is
generic in the following sense : if it is not fulfilled, the support of the
measure is included in a finite union of affine hyperplanes and in the discrete
case the atoms of the measure are linearly related.

2674. ENTROPY DISSIPATION ESTIMATES IN A ZERO-RANGE DYNAMICS 

Pietro Caputo and Gustavo Posta

  We prove new inequalities implying exponential decay of relative entropy
functionals for a class of Zero-Range processes on the complete graph. We first
consider the case of uniformly increasing rates, where we use a discrete
version of the Bakry-Emery criterium to prove spectral gap and entropy
dissipation estimates, uniformly over the number of particles and the number of
vertices. We then study the standard case of possibly oscillating but roughly
linearly increasing rates. Here the uniform entropy dissipation estimate is
obtained by an adaptation of the martingale approach.

2675. INVARIANT PERCOLATION AND HARMONIC DIRICHLET FUNCTIONS 

Damien Gaboriau

  The main goal of this paper is to answer question~1.10 and settle
conjecture~1.11 of Benjamini-Lyons-Schramm \cite{BLS99} relating harmonic
Dirichlet functions on a graph to those of the infinite clusters in the
uniqueness phase of Bernoulli percolation. We extend the result to more general
invariant percolations, including the Random-Cluster model. We prove the
existence of the nonuniqueness phase for the Bernoulli percolation (and make
some progress for Random-Cluster model) on unimodular transitive locally finite
graphs admitting nonconstant harmonic Dirichlet functions. This is done by
using the device of $\ell^2$ Betti numbers.

2676. CONVERGENCE OF VALUES IN OPTIMAL STOPPING 

Sandrine Toldo

  Under the hypothesis of convergence in probability of a sequence of
c\`adl\`ag processes $(X^n)_n$ to a c\`adl\`ag process $X$, we are interested
in the convergence of corresponding values in optimal stopping. We give results
under hypothesis of inclusion of filtrations or convergence of filtrations.

2677. ERGODICITY FOR THE STOCHASTIC COMPLEX GINZBURG-LANDAU EQUATIONS 

Cyril Odasso

  We study a stochastic complex Ginzburg--Landau (CGL) equation driven by a
smooth noise in space and we establish exponential convergence of the Markovian
transition semi-group toward a unique invariant probability measure. Since Doob
Theorem does not seem not to be useful in our situation, a coupling method is
used. In order to make this method easier to understand, we first focus on two
simple examples which contain most of the arguments and the essential
difficulties.

2678. MODIFIED LOGARITHMIC SOBOLEV INEQUALITIES AND TRANSPORTATION INEQUALITIES 

Ivan Gentil, Arnaud Guillin, Laurent Miclo

  We present a class of modified logarithmic Sobolev inequality, interpolating
between Poincar\'e and logarithmic Sobolev inequalities, suitable for measures
of the type $\exp(-|x|^\al)$ or more complex $\exp(-|x|^\al\log^\beta(2+|x|))$
($\al\in]1,2[$ and $\be\in\dR$) which lead to new concentration inequalities.
These modified inequalities share common properties with usual logarithmic
Sobolev inequalities, as tensorisation or perturbation, and imply as well
Poincar\'e inequality. We also study the link between these new modified
logarithmic Sobolev inequalities and transportation inequalities.

2679. MODERATE DEVIATIONS FOR NON-LINEAR FUNCTIONALS AND EMPIRICAL SPECTRAL DENSITY OF MOVING AVERAGE PROCESSES 

Hacene Djellout, Arnaud Guillin, Liming Wu

  A moderate deviation principle for functionals, with at most quadratic
growth, of moving average processes is established. The main assumptions on the
moving average process are a Logarithmic Sobolev inequality for the driving
random variables and the continuity, or weaker, of the spectral density of the
moving average process. We also obtain the moderate deviations for the
empirical spectral density, exhibiting an interesting new form of the rate
function, i.e. with a correction term compared to the Gaussian rate
functionnal.

2680. RANDOM WALKS WITH $K$-WISE INDEPENDENT INCREMENTS 

Itai Benjamini, Gady Kozma, Dan Romik

  We construct examples of a random walk with pairwise-independent steps which
is almost-surely bounded, and for any $m$ and $k$ a random walk with $k$-wise
independent steps which has no stationary distribution modulo $m$.

2681. WEAK CONVERGENCE OF POSITIVE SELF-SIMILAR MARKOV PROCESSES AND OVERSHOOTS OF L\'EVY PROCESSES 

Mar\'ia Emilia Caballero and Lo\"ic Chaumont

  Using Lamperti's relationship between L\'evy processes and positive
self-similar Markov processes (pssMp), we study the weak convergence of the law
$\p_x$ of a pssMp starting at $x>0$, in the Skorohod space of c\`adl\`ag paths,
when $x$ tends to 0. To do so, we first give conditions which allow us to
construct a c\`adl\`ag Markov process $X^{(0)}$, starting from 0, which stays
positive and verifies the scaling property. Then we establish necessary and
sufficient conditions for the laws $\p_x$ to converges weakly to the law of
$X^{(0)}$ as $x$ goes to 0. In particular, this answers a question raised by
Lamperti \cite{la} about the Feller property for pssMp at $x=0$.

2682. QUASISTATIONARY DISTRIBUTIONS FOR ONE-DIMENSIONAL DIFFUSIONS WITH KILLING 

David Steinsaltz and Steven N. Evans

  We extend some results on the convergence of one-dimensional diffusions
killed at the boundary, conditioned on extended survival, to the case of
general killing on the interior. We show, under fairly general conditions, that
a diffusion conditioned on long survival either runs off to infinity almost
surely, or almost surely converges to a quasistationary distribution given by
the lowest eigenfunction of the generator. In the absence of internal killing,
only a sufficiently strong inward drift can keep the process close to the
origin, to allow convergence in distribution. An alternative, that arises when
general killing is allowed, is that the conditioned process is held near the
origin by a high rate of killing near infinity. We also extend, to the case of
general killing, the standard result on convergence to a quasistationary
distribution of a diffusion on a compact interval.

2683. SHORT-TERM EQUITY DYNAMICS AND ENDOGENOUS MARKET FLUCTUATIONS 

Ted Theodosopoulos and Muffasir Badshah

  We present a model that investigates the spontaneous emergence of randomness
in equity market microstructure. The phase space analysis of our model imposes
limits to the contemporaneous determination of volume and price momentum, which
serve as canonical conjugate variables. We formulate a control problem for
maximizing price regularity and stability while minimizing entanglement with
the market, representing the NYSE specialists' affirmative obligation to
maintain `fair and orderly markets'.

2684. SELF-SIMILAR CORRECTIONS TO THE ERGODIC THEOREM FOR THE PASCAL-ADIC TRANSFORMATION 

Elise Janvresse, Thierry de la Rue, Yvan Velenik

  Let T be the Pascal-adic transformation. For any measurable function g, we
consider the corrections to the ergodic theorem sum_{k=0}^{j-1} g(T^k x) - j/l
sum_{k=0}^{l-1} g(T^k x). When seen as graphs of functions defined on
{0,...,l-1}, we show for a suitable class of functions g that these quantities,
once properly renormalized, converge to (part of) the graph of a self-affine
function depending only on the ergodic component of x.

2685. CLASSICAL AND FREE INFINITELY DIVISIBLE DISTRIBUTIONS AND RANDOM MATRICES 

Florent Benaych-Georges 

  We construct a random matrix model for the bijection Psi between classical
and free infinitely divisible distributions: for every positive integer d, we
associate in a quite natural way to each classical infinitely divisible law mu
a distribution P(d,mu) on the space of hermitian matrices of size d such that
P(d,mu)*P(d,nu)=P(d,mu*nu). The spectral distribution of a random matrix with
distribution P(d,mu) converges in probability to Psi(mu) when d goes to
infinity. It gives, among other things, a new proof of the almost sure
convergence of the spectral distribution of a matrix of the GUE and a
projection model for the Marchenko-Pastur distribution. In an analogous way,
for every positive integer d, we associate to each classical infinitely
divisible law mu a distribution L(d,mu) on the space of complex (non-hermitian)
random matrices of size d. If mu is symmetric, the symmetrization of the
singular distribution of an L(d,mu)-distributed random matrix, converges in
probability to Psi(mu).

2686. LARGE DEVIATIONS FOR EMPIRICAL ENTROPIES OF GIBBSIAN SOURCES 

J.-R. Chazottes, D. Gabrielli

  The entropy of an ergodic finite-alphabet process can be computed from a
single typical sample path x_1^n using the entropy of the k-block empirical
probability and letting k grow with $n$ roughly like log n. We further assume
that the distribution of the process is a g-measure with respect to a
continuous and regular g-function. We prove large deviation principles for
conditional, non-conditional and relative k(n)-block empirical entropies.

2687. ERGODICITY OF THE 2D NAVIER-STOKES EQUATIONS WITH DEGENERATE STOCHASTIC FORCING 

Martin Hairer and Jonathan C. Mattingly

  The stochastic 2D Navier-Stokes equations on the torus driven by degenerate
noise are studied. We characterize the smallest closed invariant subspace for
this model and show that the dynamics restricted to that subspace is ergodic.
In particular, our results yield a purely geometric characterization of a class
of noises for which the equation is ergodic in L^2 of the torus. Unlike in
previous works, this class is independent of the viscosity and the strength of
the noise. The two main tools of our analysis are the asymptotic strong Feller
property, introduced in this work, and an approximate integration by parts
formula. The first, when combined with a weak type of irreducibility, is shown
to ensure that the dynamics is ergodic. The second is used to show that the
first holds under a Hormander-type condition. This requires some interesting
non-adapted stochastic analysis.

2688. BAYES THEOREM AND THE CMPE-METHOD: DIFFERENCES, COMPLEMENTARITIES AND THE IMPORTANCE OF DISCERNING BETWEEN WEIGHT-BEARING AND EXTENSIONAL EVIDENCE 

R. Gottlob

  Both, Bayes Theorem and the cMPE-Method serve for establishing relations
between systems of probabilities. By the cMPE-Method non-conditional
probabilities are added, by the DPE-Method, they are subtracted, however, in
both versions allowing for the non-linearity of non-disjunctive probabilities.
Semantic independence is prerequisite. As compared with the results of
semantically homogeneous series of observations, the variety of evidence
permits arrival at higher probabilities. The advantage of the Bayesian method
lies in allowing for evidence extraneous to the domain covered by the
hypothesis. We must differentiate between extensional and weight-bearing
evidence. Operations based on purely weight-bearing evidence (cMPE-Method)
neglect the extensional evidence and some operations according to Bayes Theorem
may neglect weight-bearing evidence at least partially. These and some other
shortcomings may be remedied by operations, combining both of the approaches.

2689. MERGING COSTS FOR THE ADDITIVE MARCUS-LUSHNIKOV PROCESS, AND UNION-FIND ALGORITHMS 

Philippe Chassaing, Regine Marchand

  Starting with a monodisperse configuration with $n$ size-1 particles, an
additive Marcus-Lushnikov process evolves until it reaches its final state (a
unique particle with mass $n$). At each of the $n-1$ steps of its evolution, a
merging cost is incurred, that depends on the sizes of the two particles
involved, and on an independent random factor. This paper deals with the
asymptotic behaviour of the cumulated costs up to the $k$th clustering, under
various regimes for $(n,k)$, with applications to the study of Union--Find
algorithms.

2690. POISSON HYPOTHESIS FOR INFORMATION NETWORKS (A STUDY IN NON-LINEAR MARKOV PROCESSES) I. DOMAIN OF VALIDITY 

A. Rybko, S. Shlosman

  In this paper we study the Poisson Hypothesis, which is a device to analyze
approximately the behavior of large queueing networks. We prove it in some
simple limiting cases. We show in particular that the corresponding dynamical
system, defined by the non-linear Markov process, has a line of fixed points
which are global attractors. To do this we derive the corresponding non-linear
equation and we explore its self-averaging properties. We also argue that in
cases of havy-tail service times the PH can be violated.

2691. AN ASYMPTOTIC LOG-FOURIER INTERPRETATION OF THE R-TRANSFORM 

Alice Guionnet and Mylene Maida

  We estimate the asymptotics of spherical integrals when the rank of one
matrix is finite. We show that it is given in terms of the R-transform of the
spectral measure of the full rank matrix and give a new proof of the fact that
the R-transform is additive under free convolution. These asymptotics also
extend to the case where one matrix has rank one but complex eigenvalue.

2692. RANDOM OXFORD GRAPHS 

Jonah Balsiak and Rick Durrett

  Inspired by a concept in comparative genomics, we investigate properties of
randomly chosen members of G_1(m,n,t), the set of bipartite graphs with $m$
left vertices, n right vertices, t edges, and each vertex of degree at least
one. We give asymptotic results for the number of such graphs and the number of
$(i,j)$ trees they contain. We compute the thresholds for the emergence of a
giant component and for the graph to be connected.

2693. SYMMETRIC MEASURES VIA MOMENTS 

Alexey Koloydenko

  A finite $G\le GL(m,\mathbb{R})$ fixes $\Omega \subset \mathbb{R}^m$ and
induces its action on $\mathcal{P}$, the set of probability distributions on
$\Omega$. $\mathcal{P}^G$ is the set of distributions invariant under this
action. We consider models based on $\mathcal{P}^G$. Ignoring the invariance, a
common approach to modeling $P\in\mathcal{P}$ is to progressively match its
moments. Among all distributions with a requested match, one reasonable choice
is $P'$ that maximizes the entropy $H(P')$. Matching in the limit all the
moments guarantees convergence to $P$ if $P$ is uniquely determined by its
moments. We generalize ordinary determinacy to determinacy within
$\mathcal{P}^G$ and prove sufficiency of $G$-invariant moments for the latter.
Using generators of $G$-invariant polynomials, we also give several sufficient
conditions for the generalized property to hold. For applications, we propose a
sequential procedure with adaptive convergence toward $P$. The procedure
combines with one's favorite statistical model selection principle, and we
present two such examples. We also describe a distribution of small subimages
extracted from a large database of natural images, and compute generators for
the relevant invariance. We discuss computations of $G$-invariant probability
distributions. For example, concerned with computational efficiency, we lift
the invariantly constrained entropy maximization problem to an appropriate
quotient space of ``lower dimension''.

2694. COALESCENCE IN A RANDOM BACKGROUND 

N. H. Barton, A. M. Etheridge and A. K. Sturm

  We consider a single genetic locus which carries two alleles, labelled
 P and Q. This locus experiences selection and mutation. It is linked to a
second neutral locus with recombination rate r. If r=0, this reduces to the
study of a single selected locus. Assuming a Moran model for the population
dynamics, we pass to a diffusion approximation and, assuming that the allele
frequencies at the selected locus have reached stationarity, establish the
joint generating function for the genealogy of a sample from the population and
the frequency of the P allele. In essence this is the joint generating function
for a coalescent and the random background in which it evolves. We use this to
characterize, for the diffusion approximation, the probability of identity in
state at the neutral locus of a sample of two individuals (whose type at the
selected locus is known) as solutions to a system of ordinary differential
equations. The only subtlety is to find the boundary conditions for this
system. Finally, numerical examples are presented that illustrate the accuracy
and predictions of the diffusion approximation. In particular, a comparison is
made between this approach and one in which the frequencies at the selected
locus are estimated by their value in the absence of fluctuations and a
classical structured coalescent model is used.

2695. EXACT ASYMPTOTICS FOR FLUID QUEUES FED BY MULTIPLE HEAVY-TAILED ON-OFF FLOWS 

Bert Zwart, Sem Borst and Michel Mandjes

  We consider a fluid queue fed by multiple On-Off flows with heavy-tailed
 (regularly varying) On periods. Under fairly mild assumptions, we prove that
the workload distribution is asymptotically equivalent to that in a reduced
system. The reduced system consists of a ``dominant'' subset of the flows, with
the original service rate subtracted by the mean rate of the other flows. We
describe how a dominant set may be determined from a simple knapsack
formulation. The dominant set consists of a ``minimally critical'' set of
On-Off flows with regularly varying On periods. In case the dominant set
contains just a single On-Off flow, the exact asymptotics for the reduced
system follow from known results. For the case of several
 On-Off flows, we exploit a powerful intuitive argument to obtain the exact
asymptotics. Combined with the reduced-load equivalence, the results for the
reduced system provide a characterization of the tail of the workload
distribution for a wide range of traffic scenarios.

2696. LARGE DEVIATIONS PROBLEMS FOR STAR NETWORKS: THE MIN POLICY 

Franck Delcoigne and Arnaud de La Fortelle

  We are interested in analyzing the effect of bandwidth sharing for
telecommunication networks. More precisely, we want to calculate which routes
are bottlenecks by means of large deviations techniques. The method is
illustrated in this paper on a star network, where the bandwidth is shared
between customers according to the so-called min policy. We prove a sample path
large deviation principle for a rescaled process n^{-1}Q_{nt}, where Q_t
represents the joint number of connections at time t. The main result is to
compute the rate function explicitly. The major step consists in deriving large
deviation bounds for an empirical generator constructed from the join number of
customers and arrivals on each route. The rest of the analysis relies on a
suitable change of measure together with a localization procedure. An example
shows how this can be used practically.

2697. A LOCAL LIMIT THEOREM FOR RANDOM WALKS CONDITIONED TO STAY POSITIVE 

Francesco Caravenna

  We consider a random walk $S_n = X_1 + ... + X_n$, where $X_k \sim X$ are
i.i.d. random variables with $E[X]=0$ and $E[X^2]=1$. Let $Z_n^+$ be the random
variable $S_n / \sqrt{n}$ conditioned on the event $C_n := \{S_1 > 0, ..., S_n
> 0 \}$; from a general result it follows that the sequence $Z_n^+$ converges
weakly to the $t=1$ marginal $Z^+$ of the Brownian meander process. In this
paper we obtain a local refinement of this result: assuming that the step $X$
has an absolutely continuous law and that for some $n_0$ the density of
$S_{n_0}$ is bounded (the same hypothesis of the classical Local Limit
Theorem), we prove that the density of $Z_n^+$ converges uniformly to the
density of $Z^+$. Unlike the standard proof of the classical LLT, we make no
use of characteristic functions, since conditionally on $C_n$ the steps $\{X_k
\}$ are no more independent; our techniques are rather taken from the so-called
fluctuation theory for random walks.

2698. HITTING PROBABILITIES IN A MARKOV ADDITIVE PROCESS WITH LINEAR MOVEMENTS AND UPWARD JUMPS: APPLICATIONS TO RISK AND QUEUEING PROCESSES 

Masakiyo Miyazawa

  Motivated by a risk process with positive and negative premium rates, we
consider a real-valued Markov additive process with finitely many background
states. This additive process linearly increases or decreases while the
background state is unchanged, and may have upward jumps at the transition
instants of the background state. It is known that the hitting probabilities of
this additive process at lower levels have a matrix exponential form.
 We here study the hitting probabilities at upper levels, which do not have a
matrix exponential form in general. These probabilities give the ruin
probabilities in the terminology of the risk process. Our major interests are
in their analytic expressions and their asymptotic behavior when the hitting
level goes to infinity under light tail conditions on the jump sizes. To derive
those results, we use a certain duality on the hitting probabilities, which may
have an independent interest because it does not need any Markovian assumption.

2699. THE ASYMPTOTIC DISTRIBUTIONS OF THE LARGEST ENTRIES OF SAMPLE CORRELATION MATRICES 

Tiefeng Jiang

  Let X_n=(x_{ij}) be an n by p data matrix, where the n rows form a random
sample of size n from a certain p-dimensional population distribution.
  Let R_n=(\rho_{ij}) be the p\times p sample correlation matrix of X_n; that
is, the entry \rho_{ij} is the usual Pearson's correlation coefficient between
the ith column of X_n and jth column of X_n. For contemporary data both n and p
are large. When the population is a multivariate normal we study the test that
H_0: the p variates of the population are uncorrelated.
  A test statistic is chosen as L_n=max_{i\ne j}|\rho_{ij}|. The asymptotic
distribution of L_n is derived by using the Chen-Stein Poisson approximation
method. Similar results for the non-Gaussian case are also derived.

2700. SLAB PERCOLATION AND PHASE TRANSITIONS FOR THE ISING MODEL 

Emilio De Santis, Rossella Micieli

  We prove, using the random-cluster model, a strict inequality between site
percolation and magnetization in the region of phase transition for the
d-dimensional Ising model, thus improving a result of [CNPR76]. We extend this
result also at the case of two plane lattices Z^2x{0,1} (slabs) and give a
characterization of phase transition in this case. The general case of N slabs,
with N an arbitrary positive integer, is partially solved and it is used to
show that this characterization holds in the case of three slabs with periodic
boundary conditions. However in this case we do not obtain useful inequalities
between magnetization and percolation probability.

2701. POWER LAWS FOR FAMILY SIZES IN A DUPLICATION MODEL 

Rick Durrett and Jason Schweinsberg

  Qian, Luscombe, and Gerstein (2001) introduced a model of the diversification
of protein folds in a genome that we may formulate as follows. Consider a
multitype Yule process starting with one individual in which there are no
deaths and each individual gives birth to a new individual at rate one. When a
new individual is born, it has the same type as its parent with probability 1 -
r and is a new type, different from all previously observed types, with
probability r. We refer to individuals with the same type as families and
provide an approximation to the joint distribution of family sizes when the
population size reaches N. We also show that if 1 << S << N^{1-r}, then the
number of families of size at least S is approximately CNS^{-1/(1-r)}, while if
N^{1-r} << S the distribution decays more rapidly than any power.

2702. CENTRAL LIMIT THEOREM AND CONVERGENCE TO STABLE LAWS IN MALLOWS DISTANCE 

Oliver Johnson and Richard Samworth

  We give a new proof of the classical Central Limit Theorem, in the Mallows
($L^r$-Wasserstein) distance. Our proof is elementary in the sense that it does
not require complex analysis, but rather makes use of a simple subadditive
inequality related to this metric. The key is to analyse the case where
equality holds. We provide some results concerning rates of convergence. We
also consider convergence to stable distributions, and obtain a bound on the
rate of such convergence.

2703. INTERMITTENCY IN A CATALYTIC RANDOM MEDIUM 

J. G\"artner and F. den Hollander

  In this paper we study intermittency for the parabolic Anderson equation
$\partial u/\partial t = \kappa\Delta u + \xi u$, where $u\colon \Z^d\times
[0,\infty)\to\R$, $\kappa$ is the diffusion constant, $\Delta$ is the discrete
Laplacian, and $\xi\colon \Z^d\times [0,\infty)\to\R$ is a space-time random
medium. We focus on the case where $\xi$ is $\gamma$ times the random medium
that is obtained by running independent simple random walks with diffusion
constant $\rho$ starting from a Poisson random field with intensity $\nu$. The
solution of the equation describes the evolution of a ``reactant'' $u$ under
the influence of a ``catalyst'' $\xi$.
  We consider the annealed Lyapunov exponents, i.e., the exponential growth
rates of the successive moments of $u$, and show that they display an
interesting dependence on the dimension $d$ and on the parameters $\kappa$ and
$\gamma,\rho,\nu$, with qualitatively different intermittency behavior in
$d=1,2$, in $d=3$ and in $d\geq 4$. Special attention is given to the
asymptotics of these Lyapunov exponents for $\kappa\downarrow 0$ and $\kappa
\to\infty$.

2704. LIMIT THEOREMS FOR SEQUENCES OF RANDOM TREES 

David Balding, Pablo A. Ferrari, Ricardo Fraiman, Mariela Sued

  We consider a random tree and introduce a metric in the space of trees to
define the ``mean tree'' as the tree minimizing the average distance to the
random tree. When the resulting metric space is compact we show laws of large
numbers and central limit theorems for sequence of independent identically
distributed random trees. As application we propose tests to check if two
samples of random trees have the same law.

2705. COMPETITION INTERFACES AND SECOND CLASS PARTICLES 

Pablo A. Ferrari, Leandro P. R. Pimentel

  The one-dimensional nearest neighbor totally asymmetric simple exclusion
process can be constructed in the same space as a last-passage percolation
problem in the positive integer quadrant. We show that the trajectory of a
second class particle in the exclusion process can be mapped into the interface
of a competition spatial growth interface in last-passage percolation. Using
technology built up for geodesics in percolation, we show that the competition
interface converges almost surely to an asymptotic random direction. As a
consequence we get a new proof for the strong law of large numbers for the
second class particle in the rarefaction fan for the exclusion process and
describe the distribution of the asymptotic angle of the competition spatial
growth interface.

2706. BALLS-IN-BOXES DUALITY FOR COALESCING RANDOM WALKS AND COALESCING BROWNIAN MOTIONS 

Steven N. Evans and Xiaowen Zhou

  We present a duality relation between two systems of coalescing random walks
and an analogous duality relation between two systems of coalescing Brownian
motions. Our results extends previous work in the literature and we apply it to
the study of a system of coalescing Brownian motions with Poisson immigration.

2707. A THINNING ANALOGUE OF DE FINETTI'S THEOREM 

Shannon Starr 

  We consider a notion of uniform thinning for a finite sequence of random
variables $(X_1,...,X_n)$ obtained by removing one random variable, uniformly
at random. If a triangular array of random variables $(X_{n,k} : n \in
\mathbb{N}_+, 1 \le k \le n)$ satisfies that the law of $(X_{n,1},...,X_{n,n})$
is obtained by uniformly thinning $(X_{n+1,1},...,X_{n+1,n+1})$, then we call
the array thinning-invariant. We give a representation for the Choquet simplex
of all thinning-invariant triangular arrays of random variables, when all
random variables take values in a compact metric space (with Borel measurable
distributions). We give two applications: to long-ranged, asymmetric classical
spin chains, and long-ranged, asymmetric simple exclusion processes.

2708. GRAPH DIAMETER IN LONG-RANGE PERCOLATION 

Marek Biskup

  We study the asymptotic growth of the diameter of the graph obtained by
adding sparse "long" edges to a square box in $Z^{d}$. We focus on the cases
when an edge between $x$ and $y$ is added with probability decaying with their
Euclidean distance like $|x-y|^{-s+o(1)}$ as $|x-y|$ tends to infinity. For $s$
between $d$ and 2d we show that the graph diameter for a box of side $L$ scales
like (log$L$)^{Delta+o(1)} where $Delta^{-1}$=log_{2}$(2d/s)$. In other
words, the diameter grows about as fast as the graph distance between two
"typical" points in the box.

2709. LEVEL CROSSING PROBABILITIES I: ONE-DIMENSIONAL RANDOM WALKS AND SYMMETRIZATION 

Rainer Siegmund-Schultze, Heinrich von Weizsaecker

  We prove for an arbitrary one-dimensional random walk with independent
increments that the probability of crossing a level at a given time n has the
order of square root of n. Moment or symmetry assumptions are not necessary. In
removing symmetry the (sharp) inequality P(|X+Y| <= 1) < 2 P(|X-Y| <= 1) for
independent identically distributed X,Y is used. In part II we shall discuss
the connection of this result to 'polygonal recurrence' of higher-dimensional
walks and some conjectures on directionally random walks in the sense of
Mauldin, Monticino and v.Weizsaecker [4].

2710. DIFFUSION LOCAL TIME STORAGE 

M. Kozlova and P. Salminen

  In this paper we study a storage process or a liquid queue in which the input
process is the local time of a positively recurrent stationary diffusion in
stationary state and the potential output takes place with a constant
deterministic rate. For this storage process we find its stationary
distribution and compute the joint distribution of the starting and ending
times of the busy and idle periods. This work completes and extends to a more
general setting the results in Mannersalo, Norros, and Salminen (2003).

2711. LEVEL CROSSING PROBABILITIES II: POLYGONAL RECURRENCE OF MULTIDIMENSIONAL RANDOM WALKS 

Rainer Siegmund-Schultze, Heinrich von Weizsaecker

  In part I (math.PR/0406392) we proved for an arbitrary one-dimensional random
walk with independent increments that the probability of crossing a level at a
given time n is of the maximal order square root of n. In higher dimensions we
call a random walk 'polygonally recurrent' (resp. transient) if a.s. infinitely
many (resp. finitely many) of the straight lines between two consecutive sites
hit a given bounded set. The above estimate implies that three-dimensional
random walks with independent components are polygonally transient. Similarly a
directionally reinforced random walk on Z^3 in the sense of Mauldin, Monticino
and v.Weizsaecker [1] is transient. On the other hand we construct an example
of a transient but polygonally recurrent random walk with independent
components on Z^2.

2712. LEVY PROCESSES: CAPACITY AND HAUSDORFF DIMENSION 

Davar Khoshnevisan and Yimin Xiao

  We use the theory of additive Levy processes to establish connections between
an arbitrary Levy process $X$ in ${\bf R}^d$, and a new class of energy forms
and capacities. We apply these connections to solve two long-standing problems
in the folklore of the theory of Levy processes.

2713. SURVEY: INFORMATION FLOW ON TREES 

Elchanan Mossel

  Consider a tree network T, where each edge acts as an independent copy of a
given channel M, and information is propagated from the root. For which T and M
does the configuration obtained at level n of T typically contain significant
information on the root variable?
  This model appeared independently in biology, information theory, and
statistical physics. Its analysis uses techniques from the theory of finite
markov chains, statistics, statistical physics, information theory,
cryptography and noisy computation. In this paper, we survey developments and
challenges related to this problem.

2714. ROBUST RECONSTRUCTION ON TREES IS DETERMINED BY THE SECOND EIGENVALUE 

Svante Janson and Elchanan Mossel

  In this paper we study the perturbative theory of reconstruction on trees,
and show how it depends on the spectrum of the underlying Markov chain. In
particular, we show that the threshold for ``robust reconstruction'' for the
$B$-ary tree is $B |\lam_2(M)|^2 = 1$, where $\lam_2(M)$ denotes the eigenvalue
of $M$ which is the second largest in absolute value. We prove a similar
threshold for general bounded degree trees, where $B$ is replaced by the
branching number of the tree $\br(T)$.

2715. A DEFINITION AND SOME CHARACTERISTIC PROPERTIES OF PSEUDO-STOPPING TIMES 

Ashkan Nikeghbali and Marc Yor

  Recently, D. Williams \cite{williams} gave an explicit example of a random
time $\rho $ associated with Brownian motion such that $\rho $ is not a
stopping time but $\mathbb{E}M_{\rho}=\mathbb{E}M_{0}$ for every bounded
martingale $M$. The aim of this paper is to give some characterizations for
such random times, which we call pseudo-stopping times, and to construct
further examples, using techniques of progressive enlargements of filtrations.

2716. RECURRENT GRAPHS WHERE TWO INDEPENDENT RANDOM WALKS COLLIDE FINITELY OFTEN 

Manjunath Krishnapur and Yuval Peres

  We present a class of graphs where simple random walk is recurrent, yet two
independent walkers meet only finitely many times almost surely. In particular,
the comb lattice, obtained from Z^2 by removing all horizontal edges off the
X-axis, has this property. We also conjecture that the same property holds for
some other graphs, including the incipient infinite cluster for critical
percolation in Z^2.

2717. COIN FLIPPING FROM A COSMIC SOURCE: ON ERROR CORRECTION OF TRULY RANDOM BITS 

Elchanan Mossel and Ryan O'Donnell

  We study a problem related to coin flipping, coding theory, and noise
sensitivity. Consider a source of truly random bits $x \in \bits^n$, and $k$
parties, who have noisy versions of the source bits $y^i \in \bits^n$, where
for all $i$ and $j$, it holds that $\Pr[y^i_j = x_j] = 1 - \eps$, independently
for all $i$ and $j$. That is, each party sees each bit correctly with
probability $1-\epsilon$, and incorrectly (flipped) with probability
$\epsilon$, independently for all bits and all parties. The parties, who cannot
communicate, wish to agree beforehand on {\em balanced} functions $f_i :
\bits^n \to \bits$ such that $\Pr[f_1(y^1) = ... = f_k(y^k)]$ is maximized. In
other words, each party wants to toss a fair coin so that the probability that
all parties have the same coin is maximized. The functions $f_i$ may be thought
of as an error correcting procedure for the source $x$.
  When $k=2,3$ no error correction is possible, as the optimal protocol is
given by $f_i(x^i) = y^i_1$. On the other hand, for large values of $k$, better
protocols exist. We study general properties of the optimal protocols and the
asymptotic behavior of the problem with respect to $k$, $n$ and $\eps$. Our
analysis uses tools from probability, discrete Fourier analysis, convexity and
discrete symmetrization.

2718. A LAW OF LARGE NUMBERS FOR WEIGHTED MAJORITY 

Olle Haggstrom and Gil Kalai and Elchanan Mossel

  Consider an election between two candidates in which the voters' choices are
random and independent and the probability of a voter choosing the first
candidate is $p>1/2$. Condorcet's Jury Theorem which he derived from the weak
law of large numbers asserts that if the number of voters tends to infinity
then the probability that the first candidate will be elected tends to one. The
notion of influence of a voter or its voting power is relevant for extensions
of the weak law of large numbers for voting rules which are more general than
simple majority. In this paper we point out two different ways to extend the
classical notions of voting power and influences to arbitrary probability
distributions. The extension relevant to us is the ``effect'' of a voter, which
is a weighted version of the correlation between the voter's vote and the
election's outcomes. We prove an extension of the weak law of large numbers to
weighted majority games when all individual effects are small and show that
this result does not apply to any voting rule which is not based on weighted
majority.

2719. UNIQUENESS OF MAXIMAL ENTROPY MEASURE ON ESSENTIAL SPANNING FORESTS 

Scott Sheffield

  An essential spanning forest of an infinite graph G is a spanning forest of G
in which all trees have infinitely many vertices. Let G_n be an increasing
sequence of finite connected subgraphs of G whose union is G. Pemantle's
arguments (1991) imply that the uniform measures on spanning trees of G_n
converge weakly to an Aut(G)-invariant measure mu_G on essential spanning
forests of G. We show that if G is a connected, amenable graph and Gamma a
subgroup of Aut(G) that acts quasi-transitively on G, then mu_G is the unique
Gamma-invariant measure on essential spanning forests of G for which the
specific entropy is maximal.
  This result originated with Burton and Pemantle (1993), who gave a short but
incorrect proof in the case that Gamma is isomorphic to Z^d. Lyons discovered
the error (2002) and asked about the more general statement that we prove.

2720. BIDE - SIDE EXPONENTIAL AND MOMENT INEQUALITIES FOR TAILS OF DISTRIBUTIONS OF POLYNOMIAL MARTINGALES 

Eugene Ostrovsky

  In this paper non-asymptotic exponential estimates are derived for the tail
distribution of polynomial martingale differences in terms unconditional tails
distributions of summands. Applications are considered in the theory of
polynomials on independent random variables, to the theory of U-statistics,
multiply martingale series and in the theory of weak compactness measures on
the Banach spaces. Partially supported by the Israel Ministry of Absorbtion
Mathematics Subject Classification (2000): 47A45, 47B10, 60F10, 60G42.

2721. EXPONENTIAL ORLICZ SPACES: NEW NORMS AND APPLICATIONS 

Eugene Ostrovsky

  The aim of this paper is investigating of Orlicz spaces with exponential
function and correspondence Orlicz norm: we introduce some new equivalent
norms, obtain the tail characterization, study the product of functions in
Orlicz spaces etc. We consider some applications: estimation of operators in
Orlicz spaces and problem of martingales convergence and divergence

2722. UNIVERSAL ADAPTIVE ESTIMATIONS AND CONFIDENCE INTERVALS IN THE NONPARAMETRIC STATISTICS 

Eugene Ostrovsky and Leonid Sirota

  The paper considers so-called adaptive estimations of regression,
distribution density and spectral density of a Gaussian stationary sequence,
asymptotically optimal in order at a growing number of observation on any
regular subspace compactly embedded in space $L_2$, and confidence intervals,
also adaptive, are constructed on their basis for the estimated functions in an
integral norm.

2723. BROWNIAN SHEET AND QUASI-SURE ANALYSIS 

Davar Khoshnevisan

  We present a self-contained and modern survey of some existing quasi-sure
results via the connection to the Brownian sheet. Among other things, we prove
that quasi-every continuous function: (i) satisfies the local law of the
iterated logarithm; (ii) has Levy's modulus of continuity for Brownian motion;
(iii) is nowhere differentiable; and (iv) has a nontrivial quadratic variation.
We also present a hint of how to extend (iii) to obtain a quasi-sure refinement
of the M. Csorgo--P. Revesz modulus of continuity for almost every continuous
function along the lines suggested by M. Fukushima.

2724. PRODUCT OF RANDOM PROJECTIONS, JACOBI ENSEMBLES AND UNIVERSALITY PROBLEMS ARISING FROM FREE PROBABILITY 

Benoit Collins

  We consider the product of two independent randomly rotated projectors. The
square of its radial part turns out to be distributed as a Jacobi ensemble. We
study its global and local properties in the large dimension scaling relevant
to free probability theory. We establish asymptotics for one point and two
point correlation functions, as well as properties of largest and smallest
eigenvalues.

2725. HARNESSES, LEVY BRIDGES AND MONSIEUR JOURDAIN 

Roger Mansuy, Marc Yor

  Relations between so-called harness processes and initial enlargements of the
filtration of a Levy process with its positions at fixed times are
investigated.

2726. CONVERGENCE OF THE EMPIRICAL PROCESS IN MALLOWS DISTANCE, WITH AN APPLICATION TO BOOTSTRAP PERFORMANCE 

Richard Samworth and Oliver Johnson

  We study the rate of convergence of the Mallows distance between the
empirical distribution of a sample and the underlying population. The
surprising feature of our results is that the convergence rate is slower in the
discrete case than in the absolutely continuous setting. We show how the hazard
function plays a significant role in these calculations. As an application, we
recall that the quantity studied provides an upper bound on the distance
between the bootstrap distribution of a sample mean and its true sampling
distribution. Moreover, the convenient properties of the Mallows metric yield a
straightforward lower bound, and therefore a relatively precise description of
the asymptotic performance of the bootstrap in this problem.

2727. A NEW MAXIMAL INEQUALITY AND INVARIANCE PRINCIPLE FOR STATIONARY SEQUENCES 

Magda Peligrad, Sergey Utev

  We derive a new maximal inequality for stationary sequences under a
martingale-type condition introduced by Maxwell and Woodroofe (2000). Then, we
apply it to establish the Donsker invariance principle for this class of
stationary sequences. A Markov chain example is given in order to show the
optimality of the conditions imposed.

2728. EXTREMES OF THE DISCRETE TWO-DIMENSIONAL GAUSSIAN FREE FIELD 

Olivier Daviaud

  We consider the lattice version of the free field in two dimensions and study
the fractal structure of the sets where the field is unusually high (or low).
We then extend some of our computations to the case of the free field
conditioned on being everywhere non negative. For example we compute the width
of the largest downward spike of a given length. Through the prism of these
results, we find that the extrema of the free field under entropic repulsion
(minus its mean) and those of the unconditioned free field are identical.
Finally, when compared to previous results these findings reveal a suggestive
analogy between the square of the free field and the two-dimensional simple
random walk on the discrete torus.

2729. GENEALOGICAL PARTICLE ANALYSIS OF RARE EVENTS 

Pierre Del Moral, and Josselin Garnier

In this paper an original interacting particle system 
approach is developed for studying Markov chains in rare event regimes. 
The proposed particle system is theoretically studied through a 
genealogical tree interpretation of Keynman-Kac path measures. 
The algorithmic implementation  of the particle system is presented. 
An efficient estimator for the probability of ocurrence of a rare event 
is proposed and its variance is computed. 
Applications and numerical implementations are discussed. 
First, we apply the particle system technique  
to a toy model (a Gaussian random walk), 
which permits to illustrate the theoretical predictions.  
Second, we address a physically relevant problem consisting in  
the estimation of the outage probability  
due to polarization-mode dispersion in optical fibers.

delmoral@cict.fr  garnier@cict.fr

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

2730. THE `HOT SPOTS' PROBLEM IN PLANAR DOMAINS WITH ONE HOLE 

Krzysztof Burdzy

There exists a planar domain with piecewise
smooth boundary and one hole such that the second
eigenfunction for the Laplacian with Neumann boundary
conditions attains its maximum and minimum inside the domain.

burdzy@math.washington.edu

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

2731. SPATIAL COUPLING OF NEUTRAL MEASURE-VALUED POPULATION MODELS 

Siva Athreya and Anita Winter

In this article we discuss spatial  
couplings for measure-valued population
 models which have a particle
representation. We show that provided 
the  corresponding genealogical trees are 
compact the qualitative behavior of  a coupling of a
particle's individual motion  translates 
into a coupling of the continuous mass 
measure-valued models. As applications of 
the above method we present a coupling of
diffusions on $\R_{+}^n$ and a perturbation 
estimate for a class of semilinear partial 
differential equations.

athreya@isid.ac.in  winter@mi.uni-erlangen.de

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

2732. ASYMPTOTIC AND INCREASING PROPAGATION-OF-CHAOS EXPANSIONS FOR GENEALOGICAL PARTICLE MODELS 

Pierre Del Moral, Arnaud Doucet and Gareth W.  Peters

This article is concerned with the propagation-of-chaos properties of 
genetic type particle models. This class of models arises in a variety of 
scientific disciplines including theoretical physics, macromolecular biology,
engineering sciences, and more particularly in advanced signal processing.
From the pure mathematical point of view, these interacting particle systems
can be regarded as a mean field particle interpretation of a class of 
Feynman-Kac measures on path spaces. 
 
In the present article, we design an original integration theory of 
propagation-of-chaos based on the fluctuation analysis of a class of 
interacting particle random fields. We provide analytic functional 
representations of the asymptotic distributions of finite particle blocks, 
yielding what seems to be the first result of this kind for this class of 
interacting particle systems. These asymptotic expansions are expressed 
in terms of the limiting Feynman-Kac semigroups and a class of interacting
jump operators. These results provide both sharp estimates of the negligible
bias introduced by the interaction mechanisms, and central limit theorems 
for nondegenerate  U-statistics and von Mises statistics associated with 
genealogical tree models. Applications to nonlinear filtering problems and 
interacting Markov chain Monte Carlo algorithms are discussed. 

delmoral@cict.fr

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

2733. MASS EXTINCTIONS: AN ALTERNATIVE TO THE ALLEE EFFECT 

Rinaldo B. Schinazi

We introduce a spatial stochastic process on
the lattice $\ZZ^d$ to model mass extinctions. 
Each site of the lattice may host a flock of 
up to $N$ individuals. Each individual may give 
birth to a new individual at the same site at 
rate $\phi$ until the maximum of $N$ individuals 
has been reached at the site. Once the flock 
reaches N individuals then, and only then, 
it starts giving birth on each of the $2d$ 
neighboring sites at rate $\lambda(N)$. 
Finally, disaster strikes at rate 1, that is, 
the whole flock disappears. Our model shows that, 
at least in theory, there is a critical maximum
flock size above which a species is certain to 
disappear and below which it may survive.

schinazi@math.uccs.edu

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

2734. POWER LAWS FOR FAMILY SIZES IN A DUPLICATION MODEL 

Rick Durrett and Jason Schweinsberg

Qian, Luscombe, and Gerstein (2001) introduced a model
of the diversification of protein folds in a genome that
we may formulate as follows.  Consider a multitype Yule
process starting with one individual in which there are no
deaths and each individual gives birth to a new individual
at rate one.  When a new individual is born, it has the same
type as its parent with probability 1 - r and is a new type,
different from all previously observed types, with
probability r.  We refer to individuals with the same type
as families and provide an approximation to the joint
distribution of family sizes when the population size
reaches N.  We also show that if 1 << S << N^{1-r}, then
the number of families of size at least S is approximately
CNS^{-1/(1-r)}, while if N^{1-r} << S, the distribution
decays more rapidly than any power.

jasonsch@math.cornell.edu   rtd1@cornell.edu

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

2735. CHARACTERIZATION OF SUB-GAUSSIAN HEAT KERNEL ESTIMATES ON STRONGLY RECURRENT GRAPHS 

Martin T. Barlow, Thierry Coulhon and Takashi Kumagai

Sub-Gaussian estimates for random walks are typical of fractal graphs. 
We characterize them in the strongly recurrent case, in terms of resistance estimates only, 
without assuming elliptic Harnack inequalities.

barlow@math.ubc.ca  Thierry.Coulhon@math.u-cergy.fr  kumagai@kurims.kyoto-u.ac.jp

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

2736. WORKLOAD REDUCTION OF A GENERALIZED BROWNIAN NETWORK 

J. M. Harrison and R. J. Williams

We consider a dynamic control problem associated with a
generalized Brownian network, the objective being to
minimize expected discounted cost over an infinite planning
horizon. In this Brownian control problem (BCP), both the
system manager's control and the associated cumulative cost
process may be locally of unbounded variation.
Consequently, both the precise statement of the problem and
its analysis involve delicate technical issues. We show
that the BCP is equivalent, in a certain sense, to a
reduced Brownian control problem (RBCP) of lower dimension.
The RBCP is a singular stochastic control problem, in which
both the controls and the cumulative cost process are
locally of bounded variation. 


williams@math.ucsd.edu

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

2737. A DIFFERENTIATION THEORY FOR ITO CALCULUS 

Hassan Allouba

Can we define a stochastic derivative of semimartingales with respect to
local martingales that leads to a differentiation theory for It\^o's calculus?
We introduce such stochastic derivative processes, focusing here on the stochastic 
derivative of continuous semimartingales with respect to Brownian motion.   We give 
the corresponding fundamental theorem of stochastic calculus, stochastic chain rule, and 
stochastic mean value theorem.   As in It\^o's integration theory, the quadratic variation 
process is central to our differentiation theory.  We generalize, develop further, and 
apply our approach and results presented here in an upcoming article.

allouba@math.kent.edu

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

Home Page | Mirror: France | Latest Abstracts | Search | Abstract Archive | Submissions | Subscriptions
stefano . iacus at unimi . it