The binary interval tree is a random structure that underlies interval division and parking problems. Five incomplete one-sided variants of binary interval trees are considered, providing additional flavors and variations on the main applications. The size of each variant is studied, and a Gaussian tendency is proved in each case via an analytic approach. Differential equations on half scale and delayed differential equations arise and can be solved asymptotically by local expansions and Tauberian theorems. Unlike the binary case, in an incomplete interval tree the size determines most other parameters of interest, such as the height or the internal path length.

We extend the results on the extremal properties of chain-dependent sequences considered in Turkman and Walker (1983) by assuming conditions similar to those given by Leadbetter and Nandagopalan (1987) which permit clustering of high values.

Let F be the gamma distribution function with parameters a > 0 and α > 0 and let Gs be the negative binomial distribution function with parameters α and a/s, s > 0. By combining both probabilistic and approximation-theoretic methods, we obtain sharp upper and lower bounds for . In particular, we show that the exact order of uniform convergence is s–p, where p = min(1, α). Various kinds of applications concerning charged multiplicity distributions, the Yule birth process and Bernstein-type operators are also given.

An upper bound for the asymptotic velocity in various directions of first-passage percolation on the square lattice is derived. In particular this gives a lower bound for the so-called time constant. The result is generalized to other lattices. Numerical examples are included.

We consider an infinite-server queueing system in an extraneous environment. Initially it is shown that the systems of interest can be decomposed into a two-stage system. The primary system is an infinite-server queue with many customer types subject to a clearing mechanism. The secondary system is a special type of bulk-arrival, infinite-server queue. We derive results for the primary and secondary systems separately and combine the results to find the mean steady-state behavior of the original system.

Age replacement policy is commonly used in order to reduce the number of in-service failures. In this paper we define a multivariate version of this policy and develop some of its desirable properties. We also obtain an optimal age replacement policy.

Batch service has a wide application in manufacturing, communication networks, and cloud computing. In batch service queues with limited resources, one critical issue is to properly schedule the service so as to ensure the quality of service. In this paper we consider an M/G[a,b]/1/N batch service queue with bulking threshold a, max service capacity b, and buffer capacity N, where N can be finite or infinite. Through renewal theory, busy period analysis and decomposition techniques, we demonstrate explicitly how the bulking threshold influences the system performance such as the mean waiting time and time-averaged number of loss customers in batch service queues. We then establish a necessary and sufficient condition on the optimal bulking threshold that minimizes the expected waiting time. Enabled by this condition, we propose a simple algorithm which guarantees to find the optimal threshold in polynomial time. The performance of the algorithm is also demonstrated by numerical examples.

Search for an object whose motion is a symmetrical two-dimensional diffusion process is considered in the case where a given amount of search of constant density is distributed, during a given interval of time, over a fixed circular area. An expression for the probability of detection of the object during this interval of time is derived in the special case where the location of the object at time zero is given. The application of this expression would involve numerical work.

Several authors have considered the covariance structure of continuous parameter Markov chains. Most of this work has dealt with particular process ses, notably Morse (1955) who analysed the simple M/M/1 queue and Bene-(1961) who considered a telephone trunking model. Furthermore, the results obtained apply only when the process has attained its limiting (stationary) distribution. A recent paper by Reynolds (1968) gave some general results for finite chains, still assuming stationarity. This note generalises the results obtained therein, and considers the covariance structure during the transient period prior to attaining the stationary distribution where this exists. In the case where no such distribution exists, the results are valid throughout the whole lifetime of the process.

A continuum percolation model on is considered. Using a renormalization technique developed by Grimmett and Marstrand, we show a continuum analogue of their results. We prove the critical value of the percolation equals the limit of the critical value of a slice as the thickness of the slice tends to infinity. We also prove that the effective conductivity in the model is bounded from below by a positive constant in the supercritical case.

The duality results well known for classical random walk and generalized by Janssen (1976) for (J-X) processes (or sequences of random variables defined on a finite Markov chain) are extended to a class of multivariate semi-Markov processes. Just as in the classical case, these duality results lead to connections between some models of risk theory and queueing theory.

Proceeding from duality results for the GI/G/1 queue, this paper obtains the probability of the number served in a busy period of a GI/G/1 system where customers initiating a busy period have a different service time distribution from other customers. Using duality arguments for processes with interchangeable increments, the Laplace transform of the busy period duration is found for a modified GI/M/1 queue.

In this note, we compare the arrival and time stationary distributions of the number of customers in the GI/M/1/n and GI/M/1 queueing systems. We show that, if the inter-arrival c.d.f. H is non-lattice with mean value λ –1, and if the traffic intensity ρ = λμ –1 is strictly less than one, then the convergence rate of the stationary distributions of GI/M/1/n to the corresponding stationary distributions of GI/M/1 is geometric. More-over, the convergence rate can be characterized by the number ω, the unique solution in (0, 1) of the equation . A similar result is established for the M/GI/1/n and M/GI/1 queueing systems.

A coherent system of components, the failure pattern of each of which being assumed to be modelled by an alternating renewal process, is considered. Formulae are derived for the probability that the system is available at a series of points and for the expected numbers of failures and repairs of the system in a fixed interval. It is shown how the model can be generalised to permit each component to exhibit partial availability in the failed state.

A multiple unit standby redundant system with preventive maintenance is presented. The Laplace transform of the probability density function of the time to the first emptiness for the system and its mean time are derived. As a special case, a two-unit standby redundant system with preventive maintenance is investigated in detail.

Two sharp lower bounds for the expectation of a function of a non-negative random variable are obtained under rather weak hypotheses regarding the function, thus generalizing two sharp upper bounds obtained by Brook for the moment generating function. The application of these bounds to economic risk analysis is discussed.

We consider the stability of robust scheduling policies for multiclass queueing networks. These are open networks with arbitrary routeing matrix and several disjoint groups of queues in which at most one queue can be served at a time. The arrival and potential service processes and routeing decisions at the queues are independent, stationary, and ergodic. A scheduling policy is called robust if it does not depend on the arrival and service rates nor on the routeing probabilities. A policy is called throughput-optimal if it makes the system stable whenever the parameters are such that the system can be stable. We propose two robust policies: longest-queue scheduling and a new policy called longest-dominating-queue scheduling. We show that longest-queue scheduling is throughput-optimal for two groups of two queues. We also prove the throughput-optimality of longest-dominating-queue scheduling when the network topology is acyclic, for an arbitrary number of groups and queues.

We consider the estimation of Markov transition matrices by Bayes’ methods. We obtain large and moderate deviation principles for the sequence of Bayesian posterior distributions.

We consider an M/G/1 queue that is idle at time 0. The number of customers sampled at an independent exponential time is shown to have the same geometric distribution under the preemptive-resume last-in-first-out and the processor-sharing disciplines. Hence, the marginal distribution of the queue length at any time is identical for both disciplines. We then give a detailed analysis of the time until the first departure for any symmetric queueing discipline. We characterize its distribution and show that it is insensitive to the service discipline. Finally, we study the tail behavior of this distribution.

Let Dj be a domain in nj,-dimensional Euclidean space, for j = 1, …, k. Suppose that for each j = 1,…, k, Nj points are chosen independently at random in Dj. A theorem, which is an extension of a theorem of Crofton, is proved about the expected value of functions of the points.