Asymptotics in the random assignment problem

Summary We show that, in the usual probabilistic model for the random assignment problem, the optimal cost tends to a limit constant in probability and in expectation. The method involves construction of an infinite limit structure, in terms of which the limit constant is defined. But we cannot improve on the known numerical bounds for the limit.Research supported by NSF Grant MCS90-01710     

The asymptotic behaviour of lovász’ ϑ function for random graphs

We show that for a random graph Lovász’ ϑ function is of order √n.     

Probabilizing parking functions

We explore the link between combinatorics and probability generated by the question “What does a random parking function look like?” This gives rise to novel probabilistic interpretations of some elegant, known generating functions. It leads to new combinatorics: how many parking functions begin with i? We classify features (e.g., the full descent pattern) of parking functions that have exactly the same distribution among parking functions as among all functions. Finally, we develop the link between parking functions and Brownian excursion theory to give examples where the two ensembles differ.     

Eigenanalysis on a bivariate covariance kernel

Certain constructions of copulas can be interpreted as an eigendecomposition of a kernel. We study some properties of the eigenfunctions and their integrals of a covariance kernel related to a bivariate distribution. The covariance between functions of random variables in terms of the cumulative distribution function is used. Some bounds for the trace of the kernel and some inequalities for a continuous random variable concerning a function and its derivative are obtained. We also obtain relations to diagonal expansions and canonical correlation analysis and, as a by-product, series of constants for some particular distributions.     

Long paths in sparse random graphs

We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc. Dedicated to Tibor Gallai on his seventieth birthday     

Component structure in the evolution of random hypergraphs

The component structure of the most general random hypergraphs, with edges of differen sizes, is analyzed. We show that, as this is the case for random graphs, there is a “double jump” in the probable and almost sure size of the greatest component of hypergraphs, when the average vertex degree passes the value 1.     

The perimeter of uniform and geometric words: a probabilistic analysis

Abstract

Let a word be a sequence of n i.i.d. integer random variables. The perimeter P of the word is the number of edges of the word, seen as a polyomino. In this paper, we present a probabilistic approach to the computation of the moments of P. This is applied to uniform and geometric random variables. We also show that, asymptotically, the distribution of P is Gaussian and, seen as a stochastic process, the perimeter converges in distribution to a Brownian motion.     

The shape of random tanglegrams

A tanglegram consists of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the trees. We show that the two halves of a random tanglegram essentially look like two independently chosen random plane binary trees. This fact is used to derive a number of results on the shape of random tanglegrams, including theorems on the number of cherries and generally occurrences of subtrees, the root branches, the number of automorphisms, and the height. For each of these, we obtain limiting probabilities or distributions. Finally, we investigate the number of matched cherries, for which the limiting distribution is identified as well.     

Optimal replacement for discrete additive damage models: Algorithm

A system receives shocks at successive random points of discrete time, and each shock causes a positive integer-valued random amount of damage which accumulates on the system one after another. The system is subject to failure and it fails once the total cumulative damage level first exceeds a fixed threshold. Upon failure the system must be replaced by a new and identical one and a cost is incurred. If the system is replaced before failure, a smaller cost is incurred. In previous work, under some assumptions, we specified a replacement rule which minimizes the long-run (expected) average cost per unit time and possesses control limit property. In this paper, a general algorithm for such models is developed. This research has been jointly supported by ITDC, contract No.105-82150 and the National Natural Science Foundation of China.     

Asymptotics of random contractions

In this paper we discuss the asymptotic behaviour of random contractions X=RS, where R, with distribution function F, is a positive random variable independent of S∈(0,1). Random contractions appear naturally in insurance and finance. Our principal contribution is the derivation of the tail asymptotics of X assuming that F is in the max-domain of attraction of an extreme value distribution and the distribution function of S satisfies a regular variation property. We apply our result to derive the asymptotics of the probability of ruin for a particular discrete-time risk model. Further we quantify in our asymptotic setting the effect of the random scaling on the Conditional Tail Expectations, risk aggregation, and derive the joint asymptotic distribution of linear combinations of random contractions.     

Weak convergence of random <Emphasis Type="Bold">p</Emphasis>-mappings and the exploration process of inhomogeneous continuum random trees

We study the asymptotics of the p-mapping model of random mappings on [n] as n gets large, under a large class of asymptotic regimes for the underlying distribution p. We encode these random mappings in random walks which are shown to converge to a functional of the exploration process of inhomogeneous random trees, this exploration process being derived (Aldous-Miermont-Pitman 2004) from a bridge with exchangeable increments. Our setting generalizes previous results by allowing a finite number of “attracting points” to emerge.Research supported by NSF Grant DMS-0203062.Research supported by NSF Grant DMS-0071468.     

