This paper gives a survey of the historical development of the solutions of various fluctuation problems in the theory of queues from the point of view of the mathematical methods used. These methods include Markov chains, Markov processes, integral equations, complex functions, generating functions, Laplace transforms, factorization of functions, operator calculus, Banach algebras and some particular methods, such as calculus of finite differences and combinatorics. In addition, the paper contains several recent results of the author for semi-Markov queuing processes.

We consider the piecewise linear interpolation of Gaussian processes with continuous sample paths and stationary increments. The interrelation between the smoothness of the incremental variance function, d(t – s) = E[(X(t) – X(s))2], and the interpolation errors in mean square and uniform metrics is studied. The method of investigation can also be applied to the analysis of different methods of interpolation. It is based on some limit results for large deviations of a sequence of Gaussian non-stationary processes and related point processes. Non-stationarity in our case means mainly the local stationary condition for the sequence of correlation functions rn(t,s), n = 1, 2, ···, which has to hold uniformly in n. Finally, we discuss some examples and an application to the calculation of the distribution function of the maximum of a continuous Gaussian process with a given precision.

Several simple stochastic models are given for a finite closed system of individuals existing in clusters which may come together to form larger clusters which may in turn split up. Some of these models are analysed and compared in equilibrium. Several of the models fit into a general framework established and investigated by Whittle (1965a); it is shown that these models have an equilibrium solution of a particularly simple form, deduced by Whittle, if and only if the models are stochastically reversible. A normal approximation to two of the models in equilibrium is found to give the same mean value as a deterministic approximation.

A number of jobs on two interconnected queues are to be processed by m identical servers. The servers operate in parallel, so that every server can process any job. Jobs in queue i, i = 1, 2, incur an instantaneous holding cost Ci during the time they remain in the system. The service time for jobs in queue i, denoted by Xi, is a random variable with a general distribution. The interconnection process is independent of the service process. We establish sufficient conditions on the service times, the holding costs and the interconnection process under which the non-preemptive scheduling strategy that gives priority to queue 1 minimizes the total expected α -discounted cost. We call this strategy P1. We present counterexamples showing that if any of the sufficient conditions is not satisfied P1 may not be optimal, and that the optimal policy for the single-server problem is not necessarily optimal for the multiserver problem.

The concept of a stable population, which is of basic importance in demography, is generalized to person-flow models as defined by Gani. Stability and asymptotic stability of manpower systems are investigated in terms of the input process and the transition structure. Extending Bartholomew ((1973), Chapter 3) we obtain a result on the limiting behaviour of Gani-type models with asymptotic exponential input processes. The linear population-dynamic model of Leslie (1945) may be considered as a further case.

Approximate results are obtained for the probability distribution of the number of mutant substitutions over a given number of generations. The distribution is a compound Poisson distribution having a variance which is greater than the mean. The substitutions occur in clusters. The most extreme case of clustering is studied in this paper, which assumes that there is no recombination between mutant nucleotides.

We present conditions under which a point process of certain jump times of a Markov process is a Poisson process. The central idea is that if the Markov process is stationary and the compensator of the point process in reverse time has a constant intensity a, then the point process is Poisson with rate a. A known example is that the output flow from an M/M/1 queueing system is Poisson. We present similar Poisson characterizations of more general marked point process functionals of a Markov process. These results yield easy-to-use criteria for a collection of such processes to be multivariate Poisson, compound Poisson, or marked Poisson with a specified dependence or independence. We discuss several applications for queueing systems with batch arrivals and services and for networks of queues. We also indicate how our results extend to functionals of non-Markovian processes.

A new class of models for inhomogeneous spatial point processes is introduced. These locally scaled point processes are modifications of homogeneous template point processes, having the property that regions with different intensities differ only by a scale factor. This is achieved by replacing volume measures used in the density with locally scaled analogues defined by a location-dependent scaling function. The new approach is particularly appealing for modelling inhomogeneous Markov point processes. Distance-interaction and shot noise weighted Markov point processes are discussed in detail. It is shown that the locally scaled versions are again Markov and that locally the Papangelou conditional intensity of the new process behaves like that of a global scaling of the homogeneous process. Approximations are suggested that simplify calculation of the density, for example, in simulation. For sequential point processes, an alternative and simpler definition of local scaling is proposed.

The iteration of random tessellations in ℝd is considered, where each cell of an initial tessellation is further subdivided into smaller cells by so-called component tessellations. Sufficient conditions for stationarity and isotropy of iterated tessellations are given. Formulae are derived for the intensities of their facet processes, and for the expected intrinsic volumes of their typical facets. Particular emphasis is put on two special cases: superposition and nesting of tessellations. Bernoulli thinning of iterated tessellations is also considered.

In this paper we consider an Ornstein–Uhlenbeck (OU) process (M(t))t≥0 whose parameters are determined by an external Markov process (X(t))t≥0 on a finite state space {1, . . ., d}; this process is usually referred to as Markov-modulated Ornstein–Uhlenbeck. We use stochastic integration theory to determine explicit expressions for the mean and variance of M(t). Then we establish a system of partial differential equations (PDEs) for the Laplace transform of M(t) and the state X(t) of the background process, jointly for time epochs t = t1, . . ., tK. Then we use this PDE to set up a recursion that yields all moments of M(t) and its stationary counterpart; we also find an expression for the covariance between M(t) and M(t + u). We then establish a functional central limit theorem for M(t) for the situation that certain parameters of the underlying OU processes are scaled, in combination with the modulating Markov process being accelerated; interestingly, specific scalings lead to drastically different limiting processes. We conclude the paper by considering the situation of a single Markov process modulating multiple OU processes.

