For positive recurrent nearest-neighbour, semi-homogeneous random walks on the lattice {0, 1, 2, …} X {0, 1, 2, …} the bivariate generating function of the stationary distribution is analysed for the case where one-step transitions to the north, north-east and east at interior points of the state space all have zero probability. It is shown that this generating function can be represented by meromorphic functions. The construction of this representation is exposed for a variety of one-step transition vectors at the boundary points of the state space.

We consider an Mx/G/1 queueing system with N-policy and multiple vacations. As soon as the system empties, the server leaves for a vacation of random length V. When he returns, if the queue length is greater than or equal to a predetermined value N(threshold), the server immediately begins to serve the customers. If he finds less than N customers, he leaves for another vacation and so on until he finally finds at least N customers. We obtain the system size distribution and show that the system size decomposes into three random variables one of which is the system size of ordinary Mx/G/1 queue. The interpretation of the other random variables will be provided. We also derive the queue waiting time distribution and other performance measures. Finally we derive a condition under which the optimal stationary operating policy is achieved under a linear cost structure.

Modeling of manufacturing lines and data communications makes frequent use of tandem queues with blocking. Here we present and study such a system with a k-stage blocking scheme in which processing in each station requires attendance of the server of that station together with the servers of the next k – 1 stations. This scheme describes the conventional manufacturing and communications blocking schemes but is also representative of a wider range of applications. Explicit expressions for residence times, throughput, queueing times, waiting times and other measures of performance are obtained for the case of communications type flow and just-in-time input. Use of the results in modeling and analyzing a highway traffic flow situation is presented.

We consider preemptive scheduling on parallel machines where the number of available machines may be an arbitrary, possibly random, function of time. Processing times of jobs are from a family of DLR (decreasing likelihood ratio) distributions, and jobs may arrive at random agreeable times. We give a constructive coupling proof to show that LEPT stochastically minimizes the makespan, and that it minimizes the expected cost when the cost function satisfies certain agreeability conditions.

Let ℱ be a countable plane triangulation embedded in ℝ2 in such a way that no bounded region contains more than finitely many vertices, and let Pp be Bernoulli (p) product measure on the vertex set of ℱ. Let E be the event that a fixed vertex belongs to an infinite path whose vertices alternate states sequentially. It is shown that the AB percolation probability function θΑΒ (p) = Pp(E) is non-decreasing in p for 0 ≦ p ≦ ½. By symmetry, θ AΒ(p) is therefore unimodal on [0, 1]. This result partially verifies a conjecture due to Halley and stands in contrast to the examples of Łuczak and Wierman.

Some exact and asymptotic joint distributions are given for certain random variables defined on the excursions of a simple symmetric random walk. We derive appropriate recursion formulas and apply them to get certain expressions for the joint generating or characteristic functions of the random variables.

In this paper we study the departure process of M/G/1 queueing models with a single server vacation and multiple server vacations. The arguments employed are direct probability decomposition, renewal theory and the Laplace–Stieltjes transform. We discuss the distribution of the interdeparture time and the expected number of departures occurring in the time interval (0, t] from the beginning of the state i (i = 0, 1, 2, ···), and provide a new method for analysis of the departure process of the single-server queue.

We suggest a new universal method of stochastic simulation, allowing us to generate rather efficiently random vectors with arbitrary densities in a connected open region or on its boundary. Our method belongs to the class of dynamic Monte Carlo procedures and is based on a special construction of a Markov chain on the boundary of the region. Its remarkable feature is that this chain admits a simple simulation, based on a universal (depending only on the dimensionality of the space) stochastic driver.

The effects of dependencies (such as association) in the arrival process to a single server queue on mean queue lengths and mean waiting times are studied. Markov renewal arrival processes with a particular transition matrix for the underlying Markov chain are used which allow us to change dependency properties without at the same time changing distributional conditions. It turns out that correlations do not seem to be pure effects, and three main factors are studied: (a) differences in the mean interarrival times in the underlying Markov renewal process, (b) intensity in the Markov renewal jump process, (c) variability in the point processes underlying the Markov renewal process. It is shown that the mean queue length can be made arbitrarily large in the class of queues with the same interarrival distributions and the same service time distributions (with fixed smaller than one traffic intensity), by making (a) large enough and (b) small enough. The existence of the moments of interest is confirmed and some stochastic comparison results for actual waiting times are shown.

In this paper we obtain some new theoretical and numerial results on estimation of small steady-state probabilities in regenerative queueing models by using the likelihood ratio (score function) method, which is based on a change of the probability measure. For simple GI/G/1 queues, this amounts to simulating the regenerative cycles by a suitable change of the interarrival and service time distribution, typically corresponding to a reference traffic intensity ρ0 which is < 1 but larger than the given one ρ. For the M/M/1 queue, the resulting gain of efficiency is calculated explicitly and shown to be considerable. Simulation results are presented indicating that similar conclusions hold for gradient estimates and in more general queueing models like queueing networks.

