Let X1, X2, …, Xn be independent and uniformly distributed random variables in the unit square [0, 1]2, and let L(X1, …, Xn) be the length of the shortest traveling salesman path through these points. In 1959, Beardwood, Halton and Hammersley proved the existence of a universal constant β such that limn→∞n−1/2L(X1, …, Xn) = β almost surely. The best bounds for β are still those originally established by Beardwood, Halton and Hammersley, namely 0.625 ≤ β ≤ 0.922. We slightly improve both upper and lower bounds.

A large-scale service system with multiple customer classes and multiple server pools is considered, with the mean service time depending both on the customer class and server pool. The allowed activities (routeing choices) form a tree (in the graph with vertices being both customer classes and server pools). We study the behavior of the system under a leaf activity priority (LAP) policy, introduced by Stolyar and Yudovina (2012). An asymptotic regime is considered, where the arrival rate of customers and number of servers in each pool tend to ∞ in proportion to a scaling parameter r, while the overall system load remains strictly subcritical. We prove tightness of diffusion-scaled (centered at the equilibrium point and scaled down by r−1/2) invariant distributions. As a consequence, we obtain a limit interchange result: the limit of diffusion-scaled invariant distributions is equal to the invariant distribution of the limiting diffusion process.

In this paper our objective is to study continuous-time Markov decision processes on a general Borel state space with both impulsive and continuous controls for the infinite time horizon discounted cost. The continuous-time controlled process is shown to be nonexplosive under appropriate hypotheses. The so-called Bellman equation associated to this control problem is studied. Sufficient conditions ensuring the existence and the uniqueness of a bounded measurable solution to this optimality equation are provided. Moreover, it is shown that the value function of the optimization problem under consideration satisfies this optimality equation. Sufficient conditions are also presented to ensure on the one hand the existence of an optimal control strategy, and on the other hand the existence of a ε-optimal control strategy. The decomposition of the state space into two disjoint subsets is exhibited where, roughly speaking, one should apply a gradual action or an impulsive action correspondingly to obtain an optimal or ε-optimal strategy. An interesting consequence of our previous results is as follows: the set of strategies that allow interventions at time t = 0 and only immediately after natural jumps is a sufficient set for the control problem under consideration.

This paper demonstrates the occurrence of the feature called BRAVO (balancing reduces asymptotic variance of output) for the departure process of a finite-buffer Markovian many-server system in the QED (quality and efficiency-driven) heavy-traffic regime. The results are based on evaluating the limit of an equation for the asymptotic variance of death counts in finite birth-death processes.

We study the asymptotics of a Markovian system of N ≥ 3 particles in [0, 1]d in which, at each step in discrete time, the particle farthest from the current centre of mass is removed and replaced by an independent U[0, 1]d random particle. We show that the limiting configuration contains N − 1 coincident particles at a random location ξN ∈ [0, 1]d. A key tool in the analysis is a Lyapunov function based on the squared radius of gyration (sum of squared distances) of the points. For d = 1, we give additional results on the distribution of the limit ξN, showing, among other things, that it gives positive probability to any nonempty interval subset of [0, 1], and giving a reasonably explicit description in the smallest nontrivial case, N = 3.

In this paper we study the speed of infection spread and the survival of the contact process in the random geometric graph G = G(n, rn, f) of n nodes independently distributed in S = [-½, ½]2 according to a certain density f(·). In the first part of the paper we assume that infection spreads from one node to another at unit rate and that infected nodes stay in the same state forever. We provide an explicit lower bound on the speed of infection spread and prove that infection spreads in G with speed at least D1nrn2. In the second part of the paper we consider the contact process ξt on G where infection spreads at rate λ > 0 from one node to another and each node independently recovers at unit rate. We prove that, for every λ > 0, with high probability, the contact process on G survives for an exponentially long time; there exist positive constants c1 and c2 such that, with probability at least 1 - c1 / n4, the contact process starting with all nodes infected survives up to time tn = exp(c2n/logn) for all n.

