Matrix-Analytic Methods

Preface

Contents

Author Index

Organisers

Reviewers

Sponsors

In this paper, we present a new method for finding the R matrix which plays a crucial role in determining the steady-state distribution of Markov chains of the GI/M/1 type. We formulate the problem as a non-linear programming problem. We first solve this problem by a steepest-descent-like algorithm and point out the limitations of this algorithm. Next, we carry out a perturbation analysis and develop a new algorithm which circumvents the limitations of the earlier algorithm. We perform numerical experiments and show that our algorithm performs better than what we call the “standard method” of solution.

In this paper we investigate the factors that determine the decay rate of discrete phase-type distributions when there are a countably-infinite number of phases.

A discrete phase-type distribution is any distribution that can be described as the time to absorption of a discrete-time Markov chain on a finite state space with a substochastic transition matrix T and honest initial probability distribution α. In this situation it has been known for a long time that the decay rate is always given by the maximal eigenvalue of T, regardless of the choice of initial distribution α.

In this paper we consider the same setting, but allow for the state space to consist of a countably-infinite number of phases. We find that the behaviour of the decay rate is now significantly more interesting.

We specifically consider phase type distributions where the transition matrix T is such that absorption can occur through only a finite number of phases and where T can be permuted to a form with a block upper-triangular structure. We explicitly investigate the situation where T has the structure of a level-dependent Quasi-Birth-and-Death process (QBD) and then extend this to the block upper-triangular structure.

Under these assumptions, we show that the decay-rate is always determined by either the convergence radius of the transition matrix, T, or the convergence radius of a series constructed from the initial distribution α and certain properties of T.

We develop algorithms for the computation of the distribution of the total reward accrued during [0,t) in a finite continuous-parameter Markov chain. During sojourns, the reward grows linearly at a rate depending on the state visited. At transitions, there can be instantaneous rewards whose values depend on the states involved in the transition. For moderate values of t, the reward distribution is obtained by implementing a series representation, due to Sericola, that is based on the uniformization method. As an alternative, that distribution can also be computed by the numerical inversion of its Laplace-Stieltjes transform. For larger values of t, we implement a matrix convolution product to compute a related semi-Markov matrix efficiently and accurately.

In this paper, we consider a multi-server queuing model with a finite buffer in which customers arrive according to a batch Markovian arrival process (BMAP). These customers are served in groups of varying sizes ranging from a predetermined value L through a maximum size, K. The service times are exponentially distributed. The number of servers in the system at any given time varies between a lower limit and an upper limit. The steady state analysis of the model is performed by exploiting the structure of the coefficient matrices. Some interesting numerical examples are discussed.

We consider an infinite buffer fluid queue driven by a Markovian environment and we analyze it by matrix analytic methods. We extend the recent work of Ramaswami by giving a more direct algorithm for the computation of the stationary distribution, as well as a clear probabilistic interpretation of this algorithm. We conclude the paper by a brief presentation of some numerical examples.

It has been noted that when fitting Coxian phase-type distributions to observed and simulated data by maximum likelihood, often a maximum corresponding to equality of two or more eigenvalues of the matrix of transition rates was found. Such equality of eigenvalues would contribute to the smoothness of the resulting probability density function. It is proposed to adjust the log-likelihood of the data by subtracting a quantity which penalises configurations that have disparate eigenvalues. The resulting penalised maximum likelihood estimation of the parameters specifying the transition rate matrix is discussed with reference to two example data-sets.

A family of approximations to the departure process from the MAP/PH/1 queue was proposed and demonstrated in Bean, Green and Taylor ¹. In this paper we extend these models to the departure process of a MAP/PH/1 feedback queue, where the probability of feedback may be level-dependent.

