Stochastic Modelling and Applied Probability - Böcker

This book serves as an introduction to queuing theory and provides a thorough treatment of tools like Markov processes, renewal theory, random walks, Levy processes, matrix-analytic methods and change of measure. It also treats in detail basic structures like GI/G/1 and GI/G/s queues, Markov-modulated models and queuing networks, and gives an introduction to areas such as storage, inventory, and insurance risk. Exercises are included and a survey of mathematical prerequisites is given in an appendix This much updated and expanded second edition of the 1987 original contains an extended treatment of queuing networks and matrix-analytic methods as well as additional topics like Poisson's equation, the fundamental matrix, insensitivity, rare events and extreme values for regenerative processes, Palm theory, rate conservation, Levy processes, reflection, Skorokhod problems, Loynes' lemma, Siegmund duality, light traffic, heavy tails, the Ross conjecture and ordering, and finite buffer problems. Students and researchers in statistics, probability theory, operations research, and industrial engineering will find this book useful.

Monte Carlo Methods are among the most broadly applicable and thus most powerful tools for valuing derivative securities and measuring their risks. As computer speeds continue to increase and new research expands the scope and efficiency of these methods, their use is destined to grow. This book is devoted to the use of Monte Carlo methods in finance. Advances in Monte Carlo methods in financial engineering take place at the interface between academic research and industry practice. This book targets that interface developing theory closely tied to applications. It is roughly divided into three parts: the first three chapters concentrate on the basics of Monte Carlo methods; the next three develop ways to improve Monte Carlo methods; and the final four chapters deal with more specialized problems arising, in particular applications of Monte Carlo to financial engineering. This book will serve as a reference for practitioners and researchers and will also be suitable as a graduate text for courses on computational finance.

The book presents a thorough development of the modern theory of stochastic approximation or recursive stochastic algorithms for both constrained and unconstrained problems. There is a complete development of both probability one and weak convergence methods for very general noise processes. The proofs of convergence use the ODE method, the most powerful to date, with which the asymptotic behavior is characterized by the limit behavior of a mean ODE. The assumptions and proof methods are designed to cover the needs of recent applications. The development proceeds from simple to complex problems, allowing the underlying ideas to be more easily understood. Rate of convergence, iterate averaging, high-dimensional problems, stability-ODE methods, two time scale, asynchronous and decentralized algorithms, general correlated and state-dependent noise, perturbed test function methods, and large devitations methods, are covered. Many motivational examples from learning theory, ergodic cost problems for discrete event systems, wireless communications, adaptive control, signal processing, and elsewhere, illustrate the application of the theory.This second edition is a thorough revision, although the main features and the structure remain unchanged. It contains many additional applications and results, and more detailed discussion. Harold J. Kushner is a University Professor and Professor of Applied Mathematics at Brown University. He has written numerous books and articles on virtually all aspects of stochastic systems theory, and has received various awards including the IEEE Control Systems Field Award.

Most manufacturing systems are large, complex, and operate in an environment of uncertainty. It is common practice to manage such systems in a hierarchical fashion. This book articulates a new theory that shows that hierarchical decision making can in fact lead to a near optimization of system goals. The material in the book cuts across disciplines. It will appeal to graduate students and researchers in applied mathematics, operations management, operations research, and system and control theory.

This book is intended as an introduction to optimal stochastic control for continuous time Markov processes and to the theory of viscosity solutions. The authors approach stochastic control problems by the method of dynamic programming. The text provides an introduction to dynamic programming for deterministic optimal control problems, as well as to the corresponding theory of viscosity solutions. Also covered are controlled Markov diffusions and viscosity solutions of Hamilton-Jacobi-Bellman equations. The authors have tried, through illustrative examples and selective material, to connect stochastic control theory with other mathematical areas (e.g. large deviations theory) and with applications to engineering, physics, management, and finance.In this Second Edition, new material on applications to mathematical finance has been added. Concise introductions to risk-sensitive control theory, nonlinear H-infinity control and differential games are also included.

