We consider an M/G/1 queue with the special feature that the speed of the server alternates between two constant values sL and sH > sL. The high-speed periods are exponentially distributed, and the low-speed periods have a general distribution. Our main results are: (i) for the case that the distribution of the low-speed periods has a rational Laplace–Stieltjes transform, we obtain the joint distribution of the buffer content and the state of the server speed; (ii) for the case that the distribution of the low-speed periods and/or the service request distribution is regularly varying at infinity, we obtain explicit asymptotics for the tail of the buffer content distribution. The two cases in which the offered traffic load is smaller or larger than the low service speed are shown to result in completely different asymptotics.

Two non-parametric methods for the estimation of the directional measure of stationary line and fibre processes in d-dimensional space are presented. The input data for both methods are intersection counts with finitely many test windows situated in hyperplanes. The first estimator is a measure valued maximum likelihood estimator, if applied to Poisson line processes. The second estimator uses an approximation of the associated zonoid (the Steiner compact) by zonotopes. Consistency of both estimators is proved (without use of the Poisson assumption). The estimation methods are compared empirically by simulation.

We consider a stochastic model for the spread of an SIR (susceptible → infective → removed) epidemic among a closed, finite population that contains several types of individuals and is partitioned into households. The infection rate between two individuals depends on the types of the transmitting and receiving individuals and also on whether the infection is local (i.e., within a household) or global (i.e., between households). The exact distribution of the final outcome of the epidemic is outlined. A branching process approximation for the early stages of the epidemic is described and made fully rigorous, by considering a sequence of epidemics in which the number of households tends to infinity and using a coupling argument. This leads to a threshold theorem for the epidemic model. A central limit theorem for the final outcome of epidemics which take off is derived, by exploiting an embedding representation.

We show that if performance measures in a general stochastic scheduling problem satisfy partial conservation laws (PCL), which extend the generalized conservation laws (GCL) introduced by Bertsimas and Niño-Mora (1996), then the problem is solved optimally by a priority-index policy under a range of admissible linear performance objectives, with both this range and the optimal indices being determined by a one-pass adaptive-greedy algorithm that extends Klimov's: we call such scheduling problems PCL-indexable. We further apply the PCL framework to investigate the indexability property of restless bandits (two-action finite-state Markov decision chains) introduced by Whittle, obtaining the following results: (i) we present conditions on model parameters under which a single restless bandit is PCL-indexable, and hence indexable; membership of the class of PCL-indexable bandits is tested through a single run of the adaptive-greedy algorithm, which further computes the Whittle indices when the test is positive; this provides a tractable sufficient condition for indexability; (ii) we further introduce the subclass of GCL-indexable bandits (including classical bandits), which are indexable under arbitrary linear rewards. Our analysis is based on the achievable region approach to stochastic optimization, as the results follow from deriving and exploiting a new linear programming reformulation for single restless bandits.

Consider the Boolean model in ℝ2, where the germs form a homogeneous Poisson point process with intensity λ and the grains are convex compact random sets. It is known (see, e.g., Cressie (1993, Section 9.5.3)) that Laslett's rule transforms the exposed tangent points of the Boolean model into a homogeneous Poisson process with the same intensity. In the present paper, we give a simple proof of this result, which is based on a martingale argument. We also consider the cumulative process of uncovered area in a vertical strip and show that a (linear) Poisson process with intensity λ can be embedded in it.

In this paper, results on spectrally negative Lévy processes are used to study the ruin probability under some risk processes. These processes include the compound Poisson process and the gamma process, both perturbed by diffusion. In addition, the first time the risk process hits a given level is also studied. In the case of classical risk process, the joint distribution of the ruin time and the first recovery time is obtained. Some results in this paper have appeared before (e.g., Dufresne and Gerber (1991), Gerber (1990), dos Reis (1993)). We revisit them from the Lévy process theory's point of view and in a unified and simple way.

Let X(t) be a continuous two-dimensional stationary Gaussian process with mean zero, having a marginal density function p[x] and covariance matrix R(t). Let Δ = {∂L; L > 0} be a family of piecewise smooth boundaries of similar two-dimensional star-shaped regions ΓL. We show that, under two conditions on R(t), the asymptotic distribution of the duration of an excursion of X(t) outside ΓL, for large L, depends on the position of the maximum of p[x] on ∂L and on whether R′(0) is zero or not, should the maximum occur at a vertex. We obtain the asymptotic distributions of the duration of an excursion for each of the three cases that arise. We also generalise some results of Breitung (1994) on the asymptotic crossing rates of vector Gaussian processes.

We study a Markovian model for a perishable inventory system with random input and an external source of obsolescence: at Poisson random times the whole current content of the system is spoilt and must be scrapped. The system can be described by its virtual death time process. We derive its stationary distribution in closed form and find an explicit formula for the Laplace transform of the cycle length, defined as the time between two consecutive item arrivals in an empty system. The results are used to compute several cost functionals. We also derive these functionals under the corresponding heavy traffic approximation, which is modeled using a Brownian motion in [0,1] reflected at 0 and 1 and restarted at 1 at the Poisson disaster times.

