Probability models for computer science / Sheldon M. Ross.

Includes bibliographical references (p. 283) and index.

Machine generated contents note: 1 Probability 1 -- 1.1 Axioms of Probability 1 -- 1.2 Conditional Probability and Independence 1 -- 1.3 Random Variables 2 -- 1.4 Expected Value and Variance 5 -- 1.4.1 Expected Value and Variance of Sums of Random Variables 7 -- 1.5 Moment-Generating Functions and Laplace Transforms 17 -- 1.6 Conditional Expectation 20 -- 1.7 Exponential Random Variables 32 -- 1.8 Limit Theorems 41 -- 1.8.1 Stopping Times and Wald's Equation 42 -- Exercises 43 -- 2 Some Examples 49 -- 2.1 A Random Graph 49 -- 2.2 The Quicksort and Find Algorithms 55 -- 2.2.1 The Find Algorithm 58 -- 2.3 A Self-Organizing List Model 61 -- 2.4 Random Permutations 62 -- 2.4.1 Inversions 66 -- 2.4.2 Increasing Subsequences 69 -- Exercises 71 -- 3 Probability Bounds, Approximations, -- and Computations 75 -- 3.1 'ail Probability Inequalities 75 -- 3.1.1 Markov's Inequality 75 -- 3.1.2 Chernoff Bounds 76 -- 3.1.3 Jensen's Inequality 79 -- 3.2 The Second Moment and the Conditional -- Expectation Inequality 79 -- 3.3 Probability Bounds via the Importance Sampling Identity 87 -- 3.4 Poisson Random Variables and the Poisson Paradigm 89 -- 3.5 Compound Poisson Random Variables 94 -- 3.5.1 A Second Representation when the Component -- Distribution Is Discrete 95 -- 3.5.2 A Compound Poisson identity 96 -- Exercises 100 -- 4 Markov Chains 103 -- 4.1 Introduction 103 -- 4.2 Chapman-Kolmogorov Equations 105 -- 4.3 Classification of States 106 -- 4.4 Limiting and Stationary Probabilities 115 -- 4.5 Some Applications 121 -- 4.5.1 Models for Algorithmic Efficiency 121 -- 4.5.2 Using a Random Walk to Analyze a Probabilistic Algorithm -- for the Satisfiability Problem 126 -- 4.6 Time-Reversible Markov Chains 131 -- 4.7 Markov Chain Monte Carlo Methods 142 -- Exercises 147 -- 5 The Probabilistic Method 151 -- 5.1 Introduction 151 -- 5.2 Using Probability To Prove Existence 151 -- 5.3 Obtaining Bounds fiom Expectations 153 -- 5.4 The Maximum Weighted Independent -- Set Problem: A Bound and a Random Algorithm 156 -- 5.5 The Set-Covering Problem 161 -- 5.6 Antichains 163 -- 5.7 The Lovasz Local Lemma 164 -- 5.8 A Random Algorithm for Finding the Minimal -- Cut in a Graph 169 -- Exercises 171 -- 6 Martingales 175 -- 6.1 Definitions and Examples 175 -- 6.2 The Martingale Stopping Theorem 177 -- 6.3 The Hoeffding-Azuma Inequality 189 -- 6.4 Submartingales 192 -- Exercises 194 -- 7 Poisson Processes 199 -- 7.1 The Nonstationary Poisson Process 199 -- 7.2 The Stationary Poisson Process 203 -- 7.3 Some Poisson Process Computations 205 -- 7.4 Classifying the Events of a Nonstationary Poisson Process 211 -- 7.5 Conditional Distribution of the Arrival Times 215 -- Exercises 217 -- 8 Queueing Theory 221 -- 8.1 Introduction 221 -- 8.2 Preliminaries 222 -- 8.2.1 Cost Equations 222 -- 8.2.2 Steady-State Probabilities 224 -- 8.3 Exponential Models 226 -- 8.3.1 A Single-Server Exponential Queueing System 226 -- 8.4 Birth-and-Death Exponential Queueing Systems 230 -- 8.5 The Backwards Approach in Exponential Queues 238 -- 8.6 A Closed Queueing Network 239 -- 8.7 An Open Queueing Network 243 -- 8.8 The M/G/I Queue 248 -- 8.8.1 Preliminaries: Work and Another Cost Identity 248 -- 8.8.2 Application of Work to M/G/1 249 -- 8.8.3 Busy and idle Periods 253 -- 8.8.4 Relating the Variances of Waiting -- Times and Number in System 254 -- 8.9 Priority Queues 255 -- Exercises 258 -- 9 Simulation 261 -- 9.1 Monte Carlo Simulation 261 -- 9.2 Generating Discrete Random Variables 263 -- 9.3 Generating Continuous Random Variables: -- The Inverse Transform Approach 266 -- 9.4 The Rejection Method 268 -- 9,5 Variance Reduction 272 -- 9.5.1 Antithetic Variables 272 -- 9.5.2 Importance Sampling 275 -- 9.5.3 Variance Reduction by Conditional Expectation 279 -- Exercises 280 -- References 283 -- Index 285.