Ebook: Passage Times for Markov Chains

The purpose of this book is to present a unifying treatment of passage times in Markov chains, written in the systematic manner and based on modern developments, and to describe basic results of theoretical and practical importance.

Passage times have been investigated since early days of probability theory and its applications. The best known example is the first entrance time to a set, which embraces waiting times, absorption problems, extinction phenomena, busy periods and other applications. Another example, which only recently gains prominence, is the last exit time from a set.

The book is a survey of work on passage times in stable Markov chains with a discrete state space and a continuous time parameter. Although from the theoretical point of view stable chains are rather trite, nevertheless their structure is sufficiently rich to illustrate even the most sophisticated ideas. Moreover, such chains constitute bulk of applications, and it is here where the systematic unifying presentation is most desirable.

The main theme of this book is that the appropriate unifying framework for discussion of passage times is provided by the probabilistic potential theory, and all results presented in the text are interpreted from this point of view. Concepts of potentials, excessive functions and measures, balayage and duality, are freely used here. In particular, the crucial role of the Dirichlet problem and the Poisson equation, and various decomposition theorems, is stressed.

The starting point is to show that study of passage times depends essentially on a topological duality between functions and sets, which leads to the probabilistic representation by the notion of taboo probability (corresponding to killing of a chain at the first entrance). Properties of passage times are then linked to those of the first entrance time, and can be expressed in terms of taboo probabilities. The taboo probability becomes the central notion for the purpose of this book, both from the point of view of theory and of convergence in computation.

The objective is to obtain equations, or explicit expressions, for joint distributions of passage times and associated passage positions. Such equations for the first entrance times have been used in literature (usually with ad hoc justification), but those for the last exit times only recently become available. Although passage times are in fact examples of stopping and co-stopping times, they enjoy important position in theoretical aspects and in practical applications.

As it is well known, there are two complementary approaches to study of Markov chains, namely the “analytic approach” (dealing with equations for transition probabilities and Markov semi-groups) and the “measure theoretic approach” (dealing with sample functions properties and random sets). In this book the interdependence of both approaches is stressed to obtain the best results. However, for convenience of presentation, the first half of the book is more analytic in character, and measure theoretic discussion using functionals and martingales is postponed to the later part of the text.

Besides taboo probabilities, there are alternative starting points which could be used for presentation. One could start with the balayage properties (“product theorem”) and the Dynkin theorem for stopping times. It is also convenient to base presentation entirely on properties of Markovian functionals and use of martingales. In particular, the rigorous treatment of last exit times, excursions, and transformations of Markov chains is obtained in this manner. However, analysis is rather abstract, and the explicit determination again reduces to the use of taboo probabilities. Thus, although these methods are discussed in the text, taboo probabilities provide direct and convenient starting point. Concerning analytic tools, the book makes use of matrix formulation for the purpose of economy in notation, but matrix theory is not needed. Frequently, explicit expressions are provided to facilitate calculations.

The book consists of 4 chapters and an appendix. The first chapter (“Preliminaries”) summarizes the background material on Markov chains and their potential theory, and also on taboo probabilities. Next, passage times are introduced and methodology used in the book is explained.

The second chapter (“Analytic theory”) treats passage times in detail. The Dirichlet problem and the Poisson equation are discussed, and decomposition theorems and duality are examined.

The third chapter (“Measure theory”) introduces functionals and martingales, and presents various transformation of Markov chains (like reversing, killing, birthing, and a random time change). Several extensions are indicated, including composite passage times. This chapter is more advanced than previous chapters, and some of the results obtained earlier are here re-derived from a different point of view.

The last chapter (“Applications”) treats various practical systems, and discusses the notion of energy of a chain. One section presents rather meager introduction to boundary theory.

Illustrative examples are provided throughout the book, but Section 7 discusses some well-known examples (including classical absorption problems, busy periods and waiting times in Markovian queues, branching processes), whereas the last Section 13 presents more advanced examples (including perturbation, energy, random time change, martingales, and Revuz measure).

The presentation depends heavily on functional properties of Markov chains, like behavior of sample functions, strong Markov property, Kolmogorov equations, minimal process, and the jump chain. For the background material on Markov chains consult the monograph by K. L. Chung [1967j, who was the first to stress importance of taboo probabilities. For the background material on potential theory reference is made here to the monograph of R. M. Blumenthal and R. K. Getoor [1968]. Numerous other references are given in the text.

Despite all this, the book is addressed to applied probabilists, and to those who are interested in applications of probabilistic methods. The level of presentation is that of a graduate text in applied stochastic processes. In view of these aims, clarity of presentation takes precedence over secondary mathematical details whenever no serious harm may be expected. Advanced concepts needed in the text gain nowadays growing acceptance in applied fields, and it is hoped that this book will serve as an useful introduction. Indeed, it is rather exciting that such a narrow topic like passage times illustrates so well advanced concepts from probabilistic theories.

The author wishes to express his gratitude to Professors J. Glover, H. Gzyl, J. Mitro and H. Kaspi for pre-prints of their papers which have been very helpful to him. The author kept constantly in mind the appeal of Professor J. Keilson for search of a practical interpretation behind abstract formulations. Also, the friendly comment by Dr. P. Le Gall that nature is not Markovian, has been well taken. Last but not least, special thanks are due to Professor J. W. Cohen for his advice and for numerous friendly discussions spread over 40 years which have been always source of inspiration.

However, the author wants to make it clear that these writers are in no way, explicit or implicit, responsible for any misstatements, errors or distortions which may occur in this book.

Finally, it is a pleasure to thank Dr. E. Fredriksson (Director, IOS Press) for his interest in the publication of this book, and to the editors of IOS Press for their great care taken in its production.

R. Syski

College Park

October 1991