Acknowledgments ................................................ xv
Preface to the Second Edition ................................ xvii
Preface to the First Edition .................................. xix
1 Basic Concepts in Probability .............................. 1
1.1 Introduction ............................................... 1
1.1.1 Conditional Probability ............................. 3
1.1.2 Independence ........................................ 4
1.1.3 Total Probability and the Bayes' Theorem ............ 4
1.2 Random Variables ........................................... 5
1.2.1 Distribution Functions .............................. 5
1.2.2 Discrete Random Variables ........................... 6
1.2.3 Continuous Random Variables ......................... 6
1.2.4 Expectations ........................................ 7
1.2.5 Expectation of Nonnegative Random Variables ......... 7
1.2.6 Moments of Random Variables and the Variance ........ 7
1.3 Transform Methods .......................................... 8
1.3.1 The s-Transform ..................................... 8
1.3.2 The z-Transform ..................................... 9
1.4 Bivariate Random Variables ................................ 11
1.4.1 Discrete Bivariate Random Variables ................ 11
1.4.2 Continuous Bivariate Random Variables .............. 12
1.4.3 Covariance and Correlation Coefficient ............. 12
1.5 Many Random Variables ..................................... 13
1.6 Fubini's Theorem .......................................... 14
1.7 Sums of Independent Random Variables ...................... 15
1.8 Some Probability Distributions ............................ 16
1.8.1 The Bernoulli Distribution ......................... 16
1.8.2 The Binomial Distribution .......................... 17
1.8.3 The Geometric Distribution ......................... 18
1.8.4 The Pascal Distribution ............................ 19
1.8.5 The Poisson Distribution ........................... 19
1.8.6 The Exponential Distribution ....................... 20
1.8.7 The Erlang Distribution ............................ 21
1.8.8 Normal Distribution ................................ 21
1.9 Limit Theorems ............................................ 23
1.9.1 Markov Inequality .................................. 23
1.9.2 Chebyshev Inequality ............................... 23
1.9.3 Laws of Large Numbers .............................. 24
1.9.4 The Central Limit Theorem .......................... 25
1.10 Problems .................................................. 26
2 Basic Concepts in Stochastic Processes .................... 29
2.1 Introduction .............................................. 29
2.2 Classification of Stochastic Processes .................... 29
2.3 Characterizing a Stochastic Process ....................... 30
2.4 Mean and Autocorrelation Function of a Stochastic
Process ................................................... 30
2.5 Stationary Stochastic Processes ........................... 31
2.5.1 Strict-Sense Stationary Processes .................. 31
2.5.2 Wide-Sense Stationary Processes .................... 32
2.6 Ergodic Stochastic Processes .............................. 32
2.7 Some Models of Stochastic Processes ....................... 33
2.7.1 Martingales ........................................ 33
2.7.2 Counting Processes ................................. 36
2.7.3 Independent Increment Processes .................... 36
2.7.4 Stationary Increment Process ....................... 37
2.7.5 Poisson Processes .................................. 37
2.8 Problems .................................................. 46
3 Introduction to Markov Processes .......................... 49
3.1 Introduction .............................................. 49
3.2 Structure of Markov Processes ............................. 50
3.3 Strong Markov Property .................................... 52
3.4 Applications of Discrete-Time Markov Processes ............ 53
3.4.1 Branching Processes ................................ 53
3.4.2 Social Mobility .................................... 54
3.4.3 Markov Decision Processes .......................... 54
3.5 Applications of Continuous-Time Markov Processes .......... 54
3.5.1 Queueing Systems ................................... 54
3.5.2 Continuous-Time Markov Decision Processes .......... 55
3.5.3 Stochastic Storage Systems ......................... 55
3.6 Applications of Continuous-State Markov Processes ......... 55
3.6.1 Application of Diffusion Processes to Financial
Options ............................................ 56
3.6.2 Applications of Brownian Motion .................... 56
3.7 Summary ................................................... 57
4 Discrete-Time Markov Chains ............................... 59
4.1 Introduction .............................................. 59
4.2 State-Transition Probability Matrix ....................... 60
4.2.1 The л-Step State-Transition Probability ............ 60
4.1 State-Transition Diagrams ................................. 61
4.4 Classification of States .................................. 62
4.5 Limiting-State Probabilities .............................. 66
4.5.1 Doubly Stochastic Matrix ........................... 69
4.6 Sojourn Time .............................................. 70
4.7 Transient Analysis of Discrete-Time Markov Chains ......... 71
4.8 First Passage and Recurrence Times ........................ 73
4.9 Occupancy Times ........................................... 76
4.10 Absorbing Markov Chains and the Fundamental Matrix ........ 77
4.10.1 Time to Absorption ................................. 78
4.10.2 Absorption Probabilities ........................... 80
4.11 Reversible Markov Chains .................................. 81
4.12 Problems .................................................. 82
5 Continuous-Time Markov Chains ............................. 85
5.1 Introduction .............................................. 85
5.2 Transient Analysis ........................................ 87
5.2.1 The s-Transform Method ............................. 90
5.3 Birth and Death Processes ................................. 91
5.3.1 Local Balance Equations ............................ 94
5.3.2 Transient Analysis of Birth and Death Processes .... 96
5.4 First Passage Time ........................................ 96
5.5 The Uniformization Method ................................. 98
5.6 Reversible CTMCs .......................................... 99
5.7 Problems .................................................. 99
6 Markov Renewal Processes ................................. 103
6.1 Introduction ............................................. 103
6.2 Renewal Processes ........................................ 103
6.2.1 The Renewal Equation .............................. 105
6.2.2 Alternative Approach .............................. 107
6.2.3 The Elementary Renewal Theorem .................... 110
6.2.4 Random Incidence and Residual Time ................ 110
6.2.5 Delayed Renewal Process ........................... 113
6.3 Renewal-Reward Process ................................... 114
6.3.1 The Reward-Renewal Theorem ........................ 115
6.4 Regenerative Processes ................................... 115
6.4.1 Inheritance of Regeneration ....................... 116
6.4.2 Delayed Regenerative Process ...................... 116
6.4.3 Regenerative Simulation ........................... 117
6.5 Markov Renewal Process ................................... 120
6.5.1 The Markov Renewal Function ....................... 121
6.6 Semi-Markov Processes .................................... 123
6.6.1 Discrete-Time SMPs ................................ 124
6.6.2 Continuous-Time SMPs .............................. 128
6.7 Markov Regenerative Process .............................. 133
6.8 Markov Jump Processes .................................... 135
6.8.1 The Homogeneous Markov Jump Process ............... 137
6.9 Problems ................................................. 141
7 Markovian Queueing Systems ............................... 145
7.1 Introduction ............................................. 145
7.2 Description of a Queueing System ......................... 145
7.3 The Kendall Notation ..................................... 147
7.4 The Little's Formula ..................................... 148
7.5 The PASTA Property ....................................... 149
7.6 The M/M/1 Queueing System ................................ 149
7.6.1 Stochastic Balance ................................ 152
7.6.2 Total Time and Waiting Time Distributions of
the M/M/l Queueing System ......................... 153
7.7 Examples of Other M/M Queueing Systems ................... 155
7.7.1 The M/M/c Queue: The c-Server System .............. 156
7.7.2 The M/M/1/K Queue: The Single-Server Finite-
Capacity System ................................... 160
7.7.3 The M/M/c/c Queue: The c-Server Loss System ....... 165
7.7.4 The M/M/1//K Queue: The Single-Server Finite
Customer Population System ........................ 167
7.8 M/G/l Queue .............................................. 169
7.8.1 Waiting Time Distribution of the M/G/1 Queue ...... 171
7.8.2 The M/Ek/1 Queue .................................. 174
7.8.3 The M/D/1 Queue ................................... 175
7.8.4 The M/M/1 Queue Revisited ......................... 176
7.8.5 The M/Hk/1 Queue .................................. 176
7.9 G/M/l Queue .............................................. 178
7.9.1 The Ek/M/1 Queue .................................. 182
7.9.2 The D/M/1 Queue ................................... 183
7.10 M/G/l Queues with Priority ............................... 184
7.10.1 Nonpreemptive Priority ............................ 185
7.10.2 Preemptive Resume Priority ........................ 186
7.10.3 Preemptive Repeat Priority ........................ 187
7.11 Markovian Networks of Queues ............................. 189
7.11.1 Burke's Output Theorem and Tandem Queues .......... 191
7.11.2 Jackson or Open Queueing Networks ................. 193
7.11.3 Closed Queueing Networks .......................... 195
7.12 Applications of Markovian Queues ......................... 197
7.13 Problems ................................................. 198
8 Random Walk .............................................. 205
8.1 Introduction ............................................. 205
8.2 Occupancy Probability .................................... 207
8.3 Random Walk as a Markov Chain ............................ 210
8.4 Symmetric Random Walk as a Martingale .................... 210
8.5 Random Walk with Barriers ................................ 211
8.6 Gambler's Ruin ........................................... 211
8.6.1 Ruin Probability .................................. 212
8.6.2 Alternative Derivation of Ruin Probability ........ 214
8.6.3 Duration of a Game ................................ 215
8.7 Random Walk with Stay .................................... 216
8.8 First Return to the Origin ............................... 217
8.9 First Passage Times for Symmetric Random Walk ............ 220
8.9.1 First Passage Time via the Generating Function .... 220
8.9.2 First Passage Time via the Reflection Principle ... 221
8.9.3 Hitting Time and the Reflection Principle ......... 225
8.10 The Ballot Problem and the Reflection Principle .......... 225
8.10.1 The Conditional Probability Method ................ 226
8.11 Returns to the Origin and the Arc-Sine Law ............... 227
8.12 Maximum of a Random Walk ................................. 231
8.13 Random Walk on a Graph ................................... 233
8.13.1 Random Walk on a Weighted Graph ................... 239
8.14 Correlated Random Walk ................................... 240
8.15 Continuous-Time Random Walk .............................. 244
8.15.1 The Master Equation ............................... 247
8.16 Self-Avoiding Random Walk ................................ 249
8.17 Nonreversing Random Walk ................................. 253
8.18 Applications of Random Walk .............................. 255
8.18.1 Web Search ........................................ 255
8.18.2 Insurance Risk .................................... 256
8.18.3 Content of a Dam .................................. 257
8.18.4 Cash Management ................................... 257
8.18.5 Mobility Models in Mobile Networks ................ 258
8.19 Summary .................................................. 259
8.20 Problems ................................................. 259
9 Brownian Motion .......................................... 263
9.1 Introduction ............................................. 263
9.2 Mathematical Description ................................. 263
9.3 Brownian Motion with Drift ............................... 265
9.4 Brownian Motion as a Markov Process ...................... 266
9.5 Brownian Motion as a Martingale .......................... 267
9.6 First Passage Time of a Brownian Motion .................. 267
9.7 Maximum of a Brownian Motion ............................. 268
9.8 First Passage Time in an Interval ........................ 269
9.9 The Brownian Bridge ...................................... 270
9.10 Geometric Brownian Motion ................................ 271
9.11 Introduction to Stochastic Calculus ...................... 271
9.11.1 Stochastic Differential Equation and the Ito
Process ........................................... 272
9.11.2 The Ito Integral .................................. 274
9.11.3 The Ito's Formula ................................. 276
9.12 Solution of Stochastic Differential Equations ............ 277
9.13 Solution of the Geometric Brownian Motion ................ 277
9.14 The Ornstein-Uhlenbeck Process ........................... 280
9.14.1 Solution of the OUSDE ............................. 281
9.14.2 First Alternative Solution Method ................. 283
9.14.3 Second Alternative Solution Method ................ 283
9.15 Mean-Reverting OU Process ................................ 284
9.16 Fractional Brownian Motion ............................... 286
9.16.1 Self-Similar Processes ............................ 286
9.16.2 Long-Range Dependence ............................. 287
9.16.3 Self-Similarity and Long-Range Dependence ......... 288
9.16.4 FBM Revisited ..................................... 288
9.17 Fractional Gaussian Noise ................................ 290
9.18 Multifractional Brownian Motion .......................... 291
9.19 Problems ................................................. 292
10 Diffusion Processes ...................................... 295
10.1 Introduction ............................................. 295
10.2 Mathematical Preliminaries ............................... 296
10.3 Models of Diffusion ...................................... 297
10.3.1 Diffusion as a Limit of Random Walk: The Fokker-
Planck Equation ................................... 297
10.3.2 The Langevin Equation ............................. 299
10.3.3 The Fick's Equations .............................. 301
10.4 Examples of Diffusion Processes .......................... 302
10.4.1 Brownian Motion ................................... 302
10.4.2 Brownian Motion with Drift ........................ 304
10.5 Correlated Random Walk and the Telegraph Equation ........ 305
10.6 Introduction to Fractional Calculus ...................... 308
10.6.1 Gamma Function .................................... 309
10.6.2 Mittag-Leffler Functions .......................... 310
10.6.3 Laplace Transform ................................. 311
10.6.4 Fractional Derivatives ............................ 313
10.6.5 Fractional Integrals .............................. 314
10.6.6 Definitions of Fractional Integro-Differentials ... 315
10.6.7 Riemann—Liouville Fractional Derivative ........... 315
10.6.8 Caputo Fractional Derivative ...................... 316
10.6.9 Fractional Differential Equations ................. 317
10.6.10 Relaxation Differential Equation of Integer
Order ............................................ 319
10.6.11 Oscillation Differential Equation of Inter
Order ............................................ 319
10.6.12 Relaxation and Oscillation FDEs .................. 319
10.7 Anomalous (or Fractional) Diffusion ...................... 320
10.7.1 Fractional Diffusion and Continuous-Time Random
Walk .............................................. 322
10.7.2 Solution of the Fractional Diffusion Equation ..... 324
10.8 Problems ................................................. 326
11 Levy Processes ........................................... 329
11.1 Introduction ............................................. 329
11.2 Generalized Central Limit Theorem ........................ 329
11.3 Stable Distribution ...................................... 331
11.4 Levy Distribution ........................................ 335
11.5 Levy Processes ........................................... 336
11.6 Infinite Divisibility .................................... 336
11.6.1 Infinite Divisibility of the Poisson Process ...... 337
11.6.2 Infinite Divisibility of the Compound Poisson
Process ........................................... 338
11.6.3 Infinite Divisibility of the Brownian Motion
with Drift ........................................ 338
11.7 Jump-Diffusion Processes ................................. 338
11.7.1 Models of Jump-Diffusion Process .................. 339
11.7.2 Normal Jump-Diffusion Model ....................... 341
11.7.3 Bernoulli Jump Process ............................ 344
11.7.4 Double Exponential Jump-Diffusion Model ........... 345
11.7.5 Jump Diffusions and Levy Processes ................ 345
12 Markovian Arrival Processes .............................. 349
12.1 Introduction ............................................. 349
12.2 Overview of Matrix-Analytic Methods ...................... 350
12.3 Markovian Arrival Process ................................ 355
12.3.1 Properties of MAP ................................ 357
12.4 Batch Markovian Arrival Process .......................... 359
12.4.1 Properties of BMAP ................................ 362
12.5 Markov-Modulated Poisson Process ......................... 363
12.5.1 The Interrupted Poisson Process ................... 364
12.5.2 The Switched Poisson Process ...................... 366
12.5.3 Properties of MMPP ................................ 366
12.5.4 The MMPP(2)/M/1 Queue ............................. 367
12.6 Markov-Modulated Bernoulli Process ....................... 371
12.6.1 The MMBP(2) ....................................... 372
12.7 Sample Applications of MAP and Its Derivatives ........... 374
12.8 Problems ................................................. 375
13 Controlled Markov Processes .............................. 377
13.1 Introduction ............................................. 377
13.2 Markov Decision Processes ................................ 377
13.2.1 Overview of DP .................................... 378
13.2.2 Example of DP Problem ............................. 379
13.2.3 Markov Reward Processes ........................... 381
13.2.4 MDP Basics ........................................ 383
13.2.5 MDPs with Discounting ............................. 385
13.2.6 Solution Methods .................................. 385
13.3 Semi-MDPs ................................................ 395
13.3.1 Semi-Markov Reward Model .......................... 396
13.3.2 Discounted Reward ................................. 398
13.3.3 Analysis of the Continuous-Decision-Interval
SMDPs ............................................. 399
13.3.4 Solution by Policy Iteration ...................... 400
13.3.5 SMDP with Discounting ............................. 403
13.3.6 Solution by Policy Iteration When Discounting Is
Used .............................................. 404
13.3.7 Analysis of the Discrete-Decision-Interval SMDPs
with Discounting .................................. 405
13.3.8 Continuous-Time Markov Decision Processes ......... 406
13.3.9 Applications of SMDPs ............................. 406
13.4 Partially Observable MDPs ................................ 407
13.4.1 Partially Observable Markov Processes ............. 408
13.4.2 POMDP Basics ...................................... 410
13.4.3 Solving POMDPs .................................... 413
13.4.4 Computing the Optimal Policy ...................... 414
13.4.5 Approximate Solutions of POMDP .................... 415
13.5 Problems ................................................. 415
14 Hidden Markov Models ..................................... 417
14.1 Introduction ............................................. 417
14.2 HMM Basics ............................................... 419
14.3 HMM Assumptions .......................................... 421
14.4 Three Fundamental Problems ............................... 422
14.5 Solution Methods ......................................... 422
14.5.1 The Evaluation Problem ............................ 422
14.5.2 The Decoding Problem and the Viterbi Algorithm .... 430
14.5.3 The Learning Problem and the Baum - Welch
Algorithm ......................................... 436
14.6 Types of HMMs ............................................ 438
14.7 HMMs with Silent States .................................. 439
14.8 Extensions of HMMs ....................................... 439
14.8.1 Hierarchical Hidden Markov Model .................. 440
14.8.2 Factorial Hidden Markov Model ..................... 441
14.8.3 Coupled Hidden Markov Model ....................... 442
14.8.4 Hidden Semi-Markov Models ......................... 443
14.8.5 PHMMs for Biological Sequence Analysis ............ 444
14.9 Other Extensions of HMM .................................. 448
14.10 Problems ................................................ 448
15 Markov Point Processes ................................... 453
15.1 Introduction ............................................. 453
15.2 Temporal Point Processes ................................. 454
15.3 Specific Temporal Point Processes ........................ 455
15.3.1 Poisson Point Processes ........................... 456
15.3.2 Сох Point Processes ............................... 456
15.4 Spatial Point Processes .................................. 456
15.5 Specific Spatial Point Processes ......................... 458
15.5.1 Spatial Poisson Point Processes ................... 458
15.5.2 Spatial Cox Point Processes ....................... 460
15.5.3 Spatial Gibbs Processes ........................... 461
15.6 Spatial - Temporal Point Processes ....................... 462
15.7 Operations on Point Processes ............................ 464
15.7.1 Thinning .......................................... 464
15.7.2 Superposition ..................................... 465
15.7.3 Clustering ........................................ 465
15.8 Marked Point Processes ................................... 466
15.9 Introduction to Markov Random Fields ..................... 467
15.9.1 MRF Basics ........................................ 468
15.9.2 Graphical Representation .......................... 471
15.9.3 Gibbs Random Fields and the Hammersley -
Clifford Theorem .................................. 473
15.10 Markov Point Processes .................................. 476
15.11 Markov Marked Point Processes ........................... 478
15.12 Applications of Markov Point Processes .................. 479
15.13 Problems ................................................ 479
References .................................................... 481
| 
