Matrix Analytic Methods in Applied Probability with a View towards Engineering Applications

Queueing permeates most of man's commercial behaviour. People queue in stores, at banks, and at restaurants. Cars, ships and air-planes queue at roads, ports and runways, while electronic messages queue at transmission lines and in servers, waiting to be processed. The mathematical modelling of queueing phenomena has developed at ever increasing speed since the birth of queueing theory in the early 20th century, usually ascribed to A. K. Erlang, who worked as a mathematician for the Copenhagen Telephone Company (KTAS – Kjøbenhavns Telefons Aktie Selskab). Erlang is perhaps the foremost representative among many Danish and Scandinavian scientists who have contributed profoundly to queueing theory and the closely related field of risk theory, with insurance being its main application area. When modelling queueing systems a model is needed for the description of the random arrival stream of demands, in terms of customers in the various forms of people, cars, ships, or electronic messages. Point process theory arose from the field of applied probability to address this need.

The Markovian Arrival Process (MAP) is one of the main concrete manifestations of point process theory. The MAP is an essential building block within matrix analytic methods in queueing theory pioneered by Neuts and coauthors. The theory of matrix analytic methods is appealing from a practical point of view as many systems can be analytically and numerically evaluated using this approach.

In this thesis we present contributions to the theoretical development of the field of matrix analytic methods including an extension to a multivariate setting. We further demonstrate the applicability of the theory, giving examples from telecommunications engineering and computer science.

The thesis is based on a number of original contributions and a summary introductory paper. The outline of the summary is as follows.

The class of MAPs and the related class of Phase Type (PH) distributions belong to the slightly larger classes of what have been termed Rational Arrival Processes (RAP) and Matrix Exponential (ME) distributions, respectively. In Chapter 2 we present the basic constructions of phase-type and matrix-exponential distributions along with the Markovian and rational arrival processes. We briefly mention some well-known properties of these constructions while describing our own contributions in more detail. Chapter 3 is devoted to discussion of parameter estimation in the models described in Chapter 2. We give a very brief review of current estimation methods while focusing on our own contributions.

Chapters 4 and 5 contain different aspects of applications. The MAP is a versatile tool in sensitivity analyses of stochastic systems since point process descriptors of a MAP can be evaluated numerically. Sensitivity analyses based on the MAP are described in Chapter 4. That chapter is somewhat more generic in nature than Chapter 5 in which some concrete examples of engineering applications are presented.

In Chapter 6 we present two different ways of proving how the matrix analytic results related to the classical models of phase-type distributions and Markovian arrival processes extend to the case of matrix-exponential distributions and rational arrival processes.

In Chapter 7 we introduce the classes multivariate matrix-exponential and bilateral multivariate matrix-exponential distributions. The chapter starts with a small review of previous work on multivariate phase-type distributions while the rest of the chapter contains recent results of our own research.

The main contributions of the thesis are described in Chapters 4, 6, and 7. Chapter 4 is important from an engineering perspective. The approach described in reference [8] was somewhat controversial at the time. Measurements in packet based communication networks made some researchers call for a paradigm shift in queueing theory, where models based on Markovian assumptions would be, if not superfluous, then at least of minor importance. The contribution of [8] was to show that the Markovian arrival process could indeed remain a useful tool in modelling modern communication systems. The paper and its preliminary version reference [7] have been widely cited. Also reference [4] is important as this paper exemplifies how sensitivity analyses of queueing systems can be carried out using the Markovian arrival process, frequently leading to conclusions of general validity.

The two final chapters, 6 and 7, contain substantial theoretical contributions. The importance of Chapter 6 is at present primarily the mathematical content. It has been satisfying to finally settle the common anticipation that results for PH distributions and MAPs carry over verbatim to the case of ME distributions and RAPs. The method of proof has to rely on new ideas, as the standard probabilistic line of reasoning breaks down in the case of matrix-exponential distributions and rational arrival processes. Two different proof techniques were applied. In reference [17] a continuous time analysis based on a last exit time approach was applied. The approach taken in reference [18] was that of an embedded Markov chain with a general state space.

Finally Chapter 7 describes the contributions of the references [22, 24, 25, 28] containing the definition of the important class of bilateral multivariate matrix-exponential distributions together with examples of their use and various related results. These distributions provide a very flexible tool for modelling multivariate phenomena. The definition seems to be the natural multivariate generalisation of matrix-exponential distributions. The main result is a characterisation theorem similar to the main characterisation theorem of the multivariate normal distribution. Finally we demonstrate how the MVME distribution class unifies a number of previously published models in a way quite similar to the way PH and ME distributions unified a number of seemingly loosely connected models and results. The work described in Chapter 7 opens several non-trivial mathematical and theoretical questions. If just some of these problems can be solved satisfactorily it will pave the way for a huge application potential, and it is very likely that the distributions can and will be useful in statistical analysis too. The research on multivariate distributions lead to reference [27] describing a closure property of matrix-exponential and phase-type distributions.

In general, results from our own research will be stated as definitions, lemmas, corollaries, and theorems, while other results will be part of the text flow. The notation used in the papers is generally similar to that of the summary, and it is my hope that the slight differences will not reduce the accessibility of the papers.