Markov Processes for Stochastic Modeling

Markov Processes for Stochastic Modeling......Page 4
Copyright Page......Page 5
Contents......Page 6
Preface......Page 14
1.1 Review of Probability......Page 16
1.1.2 Independence......Page 19
1.1.3 Total Probability and the Bayes’ Theorem......Page 20
1.2.2 Discrete Random Variables......Page 21
1.2.3 Continuous Random Variables......Page 22
1.2.6 Moments of Random Variables and the Variance......Page 23
1.3.1 The s-Transform......Page 24
1.3.2 The z-Transform......Page 25
1.4 Bivariate Random Variables......Page 27
1.4.2 Continuous Bivariate Random Variables......Page 28
1.5 Many Random Variables......Page 29
1.6 Fubini’s Theorem......Page 30
1.7 Sums of Independent Random Variables......Page 31
1.8.1 The Bernoulli Distribution......Page 33
1.8.2 The Binomial Distribution......Page 34
1.8.4 The Pascal Distribution......Page 35
1.8.6 The Exponential Distribution......Page 36
1.8.7 The Erlang Distribution......Page 37
1.8.8 Normal Distribution......Page 38
1.9 Introduction to Stochastic Processes......Page 39
1.11 Characterizing a Stochastic Process......Page 40
1.11.1 Mean and Autocorrelation Function of a Stochastic Process......Page 41
1.12.1 Strict-Sense Stationary Processes......Page 42
1.13 Ergodic Stochastic Processes......Page 43
1.14.1 Martingales......Page 44
1.14.3 Independent Increment Processes......Page 47
1.14.5 Poisson Processes......Page 48
1.15 Problems......Page 53
2.1 Introduction......Page 60
2.2 Structure of Markov Processes......Page 61
2.3 Strong Markov Property......Page 63
2.4.1 Branching Processes......Page 64
2.5.1 Queueing Systems......Page 65
2.5.3 Stochastic Storage Systems......Page 66
2.6.2 Applications of Brownian Motion......Page 67
3.1 Introduction......Page 70
3.2.1 The n-Step State Transition Probability......Page 71
3.3 State Transition Diagrams......Page 73
3.4 Classification of States......Page 74
3.5 Limiting-State Probabilities......Page 76
3.5.1 Doubly Stochastic Matrix......Page 80
3.6 Sojourn Time......Page 81
3.7 Transient Analysis of Discrete-Time Markov Chains......Page 82
3.8 First Passage and Recurrence Times......Page 84
3.9 Occupancy Times......Page 87
3.10 Absorbing Markov Chains and the Fundamental Matrix......Page 88
3.10.1 Time to Absorption......Page 89
3.10.2 Absorption Probabilities......Page 92
3.11 Reversible Markov Chains......Page 93
3.12 Problems......Page 94
4.1 Introduction......Page 98
4.2 Transient Analysis......Page 101
4.3 Birth and Death Processes......Page 105
4.3.1 Local Balance Equations......Page 109
4.3.2 Transient Analysis of Birth and Death Processes......Page 110
4.4 First Passage Time......Page 111
4.5 The Uniformization Method......Page 113
4.7 Problems......Page 114
5.2 Description of a Queueing System......Page 120
5.3 The Kendall Notation......Page 123
5.4 The Little’s Formula......Page 124
5.6 The M/M/1 Queueing System......Page 125
5.6.2 Total Time and Waiting Time Distributions of the M/M/1 Queueing System......Page 129
5.7 Examples of Other M/M Queueing Systems......Page 132
5.7.1 The M/M/c Queue: The c-Server System......Page 133
5.7.2 The M/M/1/K Queue: The Single-Server Finite-Capacity System......Page 136
5.7.3 The M/M/c/c Queue: The c-Server Loss System......Page 141
5.7.4 The M/M/1//K Queue: The Single-Server Finite-Customer Population System......Page 143
5.8 M/G/1 Queue......Page 145
5.8.1 Waiting Time Distribution of the M/G/1 Queue......Page 147
5.8.2 The M/Ek/1 Queue......Page 150
5.8.3 The M/D/1 Queue......Page 152
5.8.5 The M/HK/1 Queue......Page 153
5.9 G/M/1 Queue......Page 155
5.9.1 The Ek/M/1 Queue......Page 159
5.9.2 The D/M/1 Queue......Page 160
5.9.3 The H2/ M/1 Queue......Page 161
5.10 Applications of Markovian Queues......Page 162
5.11 Problems......Page 163
6.1 Introduction......Page 168
6.2 The Renewal Equation......Page 169
6.2.1 Alternative Approach......Page 171
6.3 The Elementary Renewal Theorem......Page 173
6.4 Random Incidence and Residual Time......Page 174
6.5 Markov Renewal Process......Page 176
6.5.1 The Markov Renewal Function......Page 177
6.6 Semi-Markov Processes......Page 179
6.6.1 Discrete-Time Semi-Markov Processes......Page 180
6.6.2 Continuous-Time Semi-Markov Processes......Page 185
6.7 Markov Jump Processes......Page 190
6.7.1 The Homogeneous Markov Jump Process......Page 193
6.8 Problems......Page 196
7.1 Introduction......Page 200
7.2 Overview of Matrix-Analytic Methods......Page 201
7.3 Markovian Arrival Process......Page 206
7.3.1 Properties of MAP......Page 209
7.4 Batch Markovian Arrival Process......Page 211
7.4.1 Properties of BMAP......Page 214
7.5 Markov-Modulated Poisson Process......Page 215
7.5.1 The Interrupted Poisson Process......Page 216
7.5.3 Properties of MMPP......Page 218
7.5.4 The MMPP(2)/M/1 Queue......Page 220
7.6 Markov-Modulated Bernoulli Process......Page 224
7.6.1 The MMBP(2)......Page 225
7.7 Sample Applications of MAP and Its Derivatives......Page 227
7.8 Problems......Page 228
8.1 Introduction......Page 230
8.2 The Two-Dimensional Random Walk......Page 232
8.3 Random Walk as a Markov Chain......Page 233
8.5 Random Walk with Barriers......Page 234
8.6.1 Ruin Probability......Page 235
8.6.2 Duration of a Game......Page 237
8.7 First Return Times......Page 239
8.8 First Passage Times......Page 242
8.9 Maximum of a Random Walk......Page 244
8.10 Random Walk on a Graph......Page 246
8.10.1 Random Walk on a Weighted Graph......Page 251
8.11 Markov Random Walk......Page 252
8.11.1 Markov Random Walk in Semisupervised Machine Learning......Page 254
8.12 Random Walk with Correlation......Page 255
8.13 Continuous-Time Random Walk......Page 261
8.13.1 The Master Equation......Page 263
8.14.1 The Ballot Problem......Page 266
8.14.2 Web Search......Page 269
8.14.3 Mobility Models in Mobile Networks......Page 270
8.14.5 Content of a Dam......Page 272
8.15 Problems......Page 273
9.2 Brownian Motion......Page 278
9.2.2 Brownian Motion as a Markov Process......Page 280
9.2.4 First Passage Time of a Brownian Motion......Page 281
9.2.5 Maximum of a Brownian Motion......Page 283
9.2.6 First Passage Time in an Interval......Page 284
9.2.7 The Brownian Bridge......Page 285
9.3.1 The Ito Integral......Page 286
9.3.3 The Ito’s Formula......Page 288
9.4 Geometric Brownian Motion......Page 289
9.5 Fractional Brownian Motion......Page 291
9.6 Application of Brownian Motion to Option Pricing......Page 292
9.7 Random Walk Approximation of Brownian Motion......Page 295
9.8 The Ornstein-Uhlenbeck Process......Page 296
9.8.1 Mean Reverting Ornstein-Uhlenbeck Process......Page 300
9.8.2 Applications of the Ornstein-Uhlenbeck Process......Page 301
9.9 Diffusion Processes......Page 302
9.10.1 Brownian Motion......Page 304
9.10.2 Brownian Motion with Drift......Page 306
9.10.3 Levy Processes......Page 307
9.11 Relationship Between the Diffusion Process and Random Walk......Page 309
9.12 Problems......Page 310
10.2 Markov Decision Processes......Page 312
10.2.1 Overview of Dynamic Programming......Page 314
10.2.2 Markov Reward Processes......Page 317
10.2.3 MDP Basics......Page 319
10.2.4 MDPs with Discounting......Page 321
10.2.5 Solution Methods......Page 322
10.3 Semi-Markov Decision Processes......Page 332
10.3.1 Semi-Markov Reward Model......Page 333
10.3.2 Discounted Reward......Page 335
10.3.3 Analysis of the Continuous-Decision-Interval SMDPs......Page 336
10.3.4 Solution by Policy-Iteration......Page 338
10.3.5 SMDP with Discounting......Page 340
10.3.6 Solution by Policy Iteration when Discounting Is Used......Page 342
10.3.7 Analysis of the Discrete-Decision-Interval SMDPs with Discounting......Page 343
10.3.8 Continuous-Time Markov Decision Processes......Page 344
10.4 Partially Observable Markov Decision Processes......Page 345
10.4.1 Partially Observable Markov Processes......Page 347
10.4.2 POMDP Basics......Page 349
10.4.3 Solving POMDPs......Page 352
10.4.5 Approximate Solutions of POMDP......Page 353
10.5 Problems......Page 354
11.1 Introduction......Page 356
11.2 HMM Basics......Page 358
11.3 HMM Assumptions......Page 360
11.4 Three Fundamental Problems......Page 361
11.5.1 The Evaluation Problem......Page 362
11.5.2 The Decoding Problem and the Viterbi Algorithm......Page 371
11.5.3 The Learning Problem and the Baum-Welch Algorithm......Page 377
11.6 Types of Hidden Markov Models......Page 380
11.8 Extensions of Hidden Markov Models......Page 381
11.8.1 Hierarchical Hidden Markov Model......Page 382
11.8.2 Factorial Hidden Markov Model......Page 383
11.8.3 Coupled Hidden Markov Model......Page 384
11.8.4 Hidden Semi-Markov Models......Page 385
11.8.5 Profile HMMs for Biological Sequence Analysis......Page 386
11.9 Other Extensions of HMM......Page 390
11.10 Problems......Page 391
12.1 Introduction......Page 396
12.2 Markov Random Fields......Page 397
12.2.1 Graphical Representation......Page 401
12.2.2 Gibbs Random Fields and the Hammersley-Clifford Theorem......Page 403
12.3.1 The Ising Model......Page 405
12.3.2 The Potts Model......Page 407
12.3.3 Gauss-Markov Random Fields......Page 408
12.4 Hidden Markov Random Fields......Page 409
12.5 Applications of Markov Random Fields......Page 412
12.6 Problems......Page 413
13.1 Introduction......Page 416
13.2 Temporal Point Processes......Page 417
13.2.1 Specific Temporal Point Processes......Page 419
13.3 Spatial Point Processes......Page 420
13.3.1 Specific Spatial Point Processes......Page 422
13.4 Spatial-Temporal Point Processes......Page 425
13.5.1 Thinning......Page 428
13.5.3 Clustering......Page 429
13.6 Marked Point Processes......Page 430
13.7 Markov Point Processes......Page 431
13.8 Markov Marked Point Processes......Page 434
13.10 Problems......Page 435
14.1 Introduction......Page 438
14.2 Monte Carlo Simulation Basics......Page 439
14.2.1 Generating Random Variables from the Random Numbers......Page 441
14.2.2 Monte Carlo Integration......Page 444
14.3 Markov Chains Revisited......Page 446
14.4 MCMC Simulation......Page 448
14.4.1 The Metropolis-Hastings Algorithm......Page 449
14.4.2 Gibbs Sampling......Page 451
14.5.1 Simulated Annealing......Page 457
14.5.2 Inference in Belief Networks......Page 460
14.6 Choice of Method......Page 462
14.7 Problems......Page 463
References......Page 466
Index......Page 486