Index

A

Absorbing states, 185–186
Algorithmic efficiency, model for, 223
Aloha protocol, instability of, 201–202
Alternating renewal process, 439
Aperiodic chain, 219–220
Arbitrage, 615
Arbitrage theorem, 616
Arbitrary queueing system, 520
Arrival theorem, 516–517
Autoregressive process, 635

B

Backward approach, 257–258
Balance equations, 375, 487–488
Bayes’ formula, 11
Bernoulli probability mass function, 691
Bernoulli random variables, 26, 50–51, 63–64, 281–282, 323, 365–366, 453–454, 595–596, 665, 691, 693
expectation of, 35
independent, 118
Best prize problem, 118–119
Beta density with parameters, 56–57
Beta distribution, 661
Binomial compounding distribution, 161
Binomial distribution with parameters, 59
Binomial probabilities, 199, 240
Binomial random variables, 26, 95, 665
expectation of, 35–36
variance of, 50–51
Birth and death model, 357
Birth and death processes, 359–360, 364–365
forward equations for, 373
limiting probabilities for, 375
Birth and death queueing models, 499
Black-Scholes option pricing formula, 619
Bonus Malus automobile insurance system, 186, 218–219
Boolean formula, 230
Boolean variables, 230
Bose–Einstein statistics, 141
Box–Muller approach, 658–659
Bridge system, 564
Brownian bridge, 630–631
Brownian motion, 607, 752
Gaussian processes, 630
independent increment assumption, 609–610
integrated, 631–632
interpretation of, 609
maximum variable and gambler’s ruin problem, 611
pricing stock options
arbitrage theorem, 616
Black-Scholes option pricing formula, 619
Brownian motion with drift, 624
example in options pricing, 614
process, 620
with variance parameter, 622
stationary processes, 633
stochastic process, 608
variations on
with drift, 612
geometric, 612
weakly stationary processes, 637
white noise, 628

C

Car buying model, 428
Central limit theorem, 73–74, 225
heuristic proof of, 76–77
for renewal processes, 426
Chapman–Kolmogorov equations, 187, 195, 370, 372–373
Chebyshev’s inequality, 72
Chi-squared density, 98–99
Chi-square distribution, 660
definition of, 658
Chi-squared random variable, 66–68
Class mobility model, 207
Closed systems, network of queues, 514
Common distribution function, 125–126
Communication systems, 184
Compounding distribution, 157–158
Compound Poisson process, 327, 330–332
examples of, 327
Compound Poisson random variable, 113
Compound random variables, 102
identity for, 157
variance of, 113
Computer software package, 320
Conditional density function, 333–334
Conditional distribution
of arrival times, 675
function, 333–334
Conditional expectation, 97
probability and. See Conditional
probability and expectation
Conditional/mixed Poisson processes, 332
Conditional Poisson process, 332–333
Conditional probability, 6, 11
density function, 97
mass function, 93–95
Conditional probability and expectation
applications
Bose–Einstein statistics, 141
k -record values of discrete random variables, 149
left skip free random walks, 152
list model, 133
mean time for patterns, 146
Polya’s Urn model, 141
random graph, 135
computing expectations by conditioning, 100
variances, 111
computing probabilities by conditioning, 115
continuous case, 97
discrete case, 93
identity for compound random variables, 157
binomial compounding distribution, 161
compounding distribution related to negative binomial, 162
Poisson compounding distribution, 160
introduction, 93
Conditional variance
defined, 112
formula, 111–112, 234–235, 281–282, 329–330, 333, 365–366, 498–499, 531–532, 731, 748–749
Continuous case, 97
random variables, 37
Continuous-Markov chain, 732
Continuous random variables, 24, 30, 32–33
exponential random variables, 32
gamma random variables, 33
general techniques for
hazard rate method, 654
inverse transformation method, 649
rejection method, 650
increasing runs of, 461
normal random variables, 33
with probability density function, 39
special techniques for
beta distribution, 661
chi-squared distribution, 660
exponential distribution, 662
gamma distribution, 660
normal distribution, 657
Von Neumann algorithm, 662
uniform random variable, 31
Continuous-time Markov chain, 357–358, 371, 374, 380–381, 384–385, 387–388, 393, 481, 688–689
birth and death processes, 359
limiting probabilities, 374
reversed chain, 387
time reversibility, 380
transition probabilities of, 366, 396
transition probability function, 366
uniformization, 393
Continuous-time process, 78
Continuous-time stochastic process, 358
Convolution of distributions, 52
Cost equations, 482
Coupon collecting problem, 306–307
Covariance, properties of, 48
Coxian random variable, 296–297
Cumulative distribution function, 24–25, 32, 42, 52
of random variable, 32
and probability density, relationship between, 31
Cut vector, 564

