Probability, Markov Chains, Queues, and Simulation: The Mathematical Basis of Performance Modeling - Hardcover

Stewart, William J.

Hardcover

ISBN 10: 0691140626 ISBN 13: 9780691140629

Verlag: Princeton University Press, 2009

Inhaltsangabe

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

Über diesen Titel

Über die Autorin bzw. den Autor

William J. Stewart is professor of computer science at North Carolina State University. He is the author of An Introduction to the Numerical Solution of Markov Chains (Princeton).

Von der hinteren Coverseite

"This is an excellent book on the topics of probability, Markov chains, and queuing theory. Extremely well-written, the contents range from elementary topics to quite advanced material and include plenty of well-chosen examples."--Adarsh Sethi, University of Delaware

"Clear and pleasant to read, this book distinguishes itself from comparable textbooks by its inclusion of the computational aspects of the material."--Richard R. Muntz, University of California, Los Angeles

Aus dem Klappentext

"This is an excellent book on the topics of probability, Markov chains, and queuing theory. Extremely well-written, the contents range from elementary topics to quite advanced material and include plenty of well-chosen examples."--Adarsh Sethi, University of Delaware

"Clear and pleasant to read, this book distinguishes itself from comparable textbooks by its inclusion of the computational aspects of the material."--Richard R. Muntz, University of California, Los Angeles

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

PROBABILITY, MARKOV CHAINS, QUEUES, AND SIMULATION

The Mathematical Basis of Performance ModelingBy William J. Stewart

PRINCETON UNIVERSITY PRESS

Copyright © 2009 Princeton University Press
All right reserved.
ISBN: 978-0-691-14062-9

Contents

Preface and Acknowledgments................................................................xvI PROBABILITY..............................................................................11 Probability..............................................................................32 Combinatorics—The Art of Counting..................................................253 Random Variables and Distribution Functions..............................................404 Joint and Conditional Distributions......................................................645 Expectations and More....................................................................876 Discrete Distribution Functions..........................................................1157 Continuous Distribution Functions........................................................1348 Bounds and Limit Theorems................................................................180II MARKOV CHAINS...........................................................................1919 Discrete- and Continuous-Time Markov Chains..............................................19310 Numerical Solution of Markov Chains.....................................................285III QUEUEING MODELS........................................................................38311 Elementary Queueing Theory..............................................................38512 Queues with Phase-Type Laws: Neuts' Matrix-Geometric Method.............................44413 The z-Transform Approach to Solving Markovian Queues....................................47514 The M/G/1 and G/M/1 Queues..............................................................50915 Queueing Networks.......................................................................559IV SIMULATION..............................................................................61116 Some Probabilistic and Deterministic Applications of Random Numbers.....................61317 Uniformly Distributed "Random" Numbers..................................................62518 Nonuniformly Distributed "Random" Numbers...............................................64719 Implementing Discrete-Event Simulations.................................................68020 Simulation Measurements and Accuracy....................................................697Appendix A: The Greek Alphabet.............................................................719Appendix B: Elements of Linear Algebra.....................................................721Bibliography...............................................................................745Index......................................................................................749

Chapter One

Probability

1.1 Trials, Sample Spaces, and Events

The notions of trial, sample space, and event are fundamental to the study of probability theory. Tossing a coin, rolling a die, and choosing a card from a deck of cards are examples that are frequently used to explain basic concepts of probability. Each toss of the coin, roll of the die, or choice of a card is called a trial or experiment. We shall use the words trial and experiment interchangeably. Each execution of a trial is called a realization of the probability experiment.

At the end of any trial involving the examples given above, we are left with a head or a tail, an integer from one through six, or a particular card, perhaps the queen of hearts. The result of a trial is called an outcome. The set of all possible outcomes of a probability experiment is called the sample space and is denoted by Ω. The outcomes that constitute a sample space are also referred to as sample points or elements. We shall use ω to denote an element of the sample space.

Example 1.1 The sample space for coin tossing has two sample points, a head (H) and a tail (T). This gives Ω = {H, T}, as shown in Figure 1.1.

Example 1.2 For throwing a die, the sample space is Ω = {1, 2, 3, 4, 5, 6}, Figure 1.2, which represents the number of spots on the six faces of the die.

Example 1.3 For choosing a card, the sample space is a set consisting of 52 elements, one for each of the 52 cards in the deck, from the ace of spades through the king of hearts.

Example 1.4 If an experiment consists of three tosses of a coin, then the sample space is given by

{HHH, HHT, HTH, THH, HTT, THT, TTH, TTT}.

Notice that the element HHT is considered to be different from the elements HTH and THH, even though all three tosses give two heads and one tail. The position in which the tail occurs is important.

A sample space may be finite, denumerable (i.e., infinite but countable), or infinite. Its elements depend on the experiment and how the outcome of the experiment is defined. The four illustrative examples given above all have a finite number of elements.

Example 1.5 The sample space derived from an experiment that consists of observing the number of email messages received at a government office in one day may be taken to be denumerable. The sample space is denumerable since we may tag each arriving email message with a unique integer n that denotes the number of emails received prior to its arrival. Thus, Ω = {n|n [member of] N}, where N is the set of nonnegative integers.

Example 1.6 The sample space that arises from an experiment consisting of measuring the time one waits at a bus stop is infinite. Each outcome is a nonnegative real number x and the sample space is given by Ω = {x|x ≥ 0}.

If a finite number of trials is performed, then, no matter how large this number may be, there is no guarantee that every element of its sample space will be realized, even if the sample space itself is finite. This is a direct result of the essential probabilistic nature of the experiment. For example, it is possible, though perhaps not very likely (i.e., not very probable) that after a very large number of throws of the die, the number 6 has yet to appear.

Notice with emphasis that the sample space is a set, the set consisting of all the elements of the sample space, i.e., all the possible outcomes, associated with a given experiment. Since the sample space is a set, all permissible set operations can be performed on it. For example, the notion of subset is well defined and, for the coin tossing example, four subsets can be defined: the null subset φ the subsets {H}, {T}; and the subset that contains all the elements, Ω = {H, T}. The set of subsets of Ω is

φ, {H}, {T}, {H, T}.

Events

The word event by itself conjures up the image of something having happened, and this is no different in probability theory. We toss a coin and get a head, we throw a die and get a five, we choose a card and get the ten of diamonds. Each experiment has an outcome, and in these examples, the outcome is an element of the sample space. These, the elements of the sample space, are called the elementary events of the experiment. However, we would like to give a broader meaning to the term event.

Example 1.7 Consider...

Details zur Ausgabe

• Verlag: Princeton University Press
• Erscheinungsdatum: 2009
• Sprache: Englisch
• ISBN 10: 0691140626
• ISBN 13: 9780691140629
• Einband: Gebundene Ausgabe
• Anzahl der Seiten: 758
• Kontakt zum Hersteller: Nicht verfügbar
• Verantwortliche Person: Nicht verfügbar