Let M be acomplete Riemannian manifold, M ∈ ℕ andp ≥ 1. Weprove that almost everywhere on x = (x1,...,xN) ∈ MNfor Lebesgue measure in MN, the measure \hbox{$\di \mu(x)=\f1N\sum_{k=1}^N\d_{x_k}$}$\mathit{\mu }\mathrm{\left(}\mathit{x}\mathrm{\right)}\mathrm{=}\frac{\mathrm{1}}{\mathit{N}}\sum _{\mathit{k}\mathrm{=}\mathrm{1}}^{\mathit{N}}{\mathit{\delta }}_{{\mathit{x}}_{\mathit{k}}}$ has a unique p–mean ep(x).As a consequence, if X = (X1,...,XN)is a MN-valued randomvariable with absolutely continuous law, then almost surely μ(X(ω)) has aunique p–mean. In particular if (Xn)n ≥ 1is an independent sample of an absolutely continuous law in M, then the processep,n(ω) = ep(X1(ω),...,Xn(ω))is well-defined. Assume M is compact and consider a probability measureν inM. Usingpartial simulated annealing, we define a continuous semimartingale which converges inprobability to the set of minimizers of the integral of distance at power p with respect toν. When theset is a singleton, it converges to the p–mean.

A discrete time stochastic model for a multiagent system given in terms of a large collection of interacting Markov chains is studied. The evolution of the interacting particles is described through a time inhomogeneous transition probability kernel that depends on the ‘gradient’ of the potential field. The particles, in turn, dynamically modify the potential field through their cumulative input. Interacting Markov processes of the above form have been suggested as models for active biological transport in response to external stimulus such as a chemical gradient. One of the basic mathematical challenges is to develop a general theory of stability for such interacting Markovian systems and for the corresponding nonlinear Markov processes that arise in the large agent limit. Such a theory would be key to a mathematical understanding of the interactive structure formation that results from the complex feedback between the agents and the potential field. It will also be a crucial ingredient in developing simulation schemes that are faithful to the underlying model over long periods of time. The goal of this work is to study qualitative properties of the above stochastic system as the number of particles (N) and the time parameter (n) approach infinity. In this regard asymptotic properties of a deterministic nonlinear dynamical system, that arises in the propagation of chaos limit of the stochastic model, play a key role. We show that under suitable conditions this dynamical system has a unique fixed point. This result allows us to study stability properties of the underlying stochastic model. We show that as N → ∞, the stochastic system is well approximated by the dynamical system, uniformly over time. As a consequence, for an arbitrarily initialized system, as N → ∞ and n → ∞, the potential field and the empirical measure of the interacting particles are shown to converge to the unique fixed point of the dynamical system. In general, simulation of such interacting Markovian systems is a computationally daunting task. We propose a particle based approximation for the dynamic potential field which allows for a numerically tractable simulation scheme. It is shown that this simulation scheme well approximates the true physical system, uniformly over an infinite time horizon.

To study the limiting behaviour of the random running-time of the FIND algorithm, the so-called FIND process was introduced by Grübel and Rösler [1]. In this paper an approach for determining the nth moment function is presented. Applied to the second moment this provides an explicit expression for the variance.

We investigate the asymptotic behaviour of the distribution of the number of comparisons needed by a quicksort-style selection algorithm that finds the lth smallest in a set of n numbers. Letting n tend to infinity and considering the values l = 1, ···,n simultaneously we obtain a limiting stochastic process. This process admits various interpretations: it arises in connection with a representation of real numbers induced by nested random partitions and also in connection with expected path lengths of a random walk in a random environment on a binary tree.

Objects of various integer sizes, o1, · ··, on, are to be packed together into bins of size N as they arrive at a service facility. The number of objects of size oi which arrive by time t is , where the components of are independent renewal processes, with At/t → λ as t → ∞. The empty space in those bins which are neither empty nor full at time t is called the wasted space and the system is declared stabilizable if for some finite B there exists a bin-packing algorithm whose use guarantees the expected wasted space is less than B for all t. We show that the system is stabilizable if the arrival processes are Poisson and λ lies in the interior of a certain convex polyhedral cone Λ. In this case there exists a bin-packing algorithm which stabilizes the system without needing to know λ. However, if λ lies on the boundary of Λ the wasted space grows as and if λ is exterior to Λ it grows as O(t); these conclusions hold even if objects may be repacked as often as desired.