G. George Yin

This book gives a systematic treatment of singularly perturbed systems that naturally arise in control and optimization, queueing networks, manufacturing systems, and financial engineering. It presents results on asymptotic expansions of solutions of Komogorov forward and backward equations, properties of functional occupation measures, exponential upper bounds, and functional limit results for Markov chains with weak and strong interactions. To bridge the gap between theory and applications, a large portion of the book is devoted to applications in controlled dynamic systems, production planning, and numerical methods for controlled Markovian systems with large-scale and complex structures in the real-world problems. This second edition has been updated throughout and includes two new chapters on asymptotic expansions of solutions for backward equations and hybrid LQG problems. The chapters on analytic and probabilistic properties of two-time-scale Markov chains have been almost completely rewritten and the notation has been streamlined and simplified. This book is written for applied mathematicians, engineers, operations researchers, and applied scientists. Selected material from the book can also be used for a one semester advanced graduate-level course in applied probability and stochastic processes.

This book gives a systematic treatment of singularly perturbed systems that naturally arise in control and optimization, queueing networks, manufacturing systems, and financial engineering. It presents results on asymptotic expansions of solutions of Komogorov forward and backward equations, properties of functional occupation measures, exponential upper bounds, and functional limit results for Markov chains with weak and strong interactions. To bridge the gap between theory and applications, a large portion of the book is devoted to applications in controlled dynamic systems, production planning, and numerical methods for controlled Markovian systems with large-scale and complex structures in the real-world problems. This second edition has been updated throughout and includes two new chapters on asymptotic expansions of solutions for backward equations and hybrid LQG problems. The chapters on analytic and probabilistic properties of two-time-scale Markov chains have been almost completely rewritten and the notation has been streamlined and simplified. This book is written for applied mathematicians, engineers, operations researchers, and applied scientists. Selected material from the book can also be used for a one semester advanced graduate-level course in applied probability and stochastic processes.

This book encompasses the study of hybrid switching di usion processes and their applications. The word \hybrid" signi es the coexistence of c- tinuous dynamics and discrete events, which is one of the distinct features of the processes under consideration. Much of the book is concerned with the interactions of the continuous dynamics and the discrete events. Our motivations for studying such processes originate from emerging and - isting applications in wireless communications, signal processing, queueing networks, production planning, biological systems, ecosystems, nancial engineering, and modeling, analysis, and control and optimization of lar- scale systems, under the in uence of random environments. Displaying mixture distributions, switching di usions may be described by the associated operators or by systems of stochastic di erential eq- tions together with the probability transition laws of the switching actions. We either have Markov-modulated switching di usions or processes with continuous state-dependent switching. The latter turns out to be much more challenging to deal with. Viewing the hybrid di usions as a number of di usions joined together by the switching process, they may be se- ingly not much di erent from their di usion counterpart. Nevertheless, the underlying problems become more di cult to handle, especially when the switching processes depend on continuous states. The di culty is due to the interaction of the discrete and continuous processes and the tangled and hybrid information pattern.

The basic stochastic approximation algorithms introduced by Robbins and MonroandbyKieferandWolfowitzintheearly1950shavebeenthesubject of an enormous literature, both theoretical and applied. This is due to the large number of applications and the interesting theoretical issues in the analysis of “dynamically de?ned” stochastic processes. The basic paradigm is a stochastic di?erence equation such as ? = ? + Y , where ? takes n+1 n n n n its values in some Euclidean space, Y is a random variable, and the “step n size” > 0 is small and might go to zero as n??. In its simplest form, n ? is a parameter of a system, and the random vector Y is a function of n “noise-corrupted” observations taken on the system when the parameter is set to ? . One recursively adjusts the parameter so that some goal is met n asymptotically. Thisbookisconcernedwiththequalitativeandasymptotic properties of such recursive algorithms in the diverse forms in which they arise in applications. There are analogous continuous time algorithms, but the conditions and proofs are generally very close to those for the discrete time case. The original work was motivated by the problem of ?nding a root of a continuous function g ¯(?), where the function is not known but the - perimenter is able to take “noisy” measurements at any desired value of ?. Recursive methods for root ?nding are common in classical numerical analysis, and it is reasonable to expect that appropriate stochastic analogs would also perform well.

