In many communication and computer systems, information arrives to a multiplexer, switch or information processor at a rate which fluctuates randomly, often with a high degree of correlation in time. The information is buffered for service (the server typically being a communication channel or processing unit) and the service rate may also vary randomly. Accurate capture of the statistical properties of these fluctuations is facilitated by modeling the arrival and service rates as superpositions of a number of independent finite state reversible Markov processes. We call such models separable Markov-modulated rate processes (MMRP).

In this work a general mathematical model for separable MMRPs is presented, focusing on Markov-modulated continuous flow models. An efficient procedure for analyzing their performance is derived. It is shown that the ‘state explosion' problem typical of systems composed of a large number of subsystems, can be circumvented because of the separability property, which permits a decomposition of the equations for the equilibrium probabilities of these systems. The decomposition technique (generalizing a method proposed by Kosten) leads to a solution of the equilibrium equations expressed as a sum of terms in Kronecker product form. A key consequence of decomposition is that the computational complexity of the problem is vastly reduced for large systems. Examples are presented to illustrate the power of the solution technique.

A new coalescent is introduced to study the genealogy of a sample from the infinite-alleles model of population genetics. This coalescent also records the age ordering of alleles in the sample. The distribution of this process is found explicitly for the Moran model, and is shown to be robust for a wide class of reproductive schemes.

Properties of the ages themselves and the relationship between ages and class sizes then follow readily.

A method is reviewed for proving weak convergence in a function-space setting when regular variation is a sufficient condition. Point processes and weak convergence techniques involving continuity arguments play a central role. The method is dimensionless and holds computations to a minimum. Many applications of the methods to processes derived from sums and maxima are given.

This paper is a sequel to [7], in which heavy traffic limit theorems were proved for various stochastic processes arising in a single queueing facility with r arrival channels and s service channels. Here we prove similar theorems for sequences of such queueing facilities. The same heavy traffic behavior prevails in many cases in this more general setting, but new heavy traffic behavior is observed when the sequence of traffic intensities associated with the sequence of queueing facilities approaches the critical value (ρ = 1) at appropriate rates.

The aim of this paper is to present a comprehensive set of criteria for classifying as recurrent, transient, null or positive the sets visited by a general state space Markov chain. When the chain is irreducible in some sense, these then provide criteria for classifying the chain itself, provided the sets considered actually reflect the status of the chain as a whole. The first part of the paper is concerned with the connections between various definitions of recurrence, transience, nullity and positivity for sets and for irreducible chains; here we also elaborate the idea of status sets for irreducible chains. In the second part we give our criteria for classifying sets. When the state space is countable, our results for recurrence, transience and positivity reduce to the classical work of Foster (1953); for continuous-valued chains they extend results of Lamperti (1960), (1963); for general spaces the positivity and recurrence criteria strengthen those of Tweedie (1975b).

We consider a single-server queueing system in which a customer gives up whenever his waiting time is larger than a random threshold, his patience time. In the case of a GI/GI/1 queue with i.i.d. patience times, we establish the extensions of the classical GI/GI/1 formulae concerning the stability condition and the relation between actual and virtual waiting-time distribution functions. We also prove that these last two distribution functions coincide in the case of a Poisson input process and determine their common law.

In this paper, we clarify dependence properties of elliptical distributions by deriving general but explicit formulae for the coefficients of upper and lower tail dependence and spectral measures with respect to different norms. We show that an elliptically distributed random vector is regularly varying if and only if the bivariate marginal distributions have tail dependence. Furthermore, the tail dependence coefficients are fully determined by the tail index of the random vector (or equivalently of its components) and the linear correlation coefficient. Whereas Kendall's tau is invariant in the class of elliptical distributions with continuous marginals and a fixed dispersion matrix, we show that this is not true for Spearman's rho. We also show that sums of elliptically distributed random vectors with the same dispersion matrix (up to a positive constant factor) remain elliptical if they are dependent only through their radial parts.

The first-passage-time p.d.f. through a time-dependent boundary for one-dimensional diffusion processes is proved to satisfy a new Volterra integral equation of the second kind involving two arbitrary continuous functions. Use of this equation is made to prove that for the Wiener and the Ornstein–Uhlenbeck processes the singularity of the kernel can be removed by a suitable choice of these functions. A simple and efficient numerical procedure for the solution of the integral equation is provided and its convergence is briefly discussed. Use of this equation is finally made to obtain closed-form expressions for first-passage-time p.d.f.'s in the case of various time-dependent boundaries.

We consider two independent homogeneous Poisson processes Π0 and Π1 in the plane with intensities λ0 and λ1, respectively. We study additive functionals of the set of Π0-particles within a typical Voronoi Π1-cell. We find the first and the second moments of these variables as well as upper and lower bounds on their distribution functions, implying an exponential asymptotic behavior of their tails. Explicit formulae are given for the number and the sum of distances from Π0-particles to the nucleus within a typical Voronoi Π1-cell.

We consider a risk process with stochastic interest rate, and show that the probability of eventual ruin and the Laplace transform of the time of ruin can be found by solving certain boundary value problems involving integro-differential equations. These equations are then solved for a number of special cases. We also show that a sequence of such processes converges weakly towards a diffusion process, and analyze the above-mentioned ruin quantities for the limit process in some detail.