D

Data sequence, defined, 149–150
Decreasing failure rate (DFR), 581
Delayed renewal processes, 452–453, 470
Density function, 691
of gamma random variable, 115–116
Desired probability, 222
Dirichlet distribution, 143–144
Disconnected graph, 135
Discrete case, 93
random variables, 34
Discrete random variables, 24–25
Bernoulli random variable, 26
binomial random variable, 26
distributed, 146
geometric random variable, 28
k -record values of, 149
patterns of, 453
Poisson random variable, 29
with probability mass function, 39
Discrete-time Markov chains, 380–383, 393
Discrete-time process, 78
Distributed discrete random variables, 146
Distributed random variables, independent and identically, 424–425, 459
Drift, Brownian motion with, 612

E

Elementary renewal theorem, 419, 424–425, 462
proof of, 422–423
Embedded chain, 380
Equilibrium distribution, 442
Ergodic continuous-time Markov chain, 387–388
Ergodic Markov chain, 220, 242
Erlang’s loss formula, 482
Erlang’s loss system, 542
Event times, simulating, 676
Exponential distribution, 662
definition, 278
exponential random variables, convolutions of, 293
with parameter λ, 60
properties of, 277, 280, 287
Exponential interarrival random variables, 493–494
Exponential models
birth and death queueing models, 499
queueing system with bulk service, 507
shoe shine shop, 505
single-server exponential queueing system, 486
with finite capacity, 495
Exponential random variables, 32, 285–286, 450, 492, 650
convolutions of, 293
expectation of, 37
and expected discounted returns, 279

F

Failure rate function, 284–285, 293, 296, 581
of distribution, 585
of hyperexponential random variable, 285–286
Feedback arrival, 513–514
FIFO, 525
Finite source model, 538
Finite-state Markov chain, 197
First-order autoregressive process, 635
Five-component system, 562–563, 567
Forward approach, 257–258
Four-component structure, 561–562
Fourier transforms, 638–639
Front-of-the-line rule, 134, 244
Fundamental queueing identity, 503–504

G

Gambler’s fortune, 156–157
Gambler’s ruin problem, 220, 232, 611
Gambling model, 185–186
Gamma distribution, 115–116, 582, 660
Gamma random variables, 33
density function of, 115–116
Gaussian processes, 630
finite dimensional distributions of, 634
Genetics, Markov chain in, 208
Geometric Brownian motion, 612
Geometric distribution, 665
Geometric random variable, 28, 103, 105–107, 151
expectation of, 36
variance of, 111–112
Gibbs sampler, 249–250
simulation, 519
G / M / k queue, 544
G / M /1 model, 534
busy and idle periods, 538
Graph
connected, 241
components, 139–140
disconnected, 135
random, 135
Greedy algorithms, 288

H

Hardy–Weinberg law, 208
Hastings–Metropolis algorithm, 247–250
Hawkes processes, random intensity functions and, 334
Hazard function, 585
Hazard rate function. See Failure rate function
Hazard rate method, 654
Heuristic proof of equation, 483
Hidden Markov chains, 254
predicting states, 259
Hitting time theorem, 154
Hyperexponential random variable, 285–286
Hypergeometric distribution, 51, 95
Hypoexponential random variable, 293–296

I