This paper is about the probability law of the integral of geometric Brownian motion over a finite time interval. A partial differential equation is derived for the Laplace transform of the law of the reciprocal integral, and is shown to yield an expression for the density of the distribution. This expression has some advantages over the ones obtained previously, at least when the normalized drift of the Brownian motion is a non-negative integer. Bougerol's identity and a relationship between Brownian motions with opposite drifts may also be seen to be special cases of these results.

The multiplexing of variable bit rate traffic streams in a packet network gives rise to two types of queueing. On a small time-scale, the rates at which the sources send is more or less constant, but there is queueing due to simultaneous packet arrivals (packet-level effect). On a somewhat larger time-scale, queueing is the result of a relatively high number of sources sending at a rate that is higher than their average rate (burst-level effect). This paper explores these effects. In particular, we give asymptotics of the overflow probability in the combined packet/burst scale model. It is shown that there is a specific size of the buffer (i.e. the ‘critical buffer size’) below which packet-scale effects are dominant, and above which burst-scale effects essentially determine the performance—strikingly, there is a sharp demarcation: theso-called ‘phase transition’. The results are asymptotic in the number of sources n. We scale buffer space B and link rate C by n, to nb and nc, respectively; then we let n grow large. Applying large deviations theory we show that in this regime the overflow probability decays exponentially in the number of sources n. For small buffers the corresponding decay rate can be calculated explicitly, for large buffers we derive an asymptote (linear in b). The results for small and large buffers give rise to an approximation for the decay rate (with general b), as well as for the critical buffer size. A numerical example (multiplexing of voice streams) confirms the accuracy of these approximations.

Some consequences of restarting stochastic search algorithms are studied. It is shown under reasonable conditions that restarting when certain patterns occur yields probabilities that the goal state has not been found by the nth epoch which converge to zero at least geometrically fast in n. These conditions are shown to hold for restarted simulated annealing employing a local generation matrix, a cooling schedule Tn ∼ c/n and restarting after a fixed number r + 1 of duplications of energy levels of states when r is sufficiently large. For simulated annealing with logarithmic cooling these probabilities cannot decrease to zero this fast. Numerical comparisons between restarted simulated annealing and several modern variations on simulated annealing are also presented and in all cases the former performs better.

Following Füredi and Komlós, we develop a graph theory method to study the high moments of large random matrices with independent entries. We apply this method to sparse N × N random matrices AN,p that have, on average, p non-zero elements per row. One of our results is related to the asymptotic behaviour of the spectral norm ∥AN,p∥ in the limit 1 ≪ p ≪ N. We show that the value pc = log N is the critical one for lim ∥AN,p/√p∥ to be bounded or not. We discuss relations of this result with the Erdős–Rényi limit theorem and properties of large random graphs. In the proof, the principal issue is that the averaged vertex degree of plane rooted trees of k edges remains bounded even when k → ∞. This observation implies fairly precise estimates for the moments of AN,p. They lead to certain generalizations of the results by Sinai and Soshnikov on the universality of local spectral statistics at the border of the limiting spectra of large random matrices.

In generalization of the well-known formulae for quermass densities of stationary and isotropic Boolean models, we prove corresponding results for densities of mixed volumes in the stationary situation and show how they can be used to determine the intensity of non-isotropic Boolean models Z in d-dimensional space for d = 2, 3, 4. We then consider non-stationary Boolean models and extend results of Fallert on quermass densities to densities of mixed volumes. In particular, we present explicit formulae for a planar inhomogeneous Boolean model with circular grains.

The (unoriented or oriented) mean normal measure of a stationary process of convex particles carries information on the mean shape of the particles and may, in particular, be useful for describing and detecting anisotropy of the particle process. This paper investigates the mean normal measure under the aspect of its determination from intersections, especially with lines or hyperplanes.

Multivariate subordinators are multivariate Lévy processes that are increasing in each component. Various examples of multivariate subordinators, of interest for applications, are given. Subordination of Lévy processes with independent components by multivariate subordinators is defined. Multiparameter Lévy processes and their subordination are introduced so that the subordinated processes are multivariate Lévy processes. The relations between the characteristic triplets involved are established. It is shown that operator self-decomposability and the operator version of the class Lm property are inherited from the multivariate subordinator to the subordinated process under the condition of operator stability of the subordinand.

In this paper, we study a maintenance model with general repair and two types of replacement: failure and preventive replacement. When the system fails a decision is made whether to replace or repair it. The repair degree that affects the virtual age of the system is assumed to be a random function of the repair-cost and the virtual age at failure time. The system can be preventively replaced at any time before failure. The objective is to find the repair/replacement policy minimizing the long-run expected average cost per unit time. It is shown that a generalized repair-cost-limit policy is optimal and the preventive replacement time depends on the virtual age of the system and on the length of the operating time since the last repair. Computational procedures for finding the optimal repair-cost limit and the optimal average cost are developed. This model includes many well-known models as special cases and the approach provides a unified treatment of a wide class of maintenance models.

For a positive recurrent continuous-time Markov chain on a countable state space, we compare the access time to equilibrium to the hitting time of a particular state. For monotone processes, the exponential rates are ranked. When the process starts far from equilibrium, a cutoff phenomenon occurs at the same instant, in the sense that both the access time to equilibrium and the hitting time of a fixed state are equivalent to the expectation of the latter. In the case of Markov chains on trees, that expectation can be computed explicitly. The results are illustrated on the M/M/∞ queue.