In this paper, we consider a production line consisting of machines working in series, at the same speed with independent exponential times before failure and times for repair. It can be shown that this production line has an exponential time before failure with rate equal to the sum of the individual machine failure rates. The repair time for the line is distributed as a mixture of exponentials (hyper-exponential). We compare an analysis using non-linear cost functions, based on the hyper-exponential distribution of repair times for the line with an approximation that assumes an exponential repair time. The approximate exponential repair time has a mean equal to a weighted average of the individual repair times, with weights proportional to the failure rates. Non-linear cost functions allow for differences between costs of: overtime, extra shifts, and failure to meet deadlines; or for deterioration of a product if it is left standing on a production line. We use a realistic example to demonstrate that the approximate analysis can underestimate costs by over 10%. We also present models for two production lines with one or two repair crews. In the instance of a single repair crew, we distinguish between a zero priority and a priority for line one case, and show, in contrast to a single line, that the stationary distributions are slightly different from approximations which assume the line repair times are exponentially distributed.

It has been shown recently that the Perron-Frobenius eigenvalue of a nonnegative matrix provides information for a complete classification of M/G/1 type Markov chains with a tree structure. The use of that ergodicity condition depends largely on the computation of a set of nonnegative matrices, which can be quite challenging. In this paper, without using a set of nonnegative matrices, we develop two linear programs whose solutions provide sufficient conditions for ergodicity of the Markov chains of interest. We also introduce a simple approximation to the ergodicity problem. Numerical examples demonstrate that the linear program approach, as well as the approximation approach, can be quite useful.

Fluid (or Hybrid) Petri Nets with flush-out arcs are Petri net based models with two classes of places: discrete places that carry a natural number of distinct objects (tokens), and fluid places that hold a positive amount of fluid, represented by a real number. For this kind of formalism, equations can be automatically derived from the model. Such equations, however, are often too complex to be solved analytically and simple discretization techniques usually can be successfully applied only to simple cases. In this paper we present a numerical technique for steady state solution that makes use of known matrix geometric techniques.

This paper introduces a set of Markovian Arrival Processes (MAPs) with a special structure exhibiting multifractal behavior. The considered MAP structure is motivated by the unnormalized Haar wavelet transform representation of finite sequences. A parameter fitting method is also proposed to approximate the multifractal behavior of experimental data sets by MAPs of the given structure. The goodness of the fitting method is evaluated via the log-moment diagrams, the partition function, the Legendre transform, and also by comparing the queue length distribution resulting from the measured data set with the one resulted from the approximating MAP.

We consider the counting measure associated with the Isotropic Phase Planar Point Process. We establish the convergence of the ratio of the variance of the count over its mean when the size of the considered set increases to ∞. The proof is based on a spectral decomposition of the involved matrices and is a good example that both matrix analytic and spectral analysis methods are useful tools to analyze MAP-like processes.

We consider a production system with a non-renewal batch input, maintenance period, setup period and bilevel threshold control. We model the system by the BMAP/G/1 queue with double thresholds and single vacation. We show how one can apply the factorization property to directly derive the vector generating functions of the queue length (the level of the work-in-process inventory) without going through all the standard procedure. We also present an example that shows the differences in mean queue length between BMAP/G/1 and M^x/G/1 queues under the same parameter settings.

In this paper, we study the transition matrix of M/G/1 type. The radius of convergence is discussed, conditions on the α-classification of the states are obtained, and expressions of the β-invariant measure are constructed. The censoring technique is generalized to deal with nonnegative matrices, which may be neither stochastic nor substochastic. This allows us to prove a factorization result for the discounted transition matrix. This factorization provides a unified algorithmic approach for expressing the β-invariant measure for transition matrices with a block-structure, including the matrix of M/G/1 type.

From the title of this paper, one may wonder why we need to go back to the Markov additive process, which had been actively studied long time ago. In the theory of stochastic processes, this may be a right question. However, the situation is different in the queueing theory. As long as the author knows, a modeling power of this additive process has not yet been fully utilized. Recent developments of the queueing theory are motivated by algorithmic solutions and rare events. For example, the matrix geometric approach belongs to the former class, while the large deviation technique belongs to the latter. We are also compelled by those two motivations. It is apparent that certain additive structure is always a clue to study them. For example, phase transitions have a nice additive structure in the M/G/1 type queues. So far, we shall attempt to discover new things by studying the older MAP, i.e., the Markov additive process, through scrutiny of the old. The reader will see nice structure of the Markov additive process in queues and their networks.