This book focuses on two-time-scale Markov chains in discrete time. Our motivation stems from existing and emerging applications in optimization and control of complex systems in manufacturing, wireless communication, and ?nancial engineering. Much of our e?ort in this book is devoted to designing system models arising from various applications, analyzing them via analytic and probabilistic techniques, and developing feasible compu- tionalschemes. Ourmainconcernistoreducetheinherentsystemcompl- ity. Although each of the applications has its own distinct characteristics, all of them are closely related through the modeling of uncertainty due to jump or switching random processes. Oneofthesalientfeaturesofthisbookistheuseofmulti-timescalesin Markovprocessesandtheirapplications. Intuitively,notallpartsorcom- nents of a large-scale system evolve at the same rate. Some of them change rapidly and others vary slowly. The di?erent rates of variations allow us to reduce complexity via decomposition and aggregation. It would be ideal if we could divide a large system into its smallest irreducible subsystems completely separable from one another and treat each subsystem indep- dently. However, this is often infeasible in reality due to various physical constraints and other considerations. Thus, we have to deal with situations in which the systems are only nearly decomposable in the sense that there are weak links among the irreducible subsystems, which dictate the oc- sional regime changes of the system. An e?ective way to treat such near decomposability is time-scale separation. That is, we set up the systems as if there were two time scales, fast vs. slow. xii Preface Followingthetime-scaleseparation,weusesingularperturbationmeth- ology to treat the underlying systems.

This book concerns the identi?cation of systems in which only quantized output observations are available, due to sensor limitations, signal quan- zation, or coding for communications. Although there are many excellent treaties in system identi?cation and its related subject areas, a syst- atic study of identi?cation with quantized data is still in its early stage. This book presents new methodologies that utilize quantized information in system identi?cation and explores their potential in extending control capabilities for systems with limited sensor information or networked s- tems. The book is an outgrowth of our recent research on quantized iden- ?cation; it o?ers several salient features. From the viewpoint of targeted plants, it treats both linear and nonlinear systems, and both time-invariant and time-varying systems. In terms of noise types, it includes independent and dependent noises, stochastic disturbances and deterministic bounded noises, and noises with unknown distribution functions. The key meth- ologies of the book combine empirical measures and information-theoretic approaches to cover convergence, convergence rate, estimator e?ciency, - put design, threshold selection, and complexity analysis. We hope that it can shed new insights and perspectives for system identi?cation.

This book encompasses the study of hybrid switching di usion processes and their applications. The word \hybrid" signi es the coexistence of c- tinuous dynamics and discrete events, which is one of the distinct features of the processes under consideration. Much of the book is concerned with the interactions of the continuous dynamics and the discrete events. Our motivations for studying such processes originate from emerging and - isting applications in wireless communications, signal processing, queueing networks, production planning, biological systems, ecosystems, nancial engineering, and modeling, analysis, and control and optimization of lar- scale systems, under the in uence of random environments. Displaying mixture distributions, switching di usions may be described by the associated operators or by systems of stochastic di erential eq- tions together with the probability transition laws of the switching actions. We either have Markov-modulated switching di usions or processes with continuous state-dependent switching. The latter turns out to be much more challenging to deal with. Viewing the hybrid di usions as a number of di usions joined together by the switching process, they may be se- ingly not much di erent from their di usion counterpart. Nevertheless, the underlying problems become more di cult to handle, especially when the switching processes depend on continuous states. The di culty is due to the interaction of the discrete and continuous processes and the tangled and hybrid information pattern.

The basic stochastic approximation algorithms introduced by Robbins and MonroandbyKieferandWolfowitzintheearly1950shavebeenthesubject of an enormous literature, both theoretical and applied. This is due to the large number of applications and the interesting theoretical issues in the analysis of “dynamically de?ned” stochastic processes. The basic paradigm is a stochastic di?erence equation such as ? = ? + Y , where ? takes n+1 n n n n its values in some Euclidean space, Y is a random variable, and the “step n size” > 0 is small and might go to zero as n??. In its simplest form, n ? is a parameter of a system, and the random vector Y is a function of n “noise-corrupted” observations taken on the system when the parameter is set to ? . One recursively adjusts the parameter so that some goal is met n asymptotically. Thisbookisconcernedwiththequalitativeandasymptotic properties of such recursive algorithms in the diverse forms in which they arise in applications. There are analogous continuous time algorithms, but the conditions and proofs are generally very close to those for the discrete time case. The original work was motivated by the problem of ?nding a root of a continuous function g ¯(?), where the function is not known but the - perimenter is able to take “noisy” measurements at any desired value of ?. Recursive methods for root ?nding are common in classical numerical analysis, and it is reasonable to expect that appropriate stochastic analogs would also perform well.