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.

n candidates, represented by n i.i.d. continuous random variables X1, …, Xn with known distribution arrive sequentially, and one of them must be chosen, using a non-anticipating stopping rule. The objective is to minimize the expected rank (among the ranks of X1, …, Xn) of the candidate chosen, where the best candidate, i.e. the one with smallest X-value, has rank one, etc. Let the value of the optimal rule be Vn, and lim Vn = V. We prove that V > 1.85. Limiting consideration to the class of threshold rules of the form tn = min {k: Xk ≦ ak for some constants ak, let Wn be the value of the expected rank for the optimal threshold rule, and lim Wn = W. We show 2.295 < W < 2.327.

In the statistical analysis of random closed sets the distribution of the distance from a fixed point to the nearest point of the random set (the empty space function) is an important tool, and therefore development of efficient estimators is crucial.

In this paper, we present results for the steady-state system length distributions of the discrete-time GI/G/1 queue. We examine the system at customer arrival epochs (customer departure epochs) and use the residual service time (residual interarrival time) as the supplementary variable. The embedded Markov chain is of GI/M/1 type if the embedding points are arrival epochs and is of M/G/1 type if the embedding points are departure epochs. Using the matrix analytic method, we identify the necessary and sufficient condition for both Markov chains to be positive recurrent. For the GI/M/1 type chain, we derive a matrix-geometric solution for its steady-state distribution and for the M/G/1 type chain, we develop a simple linear transformation that relates it to the GI/M/1 type chain and leads to a simple analytic solution for its steady-state distribution. We also show that the steady-state system length distribution at an arbitrary point in time can be obtained by a simple linear transformation of the matrix-geometric solution for the GI/M/1 type chain. A number of applications of the model to communication systems and numerical examples are also discussed.

This paper studies optimal routing and jockeying policies in a two-station parallel queueing system. It is assumed that jobs arrive to the system in a Poisson stream with rate λand are routed to one of two parallel stations. Each station has a single server and a buffer of infinite capacity. The service times are exponential with server-dependent rates, μ1 and μ2. Jockeying between stations is permitted. The jockeying cost is cij when a job in station i jockeys to station j, i ≠ j. There is no cost when a new job joins either station. The holding cost in station j is hj, h1 ≦ h2, per job per unit time. We characterize the structure of the dynamic routing and jockeying policies that minimize the expected total (holding plus jockeying) cost, for both discounted and long-run average cost criteria. We show that the optimal routing and jockeying controls are described by three monotonically non-decreasing functions. We study the properties of these control functions, their relationships, and their asymptotic behavior. We show that some well-known queueing control models, such as optimal routing to symmetric and asymmetric queues, preemptive or non-preemptive scheduling on homogeneous or heterogeneous servers, are special cases of our system.

The paper is concerned with the distribution of the level N of the first crossing of a counting process trajectory with a lower boundary. Compound and simple Poisson or binomial processes, gamma renewal processes, and finally birth processes are considered. In the simple Poisson case, expressing the exact distribution of N requires the use of a classical family of Abel–Gontcharoff polynomials. For other cases convenient extensions of these polynomials into pseudopolynomials with a similar structure are necessary. Such extensions being applicable to other fields of applied probability, the central part of the present paper has been devoted to the building of these pseudopolynomials in a rather general framework.

We introduce a family of stationary random measures in the Euclidean space generated by so-called germ-grain models. The germ-grain model is defined as the union of i.i.d. compact random sets (grains) shifted by points (germs) of a point process. This model gives rise to random measures defined by the sum of contributions of non-overlapping parts of the individual grains. The corresponding moment measures are calculated and an ergodic theorem is presented. The main result is the central limit theorem for the introduced random measures, which is valid for rather general independently marked germ-grain models, including those with non-Poisson distribution of germs and non-convex grains. The technique is based on a central limit theorem for β-mixing random fields. It is shown that this construction of random measures includes those random measures obtained by the so-called positive extensions of intrinsic volumes. In the Poisson case it is possible to prove a central limit theorem under weaker assumptions by using approximations by m-dependent random fields. Applications to statistics of the Boolean model are also discussed. They include a standard way to derive limit theorems for estimators of the model parameters.

The series expansion for the solution of the integral equation for the first-passage-time probability density function, obtained by resorting to the fixed point theorem, is used to achieve approximate evaluations for which error bounds are indicated. A different use of the fixed point theorem is then made to determine lower and upper bounds for asymptotic approximations, and to examine their range of validity.

The classical Blaschke-Petkanschin formula is a formula in integral geometry givmg a geometric measure decomposition of the q-fold product of Lebesgue measure. The original versions are due to Blaschke and Petkanschin in the 1930s. In Zähle (1990) and Jensen and Kiêu (1992), generalized versions have been derived, where Lebesgue measure is replaced by Hausdorff measure.

This paper is concerned with the study of death processes with time-homogeneous non-linear death rates. An explicit formula is obtained for the joint distribution of the state XT and the variable ∫T0g(Xt), where g is any given real function and T corresponds to some appropriate stopping time. This is achieved by constructing a family of martingales and then by using a particular family of Abel–Gontcharoff pseudopolynomials (the theory of which has been introduced in a companion paper) and related Abelian-type expansions. Moreover, the distribution of the first crossing level of such a death process through a general upper boundary is also evaluated in terms of pseudopolynomials of that kind. The flexibility of the methods developed makes easy the extension to multidimensional death processes.

A queueing network with arbitrary topology, state dependent routing and flow control is considered. Customers may enter the network at any queue and they are routed through it until they reach certain queues from which they may leave the system. The routing is based on local state information. The service rate of a server is controlled based on local state information as well. A distributed policy for routing and service rate control is identified that achieves maximum throughput. The policy can be implemented without knowledge of the arrival and service rates. The importance of flow control is demonstrated by showing that, in certain networks, if the servers cannot be forced to idle, then no maximum throughput policy exists when the arrival rates are not known. Also a model for exchange of state information among neighboring nodes is presented and the network is studied when the routing is based on delayed state information. A distributed policy is shown to achieve maximum throughput in the case of delayed state information. Finally, some implications for deterministic flow networks are discussed.

The quasi-stationary distribution of the closed stochastic SIS model changes drastically as the basic reproduction ratio R0 passes the deterministic threshold value 1. Approximations are derived that describe these changes. The quasi-stationary distribution is approximated by a geometric distribution (discrete!) for R0 distinctly below 1 and by a normal distribution (continuous!) for R0 distinctly above 1. Uniformity of the approximation with respect to R0 allows one to study the transition between these two extreme distributions. We also study the time to extinction and the invasion and persistence thresholds of the model.

This reports on work in progress, developing a dynamical context for Bookstein's shape theory. It shows how Bookstein's shape space for triangles arises when the landmarks are moved around by a particular Brownian motion on the general linear group of (2 × 2) invertible matrices. Indeed, suppose that the random process G(t) ∈ GL(2, ℝ) solves the Stratonovich stochastic differential equation dsG = (dsB)G for a Brownian matrix B (independent Brownian motion entries). If {x1 x2, x3} is a fixed (non-degenerate) triple of planar points then Xi(t) = G(t)xi; determines a triple {X1 X2, X3} whose shape performs a diffusion which can be shown to be Brownian motion on the hyperbolic plane of negative curvature − 2.

Batch departures arise in various applications of queues. In particular, such models have been studied recently in connection with production systems. For the most part, however, these models assume Poisson arrivals and exponential service times; little is known about them under more general settings. We consider how their stationary queue length distributions are affected by the distributions of interarrival times, service times and departing batch sizes of customers. Since this is not an easy problem even for single departure models, we first concentrate on single-node queues with a symmetric service discipline, which is known to have nice properties. We start with pre-emptive LIFO, a special case of the symmetric service discipline, and then consider symmetric queues with Poisson arrivals. Stability conditions and stationary queue length distributions are obtained for them, and several stochastic order relations are considered. For the symmetric queues and Poisson arrivals, we also discuss their network. Stability conditions and the stationary joint queue length distribution are obtained for this network.

For a stationary point process X of convex particles in ℝd the projected thick section process X(L) on a q-dimensional linear subspace L is considered. Formulae connecting geometric functionals, e.g. the quermass densities of X and X(L), are presented. They generalize the classical results of Miles (1976) and Davy (1976) which hold only in the isotropic case.

We consider a model in which players must divide a fixed amount of resource between a number of trials of an underlying contest, with the underlying contest based on the War of Attrition. We are able to find the unique ES set (a simple generalisation of the idea of an evolutionarily stable strategy) in certain circumstances: in particular we find the conditions under which the ES set may contain a pure strategy.