Discrete‐time markov chains: two‐time‐scale methods and applications, G. George Yin and Qing Zhang, Springer, New York, U.S.A., 2005, 347 pp., ISBN 0‐387‐21948‐X
Yong Zeng · International Journal of Robust and Nonlinear Control · 2006
Two-time-scale Markov chains in discrete time, the focus of the book, stem from rich applications in optimization and control of complex systems. Applications include (but not limited to) manufacturing, internet traffic, wireless communication, and financial engineering. The use of two-time scales (‘fast’ vs ‘slow’ or ‘short-term’ vs ‘long-term’) in Markov process through regime-switching processes, one of the striking characteristics of the book, provides an efficient way to model real world problems and to reduce the inherent system complexity. With all the existing and emerging applications, this book furnishes a timely systematic treatment to two-time-scale Markovian systems and is an excellent reference on such topics. The book is suitable for applied mathematicians, operation researchers, applied probabilists, control scientists, and financial engineers. Chosen topics of this book can serve as an advanced graduate level course on stochastic processes and applications. Discrete-time Markov chains have a long-standing history in theory and applications. When the state space is finite but large, the decomposition of the transition matrix is an attractive approach. In the classical case when the transition matrix is decomposable into a diagonal block form of sub-transition matrices, the underlying problem can then be divided into subproblems, each of which is solvable completely and independently. By pasting together the solutions of the subproblems, one often is able to solve the whole problem. However, in the real world, most dynamic systems are unavoidably not only large and complicated, but also have interactions among many subsystems. Namely, instead of complete decomposability, one usually runs into nearly completely decomposable scenarios. That is, there are weak interactions among the irreducible blocks within which there are strong interactions and frequent changes while those weak interactions cause the less-frequent regime switches in the system. This suggests a hierarchical structure and is exactly where the two-time-scale method naturally comes to play. Intuitively, components or states of a large-scale system may change at distinct rate. Some of them may vary rapidly while others evolve slowly. So, many system can be set up with two time scales, fast vs slow. The two-time-scale method takes the advantages of the different variation speed via decomposition (of the transition matrix) and aggregation (of the clustering classes) so as to reduce the dimensionality of the underlying dynamic systems and the computation of the underlying problems. With the time-scale separation, the authors apply (a broad sense) singular perturbation methodology to deal with the aforementioned system. The authors study asymptotic properties of such systems as ε → 0 and deduce properties related to the probability distribution vectors and transition matrices and further examine the suitably scaled occupation measures. By integrating analytic and probabilistic methods, the authors provide a comprehensive study of the two-time-scale discrete-time Markov chain. There are three parts with fourteen chapters in the book. Part I, consisting of Chapters 1 and 2 and serving as a prologue, overviews the book and SUPplies the materials of mathematical background. Chapter 1 consists of a brief literature review and the motivation for the study of two time scale with several diverse and illustrative examples. Chapter 2 equips the basic (and not so basic) mathematical preliminary as a quick reference with suggested readings for further study. This includes the basic definitions such as Markov chains, martingales, diffusions, switching diffusions, basic notions such as Chapman–Kolmogorov equations, irreducibility, and quasi-stationary distributions, and their related properties. Part II, comprising Chapters 3–6, is the heart of the book and serves as the theoretical foundation for various applications in Part III. In Part II, the asymptotic properties and two-time-scale Markov chain is systematically studied in order to comprehend the intrinsic structure of such Markov chain. Chapter 3 uses the analytic techniques to develop the asymptotic expansions of the probability vectors and the transition matrices of a two-time-scale Markov chain specified by Equation (1). The asymptotic expansions consist of outer expansions and initial layer corrections. Furthermore, the approximation error bounds are obtained and the asymptotic series is justified. Chapter 4 uses the probability techniques (mainly weak convergence analysis) to further explore the asymptotic properties of such Markov chains by examining the occupation measure. The mean square type error bounds and the suitably scaled (central) limit distribution of the occupation measure are obtained. Strikingly (but not surprisedly), the limiting process turns out to be a regime-switching diffusion process. Chapter 5 further derives the large deviation exponential bounds for sequences of scaled occupation measures. In brief and roughly speaking, through the asymptotic expansion, Chapters 3–5 subsequently study the law of large number, the central limit theorem and the large deviation problems of the two-time-scale Markov chain. Chapter 6 is designed as an interlude summing up the useful results in Part II to be frequently applied to Part III. Part III tackles seven important applications in Chapters 7–13, respectively. The golden thread in these applications is that if, under suitable conditions, the limiting system has a certain (optimal) property, then so does the original system (nearly or asymptotically). The key issue is to take advantage of the two time scale decomposition in order to reduce the complexity in solving those problems, especially in computation, via appropriate aggregation. To understand the system's long-term behavior required in many engineering applications, Chapter 7 presents the stability analysis of the system governed by Equation (1) via Liapunov functions. Chapter 8 studies the hybrid filtering problem and shows that a limiting filtering problem can be derived in which the underlying Markov chain is replaced by a suitably-averaged chain with suitably-averaged system coefficients. Moreover, a discrete-time approximation of Wonham filter is obtained which provides the conditional probability of the underlying regime-shifting process. Motivated by applications in resource allocation, queueing networks, machine replacement and command control, Chapter 9 considers Markov decision processes characterized by a two-time-scale and control-dependent transition matrices in the form of Pε(u)=P(u)+εQ(u) where u is a control. Both discounted cost and long-run average cost criteria are considered. Chapter 10 handles linear quadratic regulator problems involving configuration switching. Applying dynamic programming results in a system of Riccati equations governing the optimal control laws. Under suitable conditions, the number of Riccati equations to be solved reduced substantially, leading to significant simplification in computation. Chapter 11 deals with the Markowitz's Nobel-price-winning mean-variance portfolio selection problem with regime-switching (such as ‘bull’ or ‘bear’ markets). Chapter 12 analyzes a class of near-optimal production planning problems for discrete-time planning of manufacturing systems. Chapter 13 deals with a class of stochastic approximation problems with regime switching. This has emerging applications to wireless communications in CDMA/DS (Code-Division Multiple-Access/implemented with Direct-Sequence). Finally, Chapter 14 is an Appendix containing concise discussions, basic notions and some technical results used in the book. The book has a list of 186 references with more than 40 of the authors' own contributions. Interested readers can find abundant further materials in this exciting new area. In the end of this book review, we only mention a few related books on this subject. Naidu 1 is an early book using singular perturbation methodology to study Markov chain and focusing on control. Sethi and Zhang 2 focuses on flexible manufacturing systems. Yin and Zhang (the same authors) 3 is on continuous-time Markov chain. Lastly, a recent book by Kabanov and Pergamenshchikov 4 studies the stochastic counterpart of Tikhonov–Levinson theory and its applications, and concentrates on the asymptotic analysis and control.