1 introduction to probability theory 1
1.1 introduction 1
1.2 sample space and events 1
1.3 probabilities defined on events 4
1.4 conditional probabilities 7
1.5 independent events 10
1.6 bayes’ formula 12
exercise s 15
references 20
2 random variables 21
2.1 random variables 21
2.2 discrete random variables 25
2.2.1 the bernoulli random variable 26
2.2.2 the binomial random variable 27
2.2.3 the geometric random variable 29
2.2.4 the poisson random variable 30
2.3 continuous random variables 31
2.3.1 the uniform random variable 32
2.3.2 exponential random variables 34
2.3.3 gamma random variables 34
.2.3.4 normal random variables 34
2.4 expectation of a random variable 36
2.4.1 the discrete case 36
2.4.2 the continuous case 38
2.4.3 expectation of a function of a random variable 40
2.5 jointly distributed random variables 44
2.5.1 joint distribution functions 44
2.5.2 independent random variables 48
2.5.3 covariance and variance of sums of random variables 50
2.5.4 joint probability distribution of functions of randomvariables 59
2.6 moment generating functions 62
2.6.1 the joint distribution of the sample mean and sample variance from a normal population 71
2.7 the distribution of the number of events that occur 74
2.8 limit theorems 77
2.9 stochastic processes 84
exercises 86
references 95
3 conditional probability and conditional expectation 97
3.1 introduction 97
3.2 the discrete case 97
3.3 the continuous case 102
3.4 computing expectations by conditioning 106
3.4.1 computing variances by conditioning 117
3.5 computing probabilities by conditioning 122
3.6 some applications 140
3.6.1 a list model 140
3.6.2 a random graph 141
3.6.3 uniform priors, polya’s urn model, and bose–einstein statistics 149
3.6.4 mean time for patterns 153
3.6.5 the k-record values of discrete random variables 157
3.6.6 left skip free random walks 160
3.7 an identity for compound random variables 166
3.7.1 poisson compounding distribution 169
3.7.2 binomial compounding distribution 171
3.7.3 a compounding distribution related to the negative binomial 172
exercises 173
4 markov chains 191
4.1 introduction 191
4.2 chapman–kolmogorov equations 195
4.3 classification of states 204
4.4 limiting probabilities 214
4.5 some applications 230
4.5.1 the gambler’s ruin problem 230
4.5.2 a model for algorithmic efficiency 234
4.5.3 using a random walk to analyze a probabilistic algorithm for the satisfiability problem 237
4.6 mean time spent in transient states 243
4.7 branching processes 245
4.8 time reversible markov chains 249
4.9 markov chain monte carlo methods 260
4.10 markov decision processes 265
4.11 hidden markov chains 269
4.11.1 predicting the states 273
exercises 275
references 290
5 the exponential distribution and the poisson process 291
5.1 introduction 291
5.2 the exponential distribution 292
5.2.1 definition 292
5.2.2 properties of the exponential distribution 294
5.2.3 further properties of the exponential distribution 301
5.2.4 convolutions of exponential random variables 308
5.3 the poisson process 312
5.3.1 counting processes 312
5.3.2 definition of the poisson process 313
5.3.3 interarrival and waiting time distributions 316
5.3.4 further properties of poisson processes 319
5.3.5 conditional distribution of the arrival times 325
5.3.6 estimating software reliability 336
5.4 generalizations of the poisson process 339
5.4.1 nonhomogeneous poisson process 339
5.4.2 compound poisson process 346
5.4.3 conditional or mixed poisson processes 351
exercises 354
references 370
6 continuous-time markov chains 371
6.1 introduction 371
6.2 continuous-time markov chains 372
6.3 birth and death processes 374
6.4 the transition probability function pij (t) 381
6.5 limiting probabilities 390
6.6 time reversibility 397
6.7 uniformization 406
6.8 computing the transition probabilities 409
exercises 412
references 419
7 renewal theory and its applications 421
7.1 introduction 421
7.2 distribution of n(t) 423
7.3 limit theorems and their applications 427
7.4 renewal reward processes 439
7.5 regenerative processes 447
7.5.1 alternating renewal processes 450
7.6 semi-markov processes 457
7.7 the inspection paradox 460
7.8 computing the renewal function 463
7.9 applications to patterns 466
7.9.1 patterns of discrete random variables 467
7.9.2 the expected time to a maximal run of distinct values 474
7.9.3 increasing runs of continuous random variables 476
7.10 the insurance ruin problem 478
exercises 484
references 495
8 queueing theory 497
8.1 introduction 497
8.2 preliminaries 498
8.2.1 cost equations 499
8.2.2 steady-state probabilities 500
8.3 exponential models 502
8.3.1 a single-server exponential queueing system 502
8.3.2 a single-server exponential queueing system having finite capacity 511
8.3.3 birth and death queueing models 517
8.3.4 a shoe shine shop 522
8.3.5 a queueing system with bulk service 524
8.4 network of queues 527
8.4.1 open systems 527
8.4.2 closed systems 532
8.5 the system m/g/1 538
8.5.1 preliminaries: work and another cost identity 538
8.5.2 application of work to m/g/1 539
8.5.3 busy periods 540
8.6 variations on the m/g/1 541
8.6.1 the m/g/1 with random-sized batch arrivals 541
8.6.2 priority queues 543
8.6.3 an m/g/1 optimization example 546
8.6.4 the m/g/1 queue with server breakdown 550
8.7 the model g/m/1 553
8.7.1 the g/m/1 busy and idle periods 558
8.8 a finite source model 559
8.9 multiserver queues 562
8.9.1 erlang’s loss system 563
8.9.2 the m/m/k queue 564
8.9.3 the g/m/k queue 565
8.9.4 the m/g/k queue 567
exercises 568
references 578
9 reliability theory 579
9.1 introduction 579
9.2 structure functions 580
9.2.1 minimal path and minimal cut sets 582
9.3 reliability of systems of independent components 586
9.4 bounds on the reliability function 590
9.4.1 method of inclusion and exclusion 591
9.4.2 second method for obtaining bounds on r(p) 600
9.5 system life as a function of component lives 602
9.6 expected system lifetime 610
9.6.1 an upper bound on the expected life of a parallel system 614
9.7 systems with repair 616
9.7.1 a series model with suspended animation 620
exercises 623
references 629
10 brownian motion and stationary processes 631
10.1 brownian motion 631
10.2 hitting times, maximum variable, and the gambler’s ruin problem 635
10.3 variations on brownian motion 636
10.3.1 brownian motion with drift 636
10.3.2 geometric brownian motion 636
10.4 pricing stock options 638
10.4.1 an example in options pricing 638
10.4.2 the arbitrage theorem 640
10.4.3 the black-scholes option pricing formula 644
10.5 white noise 649
10.6 gaussian processes 651
10.7 stationary and weakly stationary processes 654
10.8 harmonic analysis of weakly stationary processes 659
exercises 661
references 665
11 simulation 667
11.1 introduction 667
11.2 general techniques for simulating continuous random variables 672
11.2.1 the inverse transformation method 672
11.2.2 the rejection method 673
11.2.3 the hazard rate method 677
11.3 special techniques for simulating continuous random variables 680
11.3.1 the normal distribution 680
11.3.2 the gamma distribution 684
11.3.3 the chi-squared distribution 684
11.3.4 the beta (n, m) distribution 685
11.3.5 the exponential distribution—the von neumann algorithm 686
11.4 simulating from discrete distributions 688
11.4.1 the alias method 691
11.5 stochastic processes 696
11.5.1 simulating a nonhomogeneous poisson process 697
11.5.2 simulating a two-dimensional poisson process 703
11.6 variance reduction techniques 706
11.6.1 use of antithetic variables 707
11.6.2 variance reduction by conditioning 710
11.6.3 control variates 715
11.6.4 importance sampling 717
11.7 determining the number of runs 722
11.8 generating from the stationary distribution of a markov chain 723
11.8.1 coupling from the past 723
11.8.2 another approach 725
exercises 726
references 734
appendix: solutions to starred exercises 735
index 775
点击看大图
加载中...