In this paper we develop two permutation theorems on argument increasing functions of a multivariate random vector and a real parameter vector. We use the unified approach of our two theorems to provide some important theoretical results on the capital allocation in actuarial science, the deductible and upper limit allocations in insurance policy, and portfolio allocation in financial engineering. Our results successfully improve or extend the corresponding works in the literature.

‘Small worlds’ are large systems in which any given node has only a few connections to other points, but possessing the property that all pairs of points are connected by a short path, typically logarithmic in the number of nodes. The use of random walks for sampling a uniform element from a large state space is by now a classical technique; to prove that such a technique works for a given network, a bound on the mixing time is required. However, little detailed information is known about the behaviour of random walks on small-world networks, though many predictions can be found in the physics literature. The principal contribution of this paper is to show that for a famous small-world random graph model known as the Newman-Watts small-world model, the mixing time is of order log2n. This confirms a prediction of Richard Durrett [5, page 22], who proved a lower bound of order log2n and an upper bound of order log3n.

For a collection of objects such as socks, which can be matched according to a characteristic such as color, we study the innocent phrase ‘the distribution of the color of a matching pair’ by looking at two methods for selecting socks. One method is memoryless and effectively samples socks with replacement, while the other samples socks sequentially, with memory, until the same color has been seen twice. We prove that these two methods yield the same distribution on colors if and only if the initial distribution of colors is a uniform distribution. We conjecture a nontrivial maximum value for the total variation distance of these distributions in all other cases.

Consider two independent Goldstein-Kac telegraph processes X1(t) and X2(t) on the real line ℝ. The processes Xk(t), k = 1, 2, describe stochastic motions at finite constant velocities c1 > 0 and c2 > 0 that start at the initial time instant t = 0 from the origin of ℝ and are controlled by two independent homogeneous Poisson processes of rates λ1 > 0 and λ2 > 0, respectively. We obtain a closed-form expression for the probability distribution function of the Euclidean distance ρ(t) = |X1(t) - X2(t)|, t > 0, between these processes at an arbitrary time instant t > 0. Some numerical results are also presented.

In this paper some important properties of the generalized Pólya process are derived and their applications are discussed. The generalized Pólya process is defined based on the stochastic intensity. By interpreting the defined stochastic intensity of the generalized Pólya process, the restarting property of the process is discussed. Based on the restarting property of the process, the joint distribution of the number of events is derived and the conditional joint distribution of the arrival times is also obtained. In addition, some properties of the compound process defined for the generalized Pólya process are derived. Furthermore, a new type of repair is defined based on the process and its application to the area of reliability is discussed. Several examples illustrating the applications of the obtained properties to various areas are suggested.

We consider a stationary Poisson hyperplane process with given directional distribution and intensity in d-dimensional Euclidean space. Generalizing the zero cell of such a process, we fix a convex body K and consider the intersection of all closed halfspaces bounded by hyperplanes of the process and containing K. We study how well these random polytopes approximate K (measured by the Hausdorff distance) if the intensity increases, and how this approximation depends on the directional distribution in relation to properties of K.

We consider a nonnegative discrete time and bounded horizon process X for which 0 is an absorbing state and extend it by a random variable that is independent of X. We find a sufficient condition for the resulting process to satisfy, after a canonical time rescaling, the hypothesis of the monotone case theorem. If X describes a secretary type search on a poset with one maximal element or if we consider X with no extension then this condition assumes an especially simple log-concavity type form.

In this paper we consider the stationary Poisson Boolean model with spherical grains and propose a family of nonparametric estimators for the radius distribution. These estimators are based on observed distances and radii, weighted in an appropriate way. They are ratio unbiased and asymptotically consistent for a growing observation window. We show that the asymptotic variance exists and is given by a fairly explicit integral expression. Asymptotic normality is established under a suitable integrability assumption on the weight function. We also provide a short discussion of related estimators as well as a simulation study.

The large deviation principle in the small noise limit is derived for solutions of possibly degenerate Itô stochastic differential equations with predictable coefficients, which may also depend on the large deviation parameter. The result is established under mild assumptions using the Dupuis-Ellis weak convergence approach. Applications to certain systems with memory and to positive diffusions with square-root-like dispersion coefficient are included.