We have shown that within the setting of a difference equation it is possible to link ergodicity with stability via the physical notion of energy in the form of a Lyapunov function.

In this paper we study a new kind of option, called hereinafter a Parisian barrier option. This option is the following variant of the so-called barrier option: a down-and-out barrier option becomes worthless as soon as a barrier is reached, whereas a down-and-out Parisian barrier option is lost by the owner if the underlying asset reaches a prespecified level and remains constantly below this level for a time interval longer than a fixed number, called the window. Properties of durations of Brownian excursions play an essential role. We also study another kind of option, called here a cumulative Parisian option, which becomes worthless if the total time spent below a certain level is too long.

It is shown how Markov chain theory can be exploited to study non-linear time series, the emphasis being on the classification into stationary and non-stationary models. A generalized h-step version of the Tweedie (1975), (1976) criteria is formulated, and applications are given to a number of non-linear models. New results are obtained, and known results are shown to emerge as special cases in both the scalar and vector case. A connection to stability theory is briefly discussed, and it is indicated how the Markov property can be utilized for estimation purposes.

The paper is devoted to a systematic discussion of recently developed techniques for the study of weak convergence of sequences of stochastic processes. The methods described make essential use of the semimartingale structure of the processes. Sufficient conditions for tightness including the results of Rebolledo are derived. The techniques are applied to a special class of processes, namely the D-semimartingales. Applications to multitype branching processes are given.

This paper is in three parts. The first deals with the algebraic and topological structure of spaces of rational transfer function linear systems—ARMAX systems, as they have been called. This structure theory is dominated by the concept of a space of systems of order, or McMillan degree, n, because of the fact that this space, M(n), can be realised as a kind of high-dimensional algebraic surface of dimension n(2s + m) where s and m are the numbers of outputs and inputs. In principle, therefore, the fitting of a rational transfer model to data can be considered as the problem of determining n and then the appropriate element of M(n). However, the fact that M(n) appears to need a large number of coordinate neighbourhoods to cover it complicates the task. The problems associated with this program, as well as theory necessary for the analysis of algorithms to carry out aspects of the program, are also discussed in this first part of the paper, Sections 1 and 2.

The second part, Sections 3 and 4, deals with algorithms to carry out the fitting of a model and exhibits these algorithms through simulations and the analysis of real data.

The third part of the paper discusses the asymptotic properties of the algorithm. These properties depend on uniform rates of convergence being established for covariances up to some lag increasing indefinitely with the length of record, T. The necessary limit theorems and the analysis of the algorithms are given in Section 5. Many of these results are of interest independent of the algorithms being studied.

We consider the stability of the longest-queue-first scheduling policy (LQF), a natural and low-complexity scheduling policy, for a generalized switch model. Unlike that of common scheduling policies, the stability of LQF depends on the variance of the arrival processes in addition to their average intensities. We identify new sufficient conditions for LQF to be throughput optimal for independent, identically distributed arrival processes. Deterministic fluid analogs, proved to be powerful in the analysis of stability in queueing networks, do not adequately characterize the stability of LQF. We combine properties of diffusion-scaled sample path functionals and local fluid limits into a sharper characterization of stability.

For a birth–death process (X(t), ) on the state space {−1, 0, 1, ·· ·}, where −1 is an absorbing state which is reached with certainty and {0, 1, ·· ·} is an irreducible class, we address and solve three problems. First, we determine the set of quasi-stationary distributions of the process, that is, the set of initial distributions which are such that the distribution of X(t), conditioned on non-absorption up to time t, is independent of t. Secondly, we determine the quasi-limiting distribution of X(t), that is, the limit as t→∞ of the distribution of X(t), conditioned on non-absorption up to time t, for any initial distribution with finite support. Thirdly, we determine the rate of convergence of the transition probabilities of X(t), conditioned on non-absorption up to time t, to their limits. Some examples conclude the paper. Our main tools are the spectral representation for the transition probabilities of a birth–death process and a duality concept for birth–death processes.

Several partial orderings of counting processes are introduced and applied to compare stochastic processes in queueing models. The conditions for the queueing comparisons involve the counting processes associated with the interarrival and service times. The two queueing processes being compared are constructed on the same probability space so that each sample path of one process lies below the corresponding sample path of the other process. Stochastic comparisons between the processes and monotone functionals of the processes follow immediately from this construction. The stochastic comparisons are useful to obtain bounds for intractable systems. For example, the approach here yields bounds for queues with time-dependent arrival rates.

We consider a finite controlled Markov chain, the description of which depends on an unknown parameter a, and investigate the following control policy. To each a an optimal stationary control is associated. a is estimated recurrently from the trajectory by the minimum contrast method, and the optimal stationary control corresponding to the estimate is used. We present asymptotic properties of the estimate and of the criterion function. They follow from the law of large numbers and from the central limit theorem for controlled Markov chains derived with the aid of martingales.

A simple path transformation is described which connects one-dimensional Brownian motion with the radial part of three-dimensional Brownian motion. This provides simple proofs of various path decompositions for these processes described by David Williams.