Ignatov’s theorem, 125–126
Impulse response function, 637
Inclusion–exclusion bounds, 573
Inclusion–exclusion identity, 6, 69–71
Inclusion–exclusion theorem, 128
Increasing failure rate (IFR) distribution, 581, 586
Increasing failure rate on the average (IFRA) distribution, 559
Independent Bernoulli random variables, 74
distribution of, 118
Independent Bernoulli trials, 148
Independent components, reliability systems of, 565
Independent events, 9
Independent geometrics, 733
Independent increments, 297, 752
assumption, 297–298, 302, 609–610
Independent random variables, 45, 306–307, 653
binomial, 62
distributed, 424–425
exponential, 99–100, 289–290, 306–307, 539–540
finite-valued, 150
normal, 63, 67, 713
Poisson, 53–54, 63, 306
sequence of, 329–330
standard normal, 67
Independent time reversible continuous-time Markov chains, 386
Independent with distribution function, 313
Indicator random variable, 23
Induction hypothesis, 137, 154–156
Infinite server Poisson queue, output process of, 326
Infinite server queue, 311, 441–442
Instantaneous transition rates, 368, 384
Insurance ruin problem, 462
Integrated Brownian motion, 631–632
Intensity function, nonhomogeneous Poisson process with, 322
Interarrival density, 469
Inverse transformation method, 649
Irreducible Markov chain, 245

J

Joint cumulative probability distribution function, 42
Joint density function of n random variables, 57
Joint distribution functions, 42
Jointly distributed random variables
covariance and variance of, 46
independent random variables, 45
joint distribution functions, 42
joint probability distribution of functions, 55
Joint probability distributions, 43
Joint probability mass function, 42

K

“Key renewal theorem,” 436
Kolmogorov backward equations, 370, 396–397
Kolmogorov forward equations, 372–373
k -out-of- n system, 560–561, 563
with equal probabilities, 567
with identical components, 583–584

L

Laplace transform, 64, 299, 322
Limiting probabilities for Markov chain, 209
Limit theorems, 71
Linear birth rate, birth process with, 360
Linear growth model with immigration, 361, 376–377
Linear program, 253–254
Little’s formula, 483
Long-run proportions, Markov chain, 204

M

Machine repair model, 377–378
Markov chain, 183–184, 534, 537
applications
algorithmic efficiency, model for, 223
gambler’s ruin problem, 220
probabilistic algorithm for satisfiability problem, 226
branching processes, 234
Chapman–Kolmogorov equations, 187
classification of states, 194
defined, 191
ergodic, 242
finite-state, 197
in genetics, 208
hidden, 254
predicting the states, 259
irreducible, 245
limiting probabilities for, 204, 209, 219
long-run proportions and, 204
Markov decision processes, 251
mean pattern times in, 215
mean time spent in transient states, 231
Monte Carlo methods, 247
stationary distribution of, 695
stationary probabilities, 217, 539–540
of successive states, 218–219
time reversible, 237
transforming process into, 185
transition probabilities, 186, 212, 238, 544
transition probability matrix, 189–190, 195–196, 198, 206–207
two-dimensional, 252–253
two-state, 219–220
Markov decision processes, 251
Markovian property, 437
Markov’s inequality, 72, 711
Markov transition probability matrix, 247–248, 515
Martingale process, 623
Martingale stopping theorem, 753
Matching rounds problem, variance in, 113–114
Mean value
analysis, 517
function, 322
M / G / k queue, 546
M / G /1 system
application of, 520
busy periods, 522
optimization example, 527
preliminaries, 520
queue with server breakdown, 531
variations on, 523
Minimal cut set, 564
Minimal cut vector, 564
Minimal path set, 562
Minimal path vector, 562
M / M /1
queue, 363, 378, 487, 500
with balking, 500
with impatient customers, 502–503
steady-state customer, 492
M / M / k queue, 544
Moment generating functions, 58, 713, 747
formula for, 753
joint distribution of mean and variance, 66
number of events, distribution of, 69
Monotone, 562
system of independent components, 587
Monte Carlo methods, 247
Monte Carlo simulation, 247
approach, 645–646
Moving average process, 636
m -step transition probability, 191
Multinomial distribution, 104–105, 143–144
Multinomial probability, 199–200
Multiserver exponential queueing system, 363, 376
Multiserver queues, 542
Multiserver systems, 482
Multivariate normal distribution, 65, 67

N