The cycle representations of Markov processes have been advanced after the publication of the ?rst edition to many directions. One main purpose of these advances was the revelation of wide-ranging interpretations of the - cle decompositions of Markov processes such as homologic decompositions, orthogonality equations, Fourier series, semigroup equations, disinteg- tions of measures, and so on, which altogether express a genuine law of real phenomena. The versatility of these interpretations is consequently motivated by the existence of algebraic-topological principles in the fundamentals of the - clerepresentationsofMarkovprocesses,whicheliberatesthestandardview on the Markovian modelling to new intuitive and constructive approaches. For instance, the ruling role of the cycles to partition the ?nite-dimensional distributions of certain Markov processes updates Poincare's spirit to - scribing randomness in terms of the discrete partitions of the dynamical phase state; also, it allows the translation of the famous Minty's painting lemma (1966) in terms of the stochastic entities.Furthermore, the methods based on the cycle formula of Markov p- cesses are often characterized by minimal descriptions on cycles, which widelyexpressaphilosophicalanalogytotheKolmogoroveanentropicc- plexity. For instance, a deeper scrutiny on the induced Markov chains into smallersubsetsofstatesprovidessimplerdescriptionsoncyclesthanonthe stochastic matrices involved in the "taboo probabilities. " Also, the rec- rencecriteriaon cyclesimprovepreviousconditionsbased on thestochastic matrices, and provide plenty of examples.

Sampling-based computational methods have become a fundamental part of the numerical toolset of practitioners and researchers across an enormous number of different applied domains and academic disciplines. This book provides a broad treatment of such sampling-based methods, as well as accompanying mathematical analysis of the convergence properties of the methods discussed. The reach of the ideas is illustrated by discussing a wide range of applications and the models that have found wide usage. Given the wide range of examples, exercises and applications students, practitioners and researchers in probability, statistics, operations research, economics, finance, engineering as well as biology and chemistry and physics will find the book of value.

Our motivation for writing this book is twofold: First, the theory of waves propagating in randomly layered media has been studied extensively during the last thirty years but the results are scattered in many di?erent papers. This theory is now in a mature state, especially in the very interesting regime of separation of scales as introduced by G. Papanicolaou and his coauthors and described in [8], which is a building block for this book. Second, we were motivatedbythe time-reversalexperimentsofM. Finkandhis groupinParis. They were done with ultrasonic waves and have attracted considerable att- tion because of the surprising e?ects of enhanced spatial focusing and time compression in random media. An exposition of this work and its appli- tions is presented in [56]. Time reversal experiments were also carried out with sonar arrays in shallow water by W. Kuperman [113] and his group in San Diego. The enhanced spatial focusing and time compression of signals in time reversal in randommedia have many diverse applications in detection and in focused energy delivery on small targets as, for example, in the - struction of kidney stones. Enhanced spatial focusing is also useful in sonar and wireless communications for reducing interference. Time reversal ideas have played an important role in the development of new methods for array imaging in random media as presented in [19].

The present volume analyzes mathematical models of time-dependent physical p- nomena on three levels: microscopic, mesoscopic, and macroscopic. We provide a rigorous derivation of each level from the preceding level and the resulting me- scopic equations are analyzed in detail. Following Haken (1983, Sect. 1. 11. 6) we deal, “at the microscopic level, with individual atoms or molecules, described by their positions, velocities, and mutual interactions. At the mesoscopic level, we describe the liquid by means of ensembles of many atoms or molecules. The - tension of such an ensemble is assumed large compared to interatomic distances but small compared to the evolving macroscopic pattern. . . . At the macroscopic level we wish to study the corresponding spatial patterns. ” Typically, at the mac- scopic level, the systems under consideration are treated as spatially continuous systems such as ?uids or a continuous distribution of some chemical reactants, etc. Incontrast,onthemicroscopiclevel,Newtonianmechanicsgovernstheequationsof 1 motion of the individual atoms or molecules. These equations are cast in the form 2 of systems of deterministic coupled nonlinear oscillators. The mesoscopic level is probabilistic in nature and many models may be faithfully described by stochastic 3 ordinary and stochastic partial differential equations (SODEs and SPDEs), where the latter are de?ned on a continuum. The macroscopic level is described by ti- dependent partial differential equations (PDE’s) and its generalization and simpl- cations. In our mathematical framework we talk of particles instead of atoms and mo- cules. The transition from the microscopic description to a mesoscopic (i. e.

ThisresearchmonographdevelopstheHamilton-Jacobi-Bellman(HJB)theory viathedynamicprogrammingprincipleforaclassofoptimalcontrolproblems for stochastic hereditary di?erential equations (SHDEs) driven by a standard Brownian motion and with a bounded or an unbounded but fading m- ory. These equations represent a class of in?nite-dimensional stochastic s- tems that become increasingly important and have wide range of applications in physics, chemistry, biology, engineering, and economics/?nance. The wide applicability of these systems is due to the fact that the reaction of re- world systems to exogenous e?ects/signals is never “instantaneous” and it needs some time, time that can be translated into a mathematical language by some delay terms. Therefore, to describe these delayed e?ects, the drift and di?usion coe?cients of these stochastic equations depend not only on the current state but also explicitly on the past history of the state variable. The theory developed herein extends the ?nite-dimensional HJB theory of controlled di?usion processes to its in?nite-dimensional counterpart for c- trolledSHDEsinwhichacertainin?nite-dimensionalBanachspaceorHilbert space is critically involved in order to account for the bounded or unbounded memory. Another type of in?nite-dimensional HJB theory that is not treated in this monograph but arises from real-world application problems can often be modeled by controlled stochastic partial di?erential equations. Although they are both in?nite dimensional in nature and are both in the infancy of their developments, the SHDE exhibits many characteristics that are not in common with stochastic partial di?erential equations. Consequently, the HJB theory for controlled SHDEs is parallel to and cannot betreated as a subset of the theory developed for controlled stochastic partial di?erential equations.

Many aspects of phenomena critical to our lives can not be measured directly. Fortunately models of these phenomena, together with more limited obs- vations frequently allow us to make reasonable inferences about the state of the systems that a?ect us. The process of using partial observations and a stochastic model to make inferences about an evolving system is known as stochastic ?ltering. The objective of this text is to assist anyone who would like to become familiar with the theory of stochastic ?ltering, whether graduate student or more experienced scientist. The majority of the fundamental results of the subject are presented using modern methods making them readily available for reference. The book may also be of interest to practitioners of stochastic ?ltering, who wish to gain a better understanding of the underlying theory. Stochastic ?ltering in continuous time relies heavily on measure theory, stochasticprocessesandstochasticcalculus.Whileknowledgeofbasicmeasure theory and probability is assumed, the text is largely self-contained in that the majority of the results needed are stated in two appendices. This should make it easy for the book to be used as a graduate teaching text. With this in mind, each chapter contains a number of exercises, with solutions detailed at the end of the chapter.

The first part of this book presents the essential topics for an introduction to deterministic optimal control theory. The second part introduces stochastic optimal control for Markov diffusion processes. It also inlcudes two other topics important for applications, namely, the solution to the stochastic linear regulator and the separation principle.

The basis for this book is a number of lectures given frequently by the author to third year students of the Department of Economics at Leningrad State University who specialize in economical cybernetics. The main purpose of this book is to provide the student with a relatively simple and easy-to-understand manual containing the basic mathematical machinery utilized in the theory of games. Practical examples (including those from the field of economics) serve mainly as an interpretation of the mathematical foundations of this theory rather than as indications of their actual or potential applicability. The present volume is significantly different from other books on the theory of games. The difference is both in the choice of mathematical problems as well as in the nature of the exposition. The realm of the problems is somewhat limited but the author has tried to achieve the greatest possible systematization in his exposition. Whenever possible the author has attempted to provide a game-theoretical argument with the necessary mathematical rigor and reasonable generality. Formal mathematical prerequisites for this book are quite modest. Only the elementary tools of linear algebra and mathematical analysis are used.

The book deals mainly with three problems involving Gaussian stationary processes. The first problem consists of clarifying the conditions for mutual absolute continuity (equivalence) of probability distributions of a "random process segment" and of finding effective formulas for densities of the equiva­ lent distributions. Our second problem is to describe the classes of spectral measures corresponding in some sense to regular stationary processes (in par­ ticular, satisfying the well-known "strong mixing condition") as well as to describe the subclasses associated with "mixing rate". The third problem involves estimation of an unknown mean value of a random process, this random process being stationary except for its mean, i. e. , it is the problem of "distinguishing a signal from stationary noise". Furthermore, we give here auxiliary information (on distributions in Hilbert spaces, properties of sam­ ple functions, theorems on functions of a complex variable, etc. ). Since 1958 many mathematicians have studied the problem of equivalence of various infinite-dimensional Gaussian distributions (detailed and sys­ tematic presentation of the basic results can be found, for instance, in [23]). In this book we have considered Gaussian stationary processes and arrived, we believe, at rather definite solutions. The second problem mentioned above is closely related with problems involving ergodic theory of Gaussian dynamic systems as well as prediction theory of stationary processes.

This book is based on a seminar given at the University of California at Los Angeles in the Spring of 1975. The choice of topics reflects my interests at the time and the needs of the students taking the course. Initially the lectures were written up for publication in the Lecture Notes series. How­ ever, when I accepted Professor A. V. Balakrishnan's invitation to publish them in the Springer series on Applications of Mathematics it became necessary to alter the informal and often abridged style of the notes and to rewrite or expand much of the original manuscript so as to make the book as self-contained as possible. Even so, no attempt has been made to write a comprehensive treatise on filtering theory, and the book still follows the original plan of the lectures. While this book was in preparation, the two-volume English translation of the work by R. S. Liptser and A. N. Shiryaev has appeared in this series. The first volume and the present book have the same approach to the sub­ ject, viz. that of martingale theory. Liptser and Shiryaev go into greater detail in the discussion of statistical applications and also consider inter­ polation and extrapolation as well as filtering.

Shortly after the end of World War II high-speed digital computing machines were being developed. It was clear that the mathematical aspects of com­ putation needed to be reexamined in order to make efficient use of high-speed digital computers for mathematical computations. Accordingly, under the leadership of Min a Rees, John Curtiss, and others, an Institute for Numerical Analysis was set up at the University of California at Los Angeles under the sponsorship of the National Bureau of Standards. A similar institute was formed at the National Bureau of Standards in Washington, D. C. In 1949 J. Barkeley Rosser became Director of the group at UCLA for a period of two years. During this period we organized a seminar on the study of solu­ tions of simultaneous linear equations and on the determination of eigen­ values. G. Forsythe, W. Karush, C. Lanczos, T. Motzkin, L. J. Paige, and others attended this seminar. We discovered, for example, that even Gaus­ sian elimination was not well understood from a machine point of view and that no effective machine oriented elimination algorithm had been developed. During this period Lanczos developed his three-term relationship and I had the good fortune of suggesting the method of conjugate gradients. We dis­ covered afterward that the basic ideas underlying the two procedures are essentially the same. The concept of conjugacy was not new to me. In a joint paper with G. D.

Stochastic control theory is a relatively young branch of mathematics. The beginning of its intensive development falls in the late 1950s and early 1960s. During that period an extensive literature appeared on optimal stochastic control using the quadratic performance criterion (see references in W onham [76J). At the same time, Girsanov [25J and Howard [26J made the first steps in constructing a general theory, based on Bellman's technique of dynamic programming, developed by him somewhat earlier [4J. Two types of engineering problems engendered two different parts of stochastic control theory. Problems of the first type are associated with multistep decision making in discrete time, and are treated in the theory of discrete stochastic dynamic programming. For more on this theory, we note in addition to the work of Howard and Bellman, mentioned above, the books by Derman [8J, Mine and Osaki [55J, and Dynkin and Yushkevich [12]. Another class of engineering problems which encouraged the development of the theory of stochastic control involves time continuous control of a dynamic system in the presence of random noise. The case where the system is described by a differential equation and the noise is modeled as a time continuous random process is the core of the optimal control theory of diffusion processes. This book deals with this latter theory.

As more applications are found, interest in Hidden Markov Models continues to grow. Following comments and feedback from colleagues, students and other working with Hidden Markov Models the corrected 3rd printing of this volume contains clarifications, improvements and some new material, including results on smoothing for linear Gaussian dynamics. In Chapter 2 the derivation of the basic filters related to the Markov chain are each presented explicitly, rather than as special cases of one general filter. Furthermore, equations for smoothed estimates are given. The dynamics for the Kalman filter are derived as special cases of the authors’ general results and new expressions for a Kalman smoother are given. The Chapters on the control of Hidden Markov Chains are expanded and clarified. The revised Chapter 4 includes state estimation for discrete time Markov processes and Chapter 12 has a new section on robust control.

This book provides a unified, comprehensive treatment of some recent theoretical developments on Markov control processes. Interest is mainly confined to MCPs with Borel state and control spaces, and possibly unbounded costs and non-compact control constraint sets. The control model studied is sufficiently general to include virtually all the usual discrete-time stochastic control models that appear in applications to engineering, economics, mathematical population processes, operations research, and management science. Much of the material appears for the first time in book form.

Pattern recognition presents one of the most significant challenges for scientists and engineers, and many different approaches have been proposed. The aim of this book is to provide a self-contained account of probabilistic analysis of these approaches. The book includes a discussion of distance measures, nonparametric methods based on kernels or nearest neighbors, Vapnik-Chervonenkis theory, epsilon entropy, parametric classification, error estimation, free classifiers, and neural networks. Wherever possible, distribution-free properties and inequalities are derived. A substantial portion of the results or the analysis is new. Over 430 problems and exercises complement the material.

The theory of probability began in the seventeenth century with attempts to calculate the odds of winning in certain games of change. However, it was not until the middle of the twentieth century that mathematicians developed general techniques for maximizing the chances of beating a casino or winning against an intelligent opponent. These methods of finding optimal strategies are at the heart of the modern theory of stochastic control and stochastic games. This monograph provides an introduction to the ideas of gambling theory and stochastic games. The first chapters introduce the ideas and notation of gambling theory. Chapters 3 and 4 consider "leavable" and "nonleavable" problems which form the core theory of this subject. Chapters 5, 6, and 7 cover stationary strategies, approximate gambling problems, and two-person zero-sum stochastic games respectively. Throughout, the authors have included examples and there are problem sets at the end of each chapter.

Changes in the second edition. The second edition differs from the first in that there is a full development of problems where the variance of the diffusion term and the jump distribution can be controlled. Also, a great deal of new material concerning deterministic problems has been added, including very efficient algorithms for a class of problems of wide current interest. This book is concerned with numerical methods for stochastic control and optimal stochastic control problems. The random process models of the controlled or uncontrolled stochastic systems are either diffusions or jump diffusions. Stochastic control is a very active area of research and new problem formulations and sometimes surprising applications appear regu­ larly. We have chosen forms of the models which cover the great bulk of the formulations of the continuous time stochastic control problems which have appeared to date. The standard formats are covered, but much emphasis is given to the newer and less well known formulations. The controlled process might be either stopped or absorbed on leaving a constraint set or upon first hitting a target set, or it might be reflected or "projected" from the boundary of a constraining set. In some of the more recent applications of the reflecting boundary problem, for example the so-called heavy traffic approximation problems, the directions of reflection are actually discontin­ uous. In general, the control might be representable as a bounded function or it might be of the so-called impulsive or singular control types.

This accessible and timely book collects in a single volume the essentials of stochastic networks, from the classical product-form theory to the more recent developments such as diffusion and fluid limits, stochastic comparisons, stability, control (dynamic scheduling) and optimization.The book was developed from the authors' teaching stochastic networks over many years. It will be useful to students from engineering, business, mathematics, and probability and statistics. As stochastic networks have become widely used as a basic model of many physical systems in a diverse range of fields, the book can also be used as a reference or supplementary readings for courses in operations research, computer systems, communication networks, production planning and logistics, and by practitioners in the field.

This book provides a thorough development of the powerful methods of heavy traffic analysis and approximations with applications to a wide variety of stochastic (e.g. queueing and communication) networks, for both controlled and uncontrolled systems.The approximating models are reflected stochastic differential equations. The analytical and numerical methods yield considerable simplifications and insights and good approximations to both path properties and optimal controls under broad conditions on the data and structure.The general theory is developed, with possibly state dependent parameters, and specialized to many different cases of practical interest.Control problems in telecommunications and applications to scheduling, admissions control, polling, and elsewhere are treated. The necessary probability background is reviewed, including a detailed survey of reflected stochastic differential equations, weak convergence theory, methods for characterizing limit processes, and ergodic problems.

Stochastic portfolio theory is a mathematical methodology for constructing stock portfolios and for analyzing the effects induced on the behavior of these portfolios by changes in the distribution of capital in the market.Stochastic portfolio theory has both theoretical and practical applications: as a theoretical tool it can be used to construct examples of theoretical portfolios with specified characteristics and to determine the distributional component of portfolio return. On a practical level, stochastic portfolio theory has been the basis for strategies used for over a decade by the institutional equity manager INTECH, where the author has served as chief investment officer. This book is an introduction to stochastic portfolio theory for investment professionals and for students of mathematical finance. Each chapter includes a number of problems of varying levels of difficulty and a brief summary of the principal results of the chapter, without proofs.

In wntmg this monograph my aim has been to present a "geometric" approach to the structural synthesis of multivariable control systems that are linear, time-invariant and of finite dynamic order. The book is ad­ dressed to graduate students specializing in control, to engineering scientists involved in control systems research and development, and to mathemati­ cians interested in systems control theory. The label "geometric" in the title is applied for several reasons. First and obviously, the setting is linear state space and the mathematics chiefly linear algebra in abstract (geometric) style. The basic ideas are the familiar system concepts of controllability and observability, thought of as geometric prop­ erties of distinguished state subspaces. Indeed, the geometry was first brought in out of revulsion against the orgy of matrix manipulation which linear control theory mainly consisted of, around fifteen years ago. But secondly and of greater interest, the geometric setting rather quickly sug­ gested new methods of attacking synthesis which have proved to be intuitive and economical; they are also easily reduced to matrix arithmetic as soon as you want to compute. The essence of the "geometric" approach is just this: instead of looking directly for a feedback law (say u = Fx) which would solve your synthesis problem if a solution exists, first characterize solvability as a verifiable property of some constructible state subspace, say Y. Then, if all is well, you may calculate F from Y quite easily.

The problem of controlling or stabilizing a system of differential equa­ tions in the presence of random disturbances is intuitively appealing and has been a motivating force behind a wide variety of results grouped loosely together under the heading of "Stochastic Control." This book is concerned with a special instance of this general problem, the "Adaptive LQ Regulator," which is a stochastic control problem of partially observed type that can, in certain cases, be solved explicitly. We first describe this problem, as it is the focal point for the entire book, and then describe the contents of the book. The problem revolves around an uncertain linear system x(O) = x~ in R", where 0 E {1, ... , N} is a random variable representing this uncertainty and (Ai' B , C) and xJ are the coefficient matrices and initial state, respectively, of j j a linear control system, for eachj = 1, ... , N. A common assumption is that the mechanism causing this uncertainty is additive noise, and that conse­ quently the "controller" has access only to the observation process y( . ) where y = Cex +~.

This monograph gives a self-contained treatment of stochastic processes arising from models for queues, insurance risk, and dams and data communication, using their sample function properties. The approach is based on the fluctuation theory of random walks, L vy processes, and Markov-additive processes, in which Wiener-Hopf factorization plays a central role. The second edition includes results for the virtual waiting time and queue length in single server queues. The treatment of continuous time storage processes is thoroughly revised and simplified. Markov- modulated storage processes are inlcuded in Part III with application to data communication models. The book can be used as a text for an advanced course on applied probability models. The prerequisite is a graduate-level course in probability and stochastic processes.

This book is devoted to a systematic exposition of some recent developments in the theory of discrete-time Markov control processes. Interest is mainly confined to MCPs with Borel state and control spaces, and possibly unbounded costs. The book follows on from the authors earlier volume in this area, however, an important feature of the present volume is that it is essentially self-contained and can be read independently of the first volume, because although both volumes deal with similar classes of markov control processes the assumptions on the control models are usually different. This volume allows cost functions to take positive or negative values, as needed in some applications. The control model studied is sufficiently general to include virtually all the usual discrete-time stochastic control models that appear in applications to engineering, economics, mathematical population processes, operations research, and management science.