There is a well-known connection between the asymptotic behaviour of the tail of the distribution of the increasing ladder height and the integrated tail of the step distribution of a random walk which either drifts to –∞, or oscillates and whose decreasing ladder height has finite mean. We establish a similar connection in a local sense; this means that in the lattice case we link the asymptotic behaviours of the mass function of the ladder height distribution and of the tail of the step distribution. We deduce the asymptotic behaviour of the mass function of the maximum of the walk, when this is finite, and also treat the non-lattice case.

A Markov-modulated Poisson process (MMPP) is a Poisson process whose rate is a finite Markov chain. The Poisson process is a simple MMPP. An MMPP/M/1 queue is a queue with MMPP arrivals, an infinite capacity, and a single exponential server. We prove that the output of an MMPP/M/1 queue is not an MMPP process unless the input is Poisson. We derive this result by analyzing the structure of the non-linear filter of the state given the departure process of the queue. The practical relevance of the result is that it rules out the existence of simple finite descriptions of queueing networks with MMPP inputs.

Certain last-exit and first-passage probabilities for random walks are approximated via a heuristic method suggested by a ladder variable argument. They yield satisfactory approximations of the first- and second-order moments of the queue length within a busy period of an M/D/1 queue. The approximation is applied to the wider class of random walks that arise in studying M/GI/1 queues. For gamma-distributed service times the queue length distribution is independent of the arrival rate. For other distributions where the arrival rate affects the queue length distribution, we have to use conjugate distributions in order to exploit a local central limit property. The limit underlying the approximation has the nature of a Brownian excursion.

The source of the problem lies in recent queueing inference work; the connection with Takács' interests comes from both queueing theory and the ballot theorem.

We consider a class of G/G/1 queueing models with independent generalized setup time and exhaustive service. It is shown that a variety of single-server queueing systems with service interruption are special cases of our model. We give a simple computational scheme for the moments of the stationary waiting time and sojourn time. Our numerical investigations indicate that the algorithm is quite accurate and fast in general. For the M/G/1 case, we are able to derive a recursive formula for the moments of the stationary waiting time, which includes the Takács formula as a special case. It immediately results in the stochastic decompòsition property which can be found in the literature.

We study the problem of maximizing the probability of stopping at an object which is best in at least one of a given set of criteria, using only stopping rules based on the knowledge of whether the current object is relatively best in each of the criteria. The asymptotic results for the case of independent criteria are shown to hold in certain cases where the componentwise maxima are, pairwise, either asymptotically independent or asymptotically full dependent.

An example of the former is a random sample from a bivariate correlated normal distribution; thus our results settle a question posed recently by T. S. Ferguson.

By an argument which involves matching sample paths, some useful equations for the probability distribution of the fundamental period in the MAP/G/1 queue are derived with less calculational effort than in earlier proofs. It is further shown that analogous equations hold for the MAP/SM/1 queueing model. These results are then used to derive explicit formulas for the mean vectors of the number served during and the duration of the fundamental period.

This article investigates the accuracy of approximations for the distribution of ordered m-spacings for i.i.d. uniform observations in the interval (0, 1). Several Poisson approximations and a compound Poisson approximation are studied. The result of a simulation study is included to assess the accuracy of these approximations. A numerical procedure for evaluating the moments of the ordered m-spacings is developed and evaluated for the most accurate approximation.

The long-tailed Luria–Delbrück distribution arises in connection with the ‘random mutation’ hypothesis (whereas the ‘directed adaptation' hypothesis is thought to give a Poisson distribution). At time t the distribution depends on the parameter m = gNt/(a + g) where Nt is the current population size and g/(a + g) is the relative mutation rate (assumed constant). The paper identifies three models for the distribution in the existing literature and gives a fourth model. Ma et al. (1992) recently proved that there is a remarkably simple recursion relation for the Luria–Delbrück probabilities pn and found that asymptotically pn ≈ c/n2; their numerical studies suggested that c = 1 when the parameter m is unity. Cairns et al. (1988) had previously argued and shown numerically that Pn = Σj ≧ n Pj ≈ m/n. Here we prove that n(n + 1)pn < m(1 + 11m/30) for n = 1, 2, ···, and hence prove that as n becomes large n(n + 1)pn, ≈ m; the result mPn ≈ m follows immediately.

This paper examines the infinitely high dam with seasonal (periodic) Lévy input under the unit release rule. We show that a periodic limiting distribution of dam content exists whenever the mean input over a seasonal cycle is less than 1. The Laplace transform of dam content at a finite time and the Laplace transform of the periodic limiting distribution are derived in terms of the probability of an empty dam. Necessary and sufficient conditions for the periodic limiting distribution to have finite moments are given. Convergence rates to the periodic limiting distribution are obtained from the moment results. Our methods of analysis lean heavily on the coupling method and a stochastic monotonicity result.

For a Markov chain in n = 2, drift vectors (conditional expected jumps) on the interior and the boundaries distinguish between recurrence and transience. The result of this paper is that the analogous proposition in the n = 3 case fails.