Sheskin T.J. Markov chains and decision processes for engineers and managers (Boca Raton; London; New York, 2011). - ОГЛАВЛЕНИЕ / CONTENTS
Навигация

Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
ОбложкаSheskin T.J. Markov chains and decision processes for engineers and managers. - Boca Raton; London; New York: CRC Press, 2011. - xiii, 478 p.: ill. - Ind.: p.463-478. - ISBN 978-1-4200-5111-7
 

Оглавление / Contents
 
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


Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
 

[О библиотеке | Академгородок | Новости | Выставки | Ресурсы | Библиография | Партнеры | ИнфоЛоция | Поиск]
  Пожелания и письма: branch@gpntbsib.ru
© 1997-2024 Отделение ГПНТБ СО РАН (Новосибирск)
Статистика доступов: архив | текущая статистика
 

Документ изменен: Wed Feb 27 14:23:50 2019. Размер: 19,305 bytes.
Посещение N 1373 c 04.09.2012