NBU. See New better than used
Negative binomial distribution, 129–130, 411, 715
of noncentral chisquared random variable, 718
Network of queues
closed systems, 514
open systems, 510
New better than used (NBU), 457
Nodes, 135
Nonhomogeneous Poisson process, 322, 334–335, 672, 685
with intensity function, 731
Nonnegative random variable, 591–592, 712
Nonoverlapping patterns, 147–148
Nonstationary Poisson process. See Nonhomogeneous Poisson process
Normal distribution, 657
with parameter μ, 60–61
Normal random variables, 33, 652–653
expectation of, 38
variance of, 41
n -step transition probabilities, 187–188

O

One-closer rule, 134, 243
One-step transition probabilities, 187–188
Open systems, network of queues, 510
Order statistics, 54–55
Ornstein–Uhlenbeck process, 635

P

Pairwise independent events, 10
Parallel structure, 560
Parallel system, 559, 566
PASTA principle, 434, 486
Path vector, 562
Periodic chain, 219–220
Poisson compounding distribution, 160
Poisson distribution, 64, 212–215, 492
with mean λ, 59–60
Poisson mean, 115–116
Poisson paradigm, 63–64
Poisson process, 277, 299–300, 308–309, 320, 360, 409, 448–449, 462–463, 470, 481, 486, 522, 527, 623, 633, 646, 654–655, 661–662, 666–667, 742
assumption, 671–672
conditional distribution of arrival times, 309
counting processes, 297
definition of, 298
generalizations of, 322
interarrival and waiting time distributions, 301
nonhomogeneous, 672
properties of, 303
sampling, 311, 672
software reliability, estimating, 320
two-dimensional, 677
Poisson random variables, 29, 95–96, 117, 132, 139, 186–187, 212–213, 218–219, 323, 329, 331, 531, 533, 666, 730, 737
expectation of, 36–37
variance of, 312–315
Polar method, 660
Pollaczek–Khintchine formula, 521
Polya’s Urn model, 141
Power spectral density, 638–639
Preceding method, 149
Present value, 614
Pricing stock options
arbitrage theorem, 616
Black-Scholes option pricing formula, 619
example in options pricing, 614
Priority queueing systems, 524–525
Priority queues, 524
Probabilistic algorithm, 230
Probability density
function, 30–32, 125–126, 712
relationship between cumulative distribution and, 31
Probability mass function, 25, 29, 42–43, 69–70, 125–126
Probability theory, 1
Bayes’ formula, 11
conditional probabilities, 6
independent events, 9
probabilities defined on events, 4
sample space and events, 1
Production process, 439
Pure birth process, 357

Q

Queueing cost identity, 489–490
Queueing models, fundamental quantities for, 482
Queueing system, 684, 689
with bulk service, 507
Queueing theory
exponential models
birth and death queueing models, 499
queueing system with bulk service, 507
shoe shine shop, 505
single-server exponential queueing system, 486, 495
finite source model, 538
G / M /1 model, 534
M / G /1 system
application of, 520
busy periods, 522
optimization example, 527
preliminaries, 520
queue with server breakdown, 531
variations on, 523
multiserver queues, 542
network of queues
closed systems, 514
open systems, 510
preliminaries
cost equations, 482
steady-state probabilities, 484
Quick-sort algorithm, 108–110

R