Within reliability theory, identifiability problems arise through competing risks. If we have a series system of several components, and if that system is replaced or repaired to as good as new on failure, then the different component failures represent competing risks for the system. It is well known that the underlying component failure distributions cannot be estimated from the observable data (failure time and identity of failed component) without nontestable assumptions such as independence. In practice many systems are not subject to the ‘as good as new’ repair regime. Hence, the objective of this paper is to contrast the identifiability issues arising for different repair regimes. We consider the problem of identifying a model within a given class of probabilistic models for the system. Different models corresponding to different repair strategies are considered: a partial-repair model, where only the failing component is repaired; perfect repair, where all components are as good as new after a failure; and minimal repair, where components are only minimally repaired at failures. We show that on the basis of observing a single socket, the partial-repair model is identifiable, while the perfect- and minimal-repair models are not.

It is shown that a set of random variables with increasing and convex (concave) survival functions are stochastically increasing and convex (concave) in the sample path sense. This stochastic convexity (concavity) result is then used to establish convexity (concavity) results for (i) a single-server queueing system with a time-out control policy, (ii) residual life, (iii) stationary renewal excess life and (iv) M/G/1 queues. These results are new and could not be derived without the direct or indirect aid of the above stochastic convexity (concavity) result. Furthermore, we illustrate that the above stochastic convexity (concavity) result can be applied to obtain new bounds for queueing systems. Specifically, let be the waiting time of the nth customer in a GI/G/1 queue with inter-arrival time survival function and service time survival function . Using the above convexity result it is shown that if and for some such that then for all increasing convex functions φ, whenever the expectations exist. A similar result for and is also obtained. Other examples are also included.

An algorithm is developed for exact simulation from distributions that are defined as fixed points of maps between spaces of probability measures. The fixed points of the class of maps under consideration include examples of limit distributions of random variables studied in the probabilistic analysis of algorithms. Approximating sequences for the densities of the fixed points with explicit error bounds are constructed. The sampling algorithm relies on a modified rejection method.

The stochastic process {Xn} satisfying Xn+1 = max{Yn+1+ αβ Xn, βXn} where {Yn} is a stationary sequence of non-negative random variables and , 0<β <1, can be regarded as a simple thermal energy storage model with controlled input. Attention is mostly confined to the study of μ = EX where the random variable X has the stationary distribution for {Xn}. Even for special cases such as i.i.d. Yn or α = 0, little explicit information appears to be available on the distribution of X or μ . Accordingly, bounding techniques that have been exploited in queueing theory are used to study μ . The various bounds are illustrated numerically in a range of special cases.

The self-similar growth-fragmentation equation describes the evolution of a medium in which particles grow and divide as time proceeds, with the growth and splitting of each particle depending only upon its size. The critical case of the equation, in which the growth and division rates balance one another, was considered in Doumic and Escobedo (2015) for the homogeneous case where the rates do not depend on the particle size. Here, we study the general self-similar case, using a probabilistic approach based on Lévy processes and positive self-similar Markov processes which also permits us to analyse quite general splitting rates. Whereas existence and uniqueness of the solution are rather easy to establish in the homogeneous case, the equation in the nonhomogeneous case has some surprising features. In particular, using the fact that certain self-similar Markov processes can enter (0,∞) continuously from either 0 or ∞, we exhibit unexpected spontaneous generation of mass in the solutions.

We study the Bayesian problems of detecting a change in the drift rate of an observable diffusion process with linear and exponential penalty costs for a detection delay. The optimal times of alarms are found as the first times at which the weighted likelihood ratios hit stochastic boundaries depending on the current observations. The proof is based on the reduction of the initial problems into appropriate three-dimensional optimal stopping problems and the analysis of the associated parabolic-type free-boundary problems. We provide closed-form estimates for the value functions and the boundaries, under certain nontrivial relations between the coefficients of the observable diffusion.

In Bhatt and Roy's minimal directed spanning tree construction for a random, partially ordered set of points in the unit square, all edges must respect the ‘coordinatewise’ partial order and there must be a directed path from each vertex to a minimal element. We study the asymptotic behaviour of the total length of this graph with power-weighted edges. The limiting distribution is given by the sum of a normal component away from the boundary plus a contribution introduced by the boundary effects, which can be characterized by a fixed-point equation, and is reminiscent of limits arising in the probabilistic analysis of certain algorithms. As the exponent of the power weighting increases, the distribution undergoes a phase transition from the normal contribution being dominant to the boundary effects being dominant. In the critical case in which the weight is simple Euclidean length, both effects contribute significantly to the limit law.

We consider an M/G/1 queue in which the service rate is subject to control. The control is exercised continuously and is based on the observations of the residual workload process. For both the discounted cost and the average cost criteria we obtain conditions which are sufficient for a stationary policy to be optimal. When the service cost rate and the holding cost rates are non-decreasing and convex it is shown that these sufficient conditions are satisfied by a monotonic policy, thus showing its optimality.