To model the quasi second order self-similarity, a tree structure Markovian arrival process (TSMAP) is introduced and effective calculations of spectral methods based on eigenvalues and eigenvectors for a TSMAP/G/1 are considered. Let D(z) be the z-transform of arrival rate matrices. For a TSMAP it is shown that for a real z all the eigenvalues of D(z) are real. Then the eigenvalues of D(1), the zero points of det(zI – A(z)) on the unit disk and the minimal zero point of det(zI – A(z)) greater than 1 are calculated by a bisection method, where A(z) is the probability generating matrix function of arrival numbers during the service time. Eigenvectors of D(1) and null vectors of zI – A(z) are inductively calculated by null vectors of submatrices. And for a TSMAP/G/1 queue, the stationary distribution at service completion epochs is effectively calculated by the Fourier inversion formula. Finally, we consider a numerical example of a TSMAP which has a second-order self-similar property. The stationary distribution and the asymptotic decreasing stationary distribution are numerically calculated.

We consider a finite state Markov chain whose state space is partioned in two sets, E₀ and E₁, and define a cycle as being constituted by a sojourn period in E₀ and another one in E₁. We characterize the bivariate sequences of sojourn times in and passage times into E₀ (E₁) and states visited at entrance times into E₀ (E₁), along with the sequence of cycle durations and the states visited at the beginning of cycles. We derive bivariate probability generating matrix functions of sojourn times in E₀ and E₁, and of cycle durations. Using these, we obtain expressions for moments of sojourn times in E₀ and E₁, and of cycle durations, including their expected values, variances and covariances. Stationary versions of the Markov chain are also discussed. The derived results are illustrated in a variant of the success runs for Bernoulli trials setting, where changes between two different success probabilities are allowed. The analysis shows that non-negligible correlations between sojourn times in a set of states and between cycle durations may arise, as illustrated through the considered example.

We consider a MAP/PH/1 queue whose interarrival time and service time processes are fitted to measurement data from commercial Web sites. A methodology is developed for this fitting of Web data to various instances of Markovian Arrival Processes (MAP). Numerical experiments are used to evaluate our approach and to analyze several performance measures of the MAP/PH/1 queue.

We study a class of parallel-server queues under scheduling disciplines that share the servers in both space and time. A matrix-analytic analysis of these queues is derived, making it possible to efficiently compute exact solutions for small to moderate instances of the stochastic model and providing very accurate approximations for larger model instances. We then exploit these results to analyze fundamental properties of parallel-server queues under spacesharing and timesharing.

This paper evaluates the robustness of FS-ALOHA, a random access algorithm used to reserve uplink—that is, from the end user to the network—bandwidth in centralized wireless access networks. The performance of FS-ALOHA when subject to Poisson arrivals and operating on an error free channel was evaluated in Vazquez et al ¹ by means of a Quasi-Birth-Death (QBD) Markov chain. In this paper we relax these assumptions and study discrete time batch Markovian arrivals on a channel with memoryless errors by means of a Markov chain of the GI/M/1 type. It is concluded that FS-ALOHA performs well under correlated and bursty arrivals and memoryless errors. However, error rates above 1/5T, where T is a protocol parameter, can seriously increase the delays suffered on the contention channel and might even make the system unstable. Finally, it is concluded that implementing multiple instances of FS-ALOHA can significantly improve the delays and the robustness of the algorithm.

The spectral radius of the rate matrix of a GI/M/1 type Markov chain characterizes long term high level behavior of the system. In this paper, an analytic expression of the spectral radius is established for its estimation. An effective numerical procedure is proposed for its computation. Numerical examples are presented to illustrate the effectiveness of the estimation.