Book review

The coupling method has become an important tool in probability theory for the last two decades, though its prehistory can be traced back to W. Doeblin.

The principal idea of coupling is extremely simple. Let us consider an aperiodic, irreducible, positive recurrent denumerable Markov chain <formula>. Introduce another Markov chain <formula> that is stationary, <formula> being its stationary probabilities, has the same transition matrix as X and independent of X. Denote <formula> and define a new Markov chain X" by equality <formula>. Evidently, the distribution of the chain X" coincides with that of X and hence, <formula>. Now, it is almost evident that, under our assumptions, the random time T must be finite and, therefore, the inequality above proves that the distribution of Xn tends to the stationary distribution while n -> °. Moreover, if we are able to evaluate a probability distribution of the random time T, then we can estimate the rate of convergence in the limiting relation mentioned above.

I tried reader's patience by exposing some formulas hoping for this is the shortest and clearest way to persuade the reader in advantages of the coupling method. It goes without saying that T. Lindvall starts his book with the same example (but in contrast to this review he does not limit himself to a single example). Even this example inspires several natural questions. For instance, it is not evident how to employ this simple construction for general Markov chains, when independence X and X', evidently, does not enable the random variable T to be finite, in almost all interesting cases. Another question: "Is the inequality above tight enough?" One can continue generating different questions. Roughly speaking (in fact, close to absurdity), the book is devoted to various applications of the coupling method as well as to its different modifications which enable to adopt the method to those applications.

The first dichotomy that appears in the book is discrete and continuous theories. The example above provides a hint to the reason of such dichotomy. Namely, in the discrete time case, there is a possibility to couple independent processes. The following examples are considered to illustrate the coupling method in the discrete time case.

¥ Discrete renewal theory: the key renewal theorem is proved under usual aperiodic assumptions.

¥ Denumerable Markov chains: the coupling is applied for investigating their limiting behaviour.

¥ Random walk: the fact of approaching (in terms of the total variation) of the distribution of a random walk to the similar distribution of a "delayed" random walk (that has a fixed nonzero initial state) is proved.

¥ Card shuffling of a deck with N cards: it is proved that there exists a threshold tN, such that the distribution of the "state" of the deck at time (1 - c)tN, for arbitrarily small c > 0, is "far" from the uniform distribution in the sense that the total variation distance between the two distributions tends to 2 while N -> °, but, if we take the distribution of the "state" of the deck at time (1 + c)tN, then the similar total variation distance tends to 0.

¥ Approximation of sums of i.i.d. random variables by Poisson distributions.

In my opinion, all these examples serve to show a variety of applications of the coupling metllod. More sophisticated continuous theory is engaged to depict difficulties which lead to the necessity of introducing new concepts of coupling and non-evident constructions. In the continuous case, the author considers the following examples: renewal theory, Harris chains, regenerative processes, continuous time Markov chains. These give him the possibility to introduce:

¥ a concept of c-coupling (when considering Blakwell's renewal theorem);

¥ "dependent coupling" (when obtaining the rate of convergence in Blakwell's renewal theorem in so-called spread-out case);

¥ "splitting" construction (in order to represent Harris chains as regenerative processes);

¥ maximal coupling (in order to prove that the coupling method can be adjusted to obtain correct bounds of the rates of convergence;

¥ collplirlg of regenerative processes (showing that this notion can be reduced, in some sense, to the coupling of renewal processes.

The following group of results presented in the book can be characterized as a revealing of relationships existing between some known concepts and coupling. Partial ordering, domination in different senses are such concepts. A basic idea of all these results is as follows. Given two probability distributions relate to each other in some sense (e.g., one distribution dominates another), construct two random variables (or, processes) which have the mentioned distributions as marginals and relate to each other in a similar way. One of the simplest propositions in this direction that can be given here to clarify the vague words above, is the following. Let F and F' be two distribution functions (on the real line) satisfying the ordering relation F >= F'. Given these functions, there exist a pair (X, X') of random variables such as F(x) = P(X <= x), F'(x) = P(X' <= x) and X <= X'. So, in this simple example, the ordering relation F >= F' existing between distribution functions corresponds to a similar relation X <= X' existing between random variables. In the book, more complicated examples are considered: Strassen's theorem, Markov processes, percolation, Bernstein polynomials and others. It is a pity that author does not even mention an analogy existing between the mentioned results and a concept of minimality of probability metrics. It seems to me that exploring this analogy can be fruitful.

The following group of applications of the coupling method is associated with random processes which can be defined in terms of transition intensities: birth and death processes, queueing networks, interacting particle systems, renewal theory, a special class of point processes.

At last, diffusion processes (one- and multidimensional) are considered. They definitely differ from the processes considered in other parts of the book and demand new ideas for construction of coupling.

It seems reasonable to make minor remarks concerning mainly the adopted way of presentation. The book "is designed as a premier introductory textbook" that "is intended to serve graduate courses and seminars in departments of mathematics, statistics, and operations research". But, very often, the reader needs to turn to other places of the book in order to understand a current notations or constructions. Renewal theory is one of the main topics of the book and so, it looks rather strange that the author does not refer directly to some papers (belonging, in his terminology, to "Russian coupling"), in which the rates of convergence in Blackwell's renewal theorem were obtained first. In addition, the term "Russian coupling" that calls to mind "Russian caviar" or "Islandic herring" is not adequate because does not enable to distinguish separate results obtained in this collection of works.

Appreciating the book as a whole, I agree that "Lectures on the Coupling Method is the first detailed, comprehensive examination of the coupling method, its many uses, and gaining influence in probability studies". A clear displaying of the material as well as a variety of examples must attract specialists and students to this efficient method.