The small-world phenomenon, the principle that we are all linked by a short chain of intermediate acquaintances, has been investigated in mathematics and social sciences. It has been shown to be pervasive both in nature and in engineering systems like the World Wide Web. Work of Jon Kleinberg has shown that people, using only local information, are very effective at finding short paths in a network of social contacts. In this paper we argue that the underlying key to finding short paths is scale invariance. In order to appreciate scale invariance we suggest a continuum setting, since true scale invariance happens at all scales, something which cannot be observed in a discrete model. We introduce a random-connection model that is related to continuum percolation, and we prove the existence of a unique scale-free model, among a large class of models, that allows the construction, with high probability, of short paths between pairs of points separated by any distance.

Let S1 and S2 be two signals of a random variable X, where G1(s1 ∣ x) and G2(s2 ∣ x) are their conditional distributions given X = x. If, for all s1 and s2, G1(s1 ∣ x) - G2(s2 ∣ x) changes sign at most once from negative to positive as x increases, then the conditional expectation of X given S1 is greater than the conditional expectation of X given S2 in the convex order, provided that both conditional expectations are increasing. The stochastic order of the sufficient condition is equivalent to the more stochastically increasing order when S1 and S2 have the same marginal distribution and, when S1 and S2 are sums of X and independent noises, it is equivalent to the dispersive order of the noises.

This note introduces shape orderings for stationary time series autocorrelation and partial autocorrelation functions and explores some of their convergence rate ramifications. The shapes explored include decreasing hazard rate and new better than used, orderings that are familiar from stochastic processes settings. Time series models where these shapes arise are presented. The shapes are used to obtain explicit geometric convergence rates for mean squared errors of one-step-ahead forecasts.

This paper establishes new Foster-type criteria for a Markov chain on a general state space to be Harris recurrent, positive Harris recurrent, or geometrically ergodic. The criteria are based on drift conditions involving stopping times rather than deterministic steps. Meyn and Tweedie (1994) developed similar criteria involving random-sized steps, independent of the Markov chain under study. They also posed an open problem of finding criteria involving stopping times. Our results essentially solve that problem. We also show that the assumption of ψ-irreducibility is not needed when stating our drift conditions for positive Harris recurrence or geometric ergodicity.

In a G/GI/c loss system with balking, reneging, or limited waiting space, deleting some of the arriving customers can either increase or decrease the fraction of the remaining arrivals who get served, depending on how customers are deleted. We present a model in which the random deletion of arrivals independently and with some fixed probability can never decrease the fraction of the remaining arrivals who get served.