Random graph, 135, 141, 575
Random intensity functions, 334–335
and Hawkes processes, 334
Random numbers, 646
Random permutation, generating, 646–648
Random-sized batch arrivals, M / G /1 with, 523
Random telegraph signal process, 633–634, 636
Random variables, 21, 652–653, 675
covariance and variance of sums of, 46
density function, 652
expectation of
continuous case, 37
discrete case, 34
function of, 38
expected value of, 40
joint probability distribution of functions, 55
Random walk model, 185, 198
Random walk process, 424–425
Rate-equality principle, 487–488, 495
Rate of the distribution, 285
Recursive equation, 121–122
Rejection method, 650
Reliability function, 565–567, 683
bounds on, 570
inclusion and exclusion, method of, 570
obtaining bounds on r (p), method for, 578
Reliability theory, 559
independent components, reliability systems of, 565
reliability function, bounds on, 570
inclusion and exclusion method, 570
obtaining bounds on r (p), 578
structure functions, 560
minimal path and minimal cut sets, 562
system lifetime, expected, 587
parallel system, upper bound on, 591
systems with repair, 593
suspended animation, series model with, 597
Renewal arrivals, queueing system with, 437
Renewal equation, 413–414
Renewal function, 412–413
computing, 449
Renewal interarrival distribution, 450
Renewal process, 409–410
age of, 440
average, 432–433
average excess of, 433–434
excess of, 441
reward processes, 427, 430–431, 686
Renewal reward theory, 432–434, 476
Renewal theory and applications
distribution of N (t), 411
inspection paradox, 447
introduction, 409
limit theorems and applications, 415
patterns, applications to
continuous random variables, 461
discrete random variables, 453
distinct values, expected time to maximal run of, 459
insurance ruin problem, 462
regenerative processes, 436
alternating, 439
renewal function, computing, 449
renewal reward processes, 427
semi-Markov processes, 444
Reverse chain equations, 387, 389
Reversed process, 382–383
Reverse time equations, 390–392

S

Sample mean, 49, 625
Sample variance, 66
Satisfiability problem, 230
probabilistic algorithm for, 226
Second-order stationary process, 634, 636
Self-exciting process, 335
Semi-Markov processes, 444–445, 477, 742
Sequence of interarrival times, 301–303
Sequential queueing system, 391
Series system, 559
Simplex algorithm, 253–254
Simulation, 645
continuous random variables. See Continuous random variables
determining number of runs, 694
from discrete distributions, 664
alias method, 667
renewal function by, 686
stationary distribution of Markov chain, coupling from past, 695, 697
stochastic processes, 671
nonhomogeneous Poisson process, 672
two-dimensional Poisson process, 677
of two-dimensional Poisson processes, 646
variance reduction techniques, 680
by conditioning, 684
control variates, 688
importance sampling, 690
use of antithetic variables, 681
Single-server exponential queueing system, 486, 507–508
finite capacity, 495
Single-server Poisson arrival queues, 328
Single-server queue, 694
Single-server system, 482
Sorting algorithm, 671
Standard Brownian motion, 608, 632
Standard normal distribution function, 426
Standard normal random variables, 68, 654
Standard/unit normal distribution, 34
State space of stochastic process, 78
State vector, 560
Stationary distribution of Markov chain, 695
Stationary ergodic Markov chain, 237
Stationary increments, 298, 302, 752
Stationary probabilities, 211–215, 375
Stationary processes, 633
weakly, 634
Steady-state distribution, 544
Steady-state probability, 253–254, 484, 514
Stirling’s approximation, 199–200, 203, 225–226
Stochastic processes, 77, 144–145, 183, 436, 608
Strong law of large numbers, 73
Structure function, 560
Symmetric random walk, 199

T

Tail distribution function, 293–296
Tandem queue, 512
Tandem/sequential system, 510
Taylor series expansion, 76–77
Time inventory, long-run proportion of, 443–444
Time reversibility, 380
equations, 241–242, 736
Time reversible chain, 385
Time reversible equations, 384–385
Time reversible Markov chain, 237
T -random variable, 98–99
Transition probabilities
computing, 396
of continuous-time Markov chain, 366
defined, 237
function, 366
matrix, 724
Two-dimensional Poisson process, 677
Two independent uniform random variables, sum of, 53
Two-state continuous-time Markov chain, 394, 422, 424, 593
Two-state Markov chain, 219–220
Two-step transition matrix, 188–189

U

Unconditional probabilities, 194
Uniform distribution, 143–144
Uniformization, 393
Uniformly distributed components, series system of, 588
Uniform priors, 141
Uniform random variable, 31, 712
expectation of, 37

V

Variance parameter, process with, 622
Viterbi algorithm, 259
Von Neumann algorithm, 662

W

Wald’s equation, 419–420, 656, 663–664, 739
Weakly stationary processes, 634
harmonic analysis of, 637
Weibull distribution, 582
White noise transformation, 628
Wiener process, 608

Y

Yule process, 360, 367–368