Itô’s excursion theory and random trees

We explain how Itô’s excursion theory can be used to understand the asymptotic behavior of large random trees. We provide precise statements showing that the rescaled contour of a large Galton–Watson tree is asymptotically distributed according to Itô’s excursion measure. As an application, we provide a simple derivation of Aldous’ theorem stating that the rescaled contour function of a Galton–Watson tree conditioned to have a fixed large progeny converges to a normalized Brownian excursion. We also establish a similar result for a Galton–Watson tree conditioned to have a fixed large height.     

Extremal properties of some geometric processes

In this paper some isoperimetric inequalities for stationary random tessellations are discussed. At first, classical results on deterministic tessellations in the Euclidean plane are extended to the case of random tessellations. An isoperimetric inequality for the random Poisson polygon is derived as a consequence of a theorem of Davidson concerning an extremal property of tessellations generated by random lines inR ². We mention extremal properties of stationary hyperplane tessellations inR ^d related to Davidson's result in cased=2. Finally, similar problems for random arrangements ofr-flats inR ^d are considered (r).This work was done while the author was visiting the University of Strathclyde in Glasgow.     

Probability set functions

A probability set function is interpretable as a probability distribution on binary sequences of fixed length. Cumulants of probability set functions enjoy particularly simple properties which make them more manageable than cumulants of general random variables. We derive some identities satisfied by cumulants of probability set functions which we believe to be new. Probability set functions may be expanded in terms of their cumulants. We derive an expansion which allows the construction of examples of probability set functions whose cumulants are arbitrary, restricted only by their absolute values. It is known that this phenomenon cannot occur for continuous probability distributions. Some particular examples of probability set functions are considered, and their cumulants are computed, leading to a conjecture on the upper bound of the values of cumulants. Moments of probability set functions determined by arithmetical conditions are computed in a final example.Dedicated to our friend, W.A. Beyer. Financial support for this work was derived from the U.S.D.O.E. Human Genome Project, through the Center for Human Genome Studies at Los Alamos National Laboratory, and also through the Center for Nonlinear Studies, Los Alamos National Laboratory, LANL report LAUR-97-323.     

The forest associated with the record process on a Lévy tree

We perform a pruning procedure on a Lévy tree and instead of throwing away the removed sub-tree, we regraft it on a given branch (not related to the Lévy tree). We prove that the tree constructed by regrafting is distributed as the original Lévy tree, generalizing a result of Addario-Berry, Broutin and Holmgren where only Aldous’s tree is considered. As a consequence, we obtain that the “average pruning time” of a leaf is distributed as the height of a leaf picked at random in the Lévy tree.     

On optimal matchings

Givenn random red points on the unit square, the transportation cost between them is tipically √n logn.     

Random variables as pathwise integrals with respect to fractional Brownian motion

We give both necessary and sufficient conditions for a random variable to be represented as a pathwise stochastic integral with respect to fractional Brownian motion with an adapted integrand. We also show that any random variable is a value of such integral in an improper sense and that such integral can have any prescribed distribution. We discuss some applications of these results, in particular, to fractional Black–Scholes model of financial market.     

Law of large numbers and central limit theorem for randomly forced PDE's

We consider a class of dissipative PDE's perturbed by an external random force. Under the condition that the distribution of perturbation is sufficiently non-degenerate, a strong law of large numbers (SLLN) and a central limit theorem (CLT) for solutions are established and the corresponding rates of convergence are estimated. It is also shown that the estimates obtained are close to being optimal. The proofs are based on the property of exponential mixing for the problem in question and some abstract SLLN and CLT for mixing-type Markov processes.     

Threshold functions

It is shown that every non-trivial monotone increasing property of subsets of a set has a threshold function. This generalises a number of classical results in the theory of random graphs. First author supported by NSF grant MCS 8104854     

Random sorting networks

A sorting network is a shortest path from 12?n to n?21 in the Cayley graph of Sn generated by nearest-neighbour swaps. We prove that for a uniform random sorting network, as n→∞ the space-time process of swaps converges to the product of semicircle law and Lebesgue measure. We conjecture that the trajectories of individual particles converge to random sine curves, while the permutation matrix at half-time converges to the projected surface measure of the 2-sphere. We prove that, in the limit, the trajectories are Hölder-1/2 continuous, while the support of the permutation matrix lies within a certain octagon. A key tool is a connection with random Young tableaux.