Under consideration is a continuous-time Markov process with non-negative integer state space and a single absorbing state 0. Let T be the hitting time of zero and suppose Pi(T < ∞) ≡ 1 and (*) limi→∞Pi(T > t) = 1 for all t > 0. Most known cases satisfy (*). The Markov process has a quasi-stationary distribution iff Ei (e∊T) < ∞ for some ∊ > 0.

The published proof of this fact makes crucial use of (*). By means of examples it is shown that (*) can be violated in quite drastic ways without destroying the existence of a quasi-stationary distribution.

Each feasible transition between two distinct states i and j of a continuous-time, uniform, ergodic, countable-state Markov process gives a counting process counting the number of such transitions executed by the process. Traffic processes in Markovian queueing networks can, for instance, be represented as sums of such counting processes. We prove joint functional central limit theorems for the family of counting processes generated by all feasible transitions. We characterize which weighted sums of counts have zero covariance in the limit in terms of balance equations in the transition diagram of the process. Finally, we apply our results to traffic processes in a Jackson network. In particular, we derive simple formulas for the asymptotic covariances between the processes counting the number of customers moving between pairs of nodes in such a network.

This paper considers fluid queuing models of Markov-modulated traffic that, due to large differences in the time-scales of events, possess structural characteristics that yield a nearly completely decomposable (NCD) state-space. Extension of domain decomposition and aggregation techniques that apply to approximating the eigensystem of Markov chains permits the approximate subdivision of the full system to a number of small, independent subsystems (decomposition phase), plus an ‘aggregative' system featuring a state-space that distinguishes only one index per subsystem (aggregation phase). Perturbation analysis reveals that the error incurred by the approximation is of an order of magnitude equal to the weak coupling of the NCD Markov chain.

The study in this paper is then extended to the structure of NCD fluid models describing source superposition (multiplexing). It is shown that efficient spectral factorization techniques that arise from the Kronecker sum form of the global matrices can be applied through and combined with the decomposition and aggregation procedures. All structural characteristics and system parameters are expressible in terms of the individual sources multiplexed together, rendering the construction of the global system unnecessary.

Finally, besides providing efficient computational algorithms, the work in this paper can be recast as a conceptual framework for the better understanding of queueing systems under the presence of events happening in widely differing time-scales.

We consider scheduling a batch of jobs with stochastic processing times on single or parallel machines, with the objective of minimizing the expected holding costs. Preemption of jobs is allowed, and the holding costs of preempted jobs may depend on the stage of completion. We provide a new proof of the optimality of a Gittins priority rule for the single machine and use the same proof to show that the Gittins priority rule is nearly optimal for parallel machines.

We consider M/G/1 queues with exhaustive service and generalized vacations, where at the end of every busy period the server either follows a mixed vacation policy from a given vacation policy set or stays idle. A simple recursive formula for the moments of the stationary waiting time is provided. This formula results in the decomposition property for our model immediately. It also enables us to derive many existing results for the M/G/1 queues with various vacation policies.

A continuous-time, non-linear filtering problem is considered in which both signal and observation processes are Markov chains. New finite-dimensional filters and smoothers are obtained for the state of the signal, for the number of jumps from one state to another, for the occupation time in any state of the signal, and for joint occupation times of the two processes. These estimates are then used in the expectation maximization algorithm to improve the parameters in the model. Consequently, our filters and model are adaptive, or self-tuning.

This paper deals with a service system in which the processor must serve two types of impatient units. In the case of blocking, the first type units leave the system whereas the second type units enter a pool and wait to be processed later.

We develop an exhaustive analysis of the system including embedded Markov chain, fundamental period and various classical stationary probability distributions. More specific performance measures, such as the number of lost customers and other quantities, are also considered. The mathematical analysis of the model is based on the theory of Markov renewal processes, in Markov chains of M/G/l type and in expressions of ‘Takács' equation' type.

Conditions for a correlated cumulative shock model under which the system failure time is HNBUE are given. It is shown that the proof of a theorem given by Sumita and Shanthikumar (1985) relative to this property is not correct and a correct proof of the theorem is given.

We consider a multiserver queuing process specified by i.i.d. interarrival time, batch size and service time sequences. In the case that different servers have different service time distributions we say the system is heterogeneous. In this paper we establish conditions for the queuing process to be characterized as a geometrically Harris recurrent Markov chain, and we characterize the stationary probabilities of large queue lengths and waiting times. The queue length is asymptotically geometric and the waiting time is asymptotically exponential. Our analysis is a generalization of the well-known characterization of the GI/G/1 queue obtained using classical probabilistic techniques of exponential change of measure and renewal theory.

Convergence results are given for transient characteristics of an M/M/∞ system such as the period of time the occupation process remains above a given state, the area swept by this process above this state and the number of customers arriving during this period. These results are precise in contrast to approximations derived in the framework of the Poisson clumping heuristic introduced by Aldous.

The random k-dimensional partial order Pk(n) on n points is defined by taking n points uniformly at random from [0,1]k. Previous work has concentrated on the case where k is constant: we consider the model where k increases with n.

We pay particular attention to the height Hk(n) of Pk(n). We show that k = (t/log t!) log n is a sharp threshold function for the existence of a t-chain in Pk(n): if k – (t/log t!) log n tends to + ∞ then the probability that Pk(n) contains a t-chain tends to 0; whereas if the quantity tends to − ∞ then the probability tends to 1. We describe the behaviour of Hk(n) for the entire range of k(n).

We also consider the maximum degree of Pk(n). We show that, for each fixed d ≧ 2, is a threshold function for the appearance of an element of degree d. Thus the maximum degree undergoes very rapid growth near this value of k.

We make some remarks on the existence of threshold functions in general, and give some bounds on the dimension of Pk(n) for large k(n).

We study certain stochastic processes arising in probabilistic modelling. We discuss the limit behavior of these processes and estimate the rate of convergence to the limit.

We continue our investigation of the batch arrival-heterogeneous multiserver queue begun in Part I. In a general setting we prove the positive Harris recurrence of the system, and with no additional conditions we prove logarithmic tail limits for the stationary queue length and waiting time distributions.

A generalized semi-Markov process with reallocation (RGSMP) was introduced to accommodate a large class of stochastic processes which cannot be analyzed by the well-known model of an ordinary generalized semi-Markov process (GSMP). For stationary RGSMP whose initial distribution has a product form, we show that, for a randomly chosen clock of a fixed insensitive type, if the lifetime of this clock is changed to infinity, then the background process is stationary under a certain time change. This implies that the expected time required for the tagged clock to consume a given amount x of resource, called the attained sojourn time, is a linear function of x. Such stationarity and linearity results are known for two special RGSMPs: ordinary GSMP and Kelly's symmetric queue. Our results not only extend them to a general RGSMP but also give more detailed formulas, which allow us to calculate for instance the expected attained sojourn time while the background process is in a given state. Furthermore, we remark that analogous results hold for GSMP with point-process input, in which the lifetimes of clocks of a fixed type form an arbitrary stationary sequence (of not necessarily independent random variables).