Computations with Markov Chains presents the edited and reviewed proceedings of the Second International Workshop on the Numerical Solution of Markov Chains, held January 16--18, 1995, in Raleigh, North Carolina. New developments of particular interest include recent work on stability and conditioning, Krylov subspace-based methods for transient solutions, quadratic convergent procedures for matrix geometric problems, further analysis of the GTH algorithm, the arrival of stochastic automata networks at the forefront of modelling stratagems, and more. An authoritative overview of the field for applied probabilists, numerical analysts and systems modelers, including computer scientists and engineers.

Great advances have been made in recent years in the field of computational probability. In particular, the state of the art - as it relates to queuing systems, stochastic Petri-nets and systems dealing with reliability - has benefited significantly from these advances. The objective of this book is to make these topics accessible to researchers, graduate students, and practitioners. Great care was taken to make the exposition as clear as possible. Every line in the book has been evaluated, and changes have been made whenever it was felt that the initial exposition was not clear enough for the intended readership. The work of major research scholars in this field comprises the individual chapters of Computational Probability. The first chapter describes, in nonmathematical terms, the challenges in computational probability. Chapter 2 describes the methodologies available for obtaining the transition matrices for Markov chains, with particular emphasis on stochastic Petri-nets. Chapter 3 discusses how to find transient probabilities and transient rewards for these Markov chains. The next two chapters indicate how to find steady-state probabilities for Markov chains with a finite number of states. Both direct and iterative methods are described in Chapter 4. Details of these methods are given in Chapter 5. Chapters 6 and 7 deal with infinite-state Markov chains, which occur frequently in queueing, because there are times one does not want to set a bound for all queues. Chapter 8 deals with transforms, in particular Laplace transforms. The work of Ward Whitt and his collaborators, who have recently developed a number of numerical methods for Laplace transform inversions, is emphasized in this chapter. Finally, if one wants to optimize a system, one way to do the optimization is through Markov decision making, described in Chapter 9. Markov modeling has found applications in many areas, three of which are described in detail: Chapter 10 analyzes discrete-time queues, Chapter 11 describes networks of queues, and Chapter 12 deals with reliability theory.

Papers presented at a workshop held January 1990 (location unspecified) cover just about all aspects of solving Markov models numerically. There are papers on matrix generation techniques and generalized stochastic Petri nets; the computation of stationary distributions, including aggregation/disaggregation.

A cornerstone of applied probability, Markov chains can be used to help model how plants grow, chemicals react, and atoms diffuse--and applications are increasingly being found in such areas as engineering, computer science, economics, and education. To apply the techniques to real problems, however, it is necessary to understand how Markov chains can be solved numerically. In this book, the first to offer a systematic and detailed treatment of the numerical solution of Markov chains, William Stewart provides scientists on many levels with the power to put this theory to use in the actual world, where it has applications in areas as diverse as engineering, economics, and education. His efforts make for essential reading in a rapidly growing field. Here Stewart explores all aspects of numerically computing solutions of Markov chains, especially when the state is huge. He provides extensive background to both discrete-time and continuous-time Markov chains and examines many different numerical computing methods--direct, single-and multi-vector iterative, and projection methods. More specifically, he considers recursive methods often used when the structure of the Markov chain is upper Hessenberg, iterative aggregation/disaggregation methods that are particularly appropriate when it is NCD (nearly completely decomposable), and reduced schemes for cases in which the chain is periodic. There are chapters on methods for computing transient solutions, on stochastic automata networks, and, finally, on currently available software. Throughout Stewart draws on numerous examples and comparisons among the methods he so thoroughly explains.

Markov chains are a fundamental class of stochastic processes. They are widely used to solve problems in a large number of domains such as operational research, computer science, communication networks and manufacturing systems. The success of Markov chains is mainly due to their simplicity of use, the large number of available theoretical results and the quality of algorithms developed for the numerical evaluation of many metrics of interest. The author presents the theory of both discrete-time and continuous-time homogeneous Markov chains. He carefully examines the explosion phenomenon, the Kolmogorov equations, the convergence to equilibrium and the passage time distributions to a state and to a subset of states. These results are applied to birth-and-death processes. He then proposes a detailed study of the uniformization technique by means of Banach algebra. This technique is used for the transient analysis of several queuing systems. Contents 1. Discrete-Time Markov Chains 2. Continuous-Time Markov Chains 3. Birth-and-Death Processes 4. Uniformization 5. Queues About the Authors Bruno Sericola is a Senior Research Scientist at Inria Rennes – Bretagne Atlantique in France. His main research activity is in performance evaluation of computer and communication systems, dependability analysis of fault-tolerant systems and stochastic models.

Critically acclaimed text for computer performance analysis--now in its second edition The Second Edition of this now-classic text provides a current and thorough treatment of queueing systems, queueing networks, continuous and discrete-time Markov chains, and simulation. Thoroughly updated with new content, as well as new problems and worked examples, the text offers readers both the theory and practical guidance needed to conduct performance and reliability evaluations of computer, communication, and manufacturing systems. Starting with basic probability theory, the text sets the foundation for the more complicated topics of queueing networks and Markov chains, using applications and examples to illustrate key points. Designed to engage the reader and build practical performance analysis skills, the text features a wealth of problems that mirror actual industry challenges. New features of the Second Edition include: * Chapter examining simulation methods and applications * Performance analysis applications for wireless, Internet, J2EE, and Kanban systems * Latest material on non-Markovian and fluid stochastic Petri nets, as well as solution techniques for Markov regenerative processes * Updated discussions of new and popular performance analysis tools, including ns-2 and OPNET * New and current real-world examples, including DiffServ routers in the Internet and cellular mobile networks With the rapidly growing complexity of computer and communication systems, the need for this text, which expertly mixes theory and practice, is tremendous. Graduate and advanced undergraduate students in computer science will find the extensive use of examples and problems to be vital in mastering both the basics and the fine points of the field, while industry professionals will find the text essential for developing systems that comply with industry standards and regulations.

"Constructive Computation in Stochastic Models with Applications: The RG-Factorizations" provides a unified, constructive and algorithmic framework for numerical computation of many practical stochastic systems. It summarizes recent important advances in computational study of stochastic models from several crucial directions, such as stationary computation, transient solution, asymptotic analysis, reward processes, decision processes, sensitivity analysis as well as game theory. Graduate students, researchers and practicing engineers in the field of operations research, management sciences, applied probability, computer networks, manufacturing systems, transportation systems, insurance and finance, risk management and biological sciences will find this book valuable. Dr. Quan-Lin Li is an Associate Professor at the Department of Industrial Engineering of Tsinghua University, China.

Probability, Markov Chains, Queues, and Simulation provides a modern and authoritative treatment of the mathematical processes that underlie performance modeling. The detailed explanations of mathematical derivations and numerous illustrative examples make this textbook readily accessible to graduate and advanced undergraduate students taking courses in which stochastic processes play a fundamental role. The textbook is relevant to a wide variety of fields, including computer science, engineering, operations research, statistics, and mathematics. The textbook looks at the fundamentals of probability theory, from the basic concepts of set-based probability, through probability distributions, to bounds, limit theorems, and the laws of large numbers. Discrete and continuous-time Markov chains are analyzed from a theoretical and computational point of view. Topics include the Chapman-Kolmogorov equations; irreducibility; the potential, fundamental, and reachability matrices; random walk problems; reversibility; renewal processes; and the numerical computation of stationary and transient distributions. The M/M/1 queue and its extensions to more general birth-death processes are analyzed in detail, as are queues with phase-type arrival and service processes. The M/G/1 and G/M/1 queues are solved using embedded Markov chains; the busy period, residual service time, and priority scheduling are treated. Open and closed queueing networks are analyzed. The final part of the book addresses the mathematical basis of simulation. Each chapter of the textbook concludes with an extensive set of exercises. An instructor's solution manual, in which all exercises are completely worked out, is also available (to professors only). Numerous examples illuminate the mathematical theories Carefully detailed explanations of mathematical derivations guarantee a valuable pedagogical approach Each chapter concludes with an extensive set of exercises

This book constitutes the refereed proceedings of the 6th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2003, held in Warsaw, Poland in April 2003.The 26 revised full papers presented together with an invited paper were carefully reviewed and selectednbsp; from 96 submissions. Among the topics covered are algebraic models; automata and language theory; behavioral equivalences; categorical models; computation processes over discrete and continuous data; computation structures; logics of programs; models of concurrent, reactive, distributed, and mobile systems; process algebras and calculi; semantics of programming languages; software specification and refinement; transition systems; and type systems and type theory.

There has been dramatic growth in the development and application of Bayesian inference in statistics. Berger (2000) documents the increase in Bayesian activity by the number of published research articles, the number of books,andtheextensivenumberofapplicationsofBayesianarticlesinapplied disciplines such as science and engineering. One reason for the dramatic growth in Bayesian modeling is the availab- ity of computational algorithms to compute the range of integrals that are necessary in a Bayesian posterior analysis. Due to the speed of modern c- puters, it is now possible to use the Bayesian paradigm to ?t very complex models that cannot be ?t by alternative frequentist methods. To ?t Bayesian models, one needs a statistical computing environment. This environment should be such that one can: write short scripts to de?ne a Bayesian model use or write functions to summarize a posterior distribution use functions to simulate from the posterior distribution construct graphs to illustrate the posterior inference An environment that meets these requirements is the R system. R provides a wide range of functions for data manipulation, calculation, and graphical d- plays. Moreover, it includes a well-developed, simple programming language that users can extend by adding new functions. Many such extensions of the language in the form of packages are easily downloadable from the Comp- hensive R Archive Network (CRAN).