Preface ........................................................ xi
Author ....................................................... xiii
Chapter 1 Markov Chain Structure and Models .................... 1
1.1 Historical Note ............................................ 1
1.2 States and Transitions ..................................... 2
1.3 Model of the Weather ....................................... 5
1.4 Random Walks ............................................... 7
1.4.1 Barriers ............................................ 8
1.4.1.1 Absorbing Barriers ......................... 8
1.4.1.2 Gambler's Ruin ............................. 8
1.4.1.3 Reflecting Barriers ........................ 9
1.4.2 Circular Random Walk ................................ 9
1.5 Estimating Transition Probabilities ....................... 10
1.5.1 Conditioning on the Present State .................. 10
1.5.2 Conditioning on the Present and Previous States .... 11
1.6 Multiple-Step Transition Probabilities .................... 12
1.7 State Probabilities after Multiple Steps .................. 15
1.8 Classification of States .................................. 19
1.9 Markov Chain Structure .................................... 20
1.9.1 Unichain ........................................... 20
1.9.1.1 Irreducible ............................... 21
1.9.1.2 Reducible Unichain ........................ 23
1.9.2 Multichain ......................................... 24
1.9.3 Aggregated Canonical Form of the Transition
Matrix ............................................. 24
1.10 Markov Chain Models ....................................... 25
1.10.1 Unichain ........................................... 26
1.10.1.1 Irreducible ............................... 26
1.10.1.2 Reducible Unichain ........................ 43
1.10.2 Reducible Multichain ............................... 48
1.10.2.1 Absorbing Markov Chain .................... 49
1.10.2.2 Eight-State Multichain Model of a
Production Process ........................ 51
Problems .................................................. 54
References ................................................ 65
Chapter 2 Regular Markov Chains ............................... 67
2.1 Steady-State Probabilities ................................ 67
2.1.1 Calculating Steady-State Probabilities for
a Generic Two-State Markov Chain ................... 72
2.1.2 Calculating Steady-State Probabilities for a
Four-State Model of Weather ........................ 74
2.1.3 Steady-State Probabilities for Four-State Model
of Inventory System ................................ 76
2.1.4 Steady-State Probabilities for Four-State Model
of Component Replacement ........................... 76
2.2 First Passage to a Target State ........................... 77
2.2.1 Probability of First Passage in n Steps ............ 77
2.2.2 Mean First Passage Times ........................... 82
2.2.2.1 MFPTs for a Five-State Markov Chain ....... 82
2.2.2.2 MFPTs for a Four-State Model of
Component Replacement ..................... 86
2.2.2.3 MFPTs for a Four-State Model of Weather ... 87
2.2.3 Mean Recurrence Time ............................... 88
2.2.3.1 Mean Recurrence Time for a Five-State
Markov Chain .............................. 88
2.2.3.2 Mean Recurrence Times for a Four-State
Model of Component Replacement ............ 89
2.2.3.3 Optional Insight: Mean Recurrence Time
as the Reciprocal of the Steady-State
Probability for a Two-State Markov
Chain ..................................... 89
Problems .................................................. 91
References ................................................ 95
Chapter 3 Reducible Markov Chains ............................. 97
3.1 Canonical Form of the Transition Matrix ................... 97
3.1.1 Unichain ........................................... 97
3.1.2 Multichain ......................................... 99
3.1.3 Aggregation of the Transition Matrix in Canonical
Form .............................................. 100
3.2 The Fundamental Matrix ................................... 102
3.2.1 Definition of the Fundamental Matrix .............. 102
3.2.2 Mean Time in a Particular Transient State ......... 103
3.2.3 Mean Time in All Transient States ................. 105
3.2.4 Absorbing Multichain Model of Patient Flow in a
Hospital .......................................... 106
3.3 Passage to a Target State ................................ 108
3.3.1 Mean First Passage Times in a Regular Markov
Chain Revisited ................................... 108
3.3.2 Probability of First Passage in n Steps ........... 110
3.3.2.1 Reducible Unichain ....................... 110
3.3.2.2 Reducible Multichain ..................... 118
3.3.3 Probability of Eventual Passage to a Recurrent
State ............................................. 122
3.3.3.1 Reducible Unichain ....................... 125
3.3.3.2 Reducible Multichain ..................... 130
3.4 Eventual Passage to a Closed Set within a Reducible
Multichain ............................................... 138
3.4.1 Method One: Replacing Recurrent Sets with
Absorbing States and Using the Fundamental
Matrix ............................................ 138
3.4.1.1 Five-State Reducible Multichain .......... 138
3.4.1.2 Multichain Model of an Eight-State
Serial Production Process ................ 140
3.4.2 Method Two: Direct Calculation without Using the
Fundamental Matrix ................................ 142
3.5 Limiting Transition Probability Matrix ................... 143
3.5.1 Recurrent Multichain .............................. 143
3.5.2 Absorbing Markov Chain ............................ 145
3.5.3 Absorbing Markov Chain Model of Patient Flow in
a Hospital ........................................ 146
3.5.4 Reducible Unichain ................................ 147
3.5.4.1 Reducible Four-State Unichain ............ 149
3.5.4.2 Reducible Unichain Model of Machine
Maintenance .............................. 149
3.5.5 Reducible Multichain .............................. 150
3.5.5.1 Reducible Five-State Multichain .......... 152
3.5.5.2 Reducible Multichain Model of an
Eight-State Serial Production Process .... 153
3.5.5.3 Conditional Mean Time to Absorption ...... 156
Problems ................................................. 157
References ............................................... 163
Chapter 4 A Markov Chain with Rewards (MCR) .................. 165
4.1 Rewards .................................................. 165
4.1.1 Planning Horizon .................................. 165
4.1.2 Reward Vector ..................................... 166
4.2 Undiscounted Rewards ..................................... 168
4.2.1 MCR Chain Structure ............................... 168
4.2.2 A Recurrent MCR over a Finite Planning Horizon .... 169
4.2.2.1 An MCR Model of Monthly Sales ............ 169
4.2.2.2 Value Iteration over a Fixed Planning
Horizon .................................. 172
4.2.2.3 Lengthening a Finite Planning Horizon .... 179
4.2.2.4 Numbering the Time Periods Forward ....... 182
4.2.3 A Recurrent MCR over an Infinite Planning
Horizon ........................................... 182
4.2.3.1 Expected Average Reward or Gain .......... 183
4.2.3.2 Value Determination Equations (VDEs) ..... 185
4.2.3.3 Value Iteration .......................... 190
4.2.3.4 Examples of Recurrent MCR Models ......... 194
4.2.4 A Unichain MCR .................................... 201
4.2.4.1 Expected Average Reward or Gain .......... 201
4.2.4.2 Value Determination Equations ............ 206
4.2.4.3 Solution by Value Iteration of Unichain
MCR Model of Machine Maintenance
under Modified Policy of Doing Nothing
in State 3 ............................... 211
4.2.4.4 Expected Total Reward before Passage to
a Closed Set ............................. 214
4.2.4.5 Value Iteration over a Finite Planning
Horizon .................................. 218
4.2.5 A Multichain MCR .................................. 220
4.2.5.1 An Eight-State Multichain MCR Model of
a Production Process ..................... 221
4.2.5.2 Expected Average Reward or Gain .......... 224
4.2.5.3 Reward Evaluation Equations .............. 227
4.2.5.4 Expected Total Reward before Passage to
a Closed Set ............................. 239
4.2.5.5 Value Iteration over a Finite Planning
Horizon .................................. 243
4.3 Discounted Rewards ....................................... 245
4.3.1 Time Value of Money ............................... 245
4.3.2 Value Iteration over a Finite Planning Horizon .... 246
4.3.2.1 Value Iteration Equation ................. 246
4.3.2.2 Value Iteration for Discounted MCR Model
of Monthly Sales ......................... 249
4.3.3 An Infinite Planning Horizon ...................... 251
4.3.3.1 VDEs for Expected Total Discounted
Rewards .................................. 251
4.3.3.2 Value Iteration for Expected Total
Discounted Rewards ....................... 260
Problems ................................................. 263
References ............................................... 270
Chapter 5 A Markov Decision Process (MDP) .................... 271
5.1 An Undiscounted MDP ...................................... 271
5.1.1 MDP Chain Structure ............................... 271
5.1.2 A Recurrent MDP ................................... 272
5.1.2.1 A Recurrent MDP Model of Monthly Sales ... 272
5.1.2.2 Value Iteration over a Finite Planning
Horizon .................................. 275
5.1.2.3 An Infinite Planning Horizon ............. 284
5.1.3 A Unichain MDP .................................... 315
5.1.3.1 Policy Iteration (PI) .................... 315
5.1.3.2 Linear Programming ....................... 323
5.1.3.3 Examples of Unichain MDP Models .......... 329
5.1.4 A Multichain MDP .................................. 350
5.1.4.1 Multichain Model of a Flexible
Production System ........................ 350
5.1.4.2 PI for a Multichain MDP .................. 352
5.1.4.3 Linear Programming ....................... 361
5.1.4.4 A Multichain MDP Model of Machine
Maintenance .............................. 368
5.2 A Discounted MDP ......................................... 374
5.2.1 Value Iteration over a Finite Planning Horizon .... 374
5.2.1.1 Value Iteration Equation ................. 374
5.2.1.2 Value Iteration for Discounted MDP
Model of Monthly Sales ................... 374
5.2.2 An Infinite Planning Horizon ...................... 382
5.2.2.1 Value Iteration .......................... 383
5.2.2.2 Policy Iteration ......................... 385
5.2.2.3 LP for a Discounted MDP .................. 396
5.2.2.4 Examples of Discounted MDP Models ........ 404
Problems ................................................. 413
References ............................................... 422
Chapter 6 Special Topics: State Reduction and Hidden Markov
Chains ............................................. 423
6.1 State Reduction .......................................... 423
6.1.1 Markov Chain Partitioning Algorithm for
Computing Steady-State Probabilities .............. 424
6.1.1.1 Matrix Reduction of a Partitioned
Markov Chain ............................. 424
6.1.1.2 Optional Insight: Informal
Justification of the Formula for Matrix
Reduction ................................ 426
6.1.1.3 Optional Insight: Informal Derivation
of the MCPA .............................. 427
6.1.1.4 Markov Chain Partitioning Algorithm ...... 431
6.1.1.5 Using the MCPA to Compute the Steady-
State Probabilities for a Four-State
Markov Chain ............................. 432
6.1.1.6 Optional Insight: Matrix Reduction and
Gaussian Elimination ..................... 433
6.1.2 Mean First Passage Times .......................... 435
6.1.2.1 Forming the Augmented Matrix ............. 435
6.1.2.2 State Reduction Algorithm for Computing
MFPTs .................................... 436
6.1.2.3 Using State Reduction to Compute MFPl\
for a Five-State Markov Chain ............ 437
6.1.3 Absorption Probabilities .......................... 439
6.1.3.1 Forming the Augmented Matrix ............. 439
6.1.3.2 State Reduction Algorithm for Computing
Absorption Probabilities ................. 440
6.1.3.3 Using State Reduction to Compute
Absorption Probabilities for an
Absorbing Multichain Model of Patient
Flow in a Hospital ........................ 441
6.2 An Introduction to Hidden Markov Chains .................. 443
6.2.1 HMM of the Weather ................................ 444
6.2.2 Generating an Observation Sequence ................ 446
6.2.3 Parameters of an HMM .............................. 447
6.2.4 Three Basic Problems for HMMs ..................... 447
6.2.4.1 Solution to Problem 1 .................... 448
6.2.4.2 Solution to Problem 2 .................... 455
Problems ................................................. 460
References ............................................... 462
Index ......................................................... 463
| 
