Markov Chains : Models, Algorithms and Applications

✍ Scribed by Ching W.K., et al.

• Publisher: Springer
• Year: 2013
• Tongue: English
• Leaves: 258
• Series: International Series in Operations Research & Management Science, 189
• Edition: 2ed.
• Category: Library

✦ Synopsis

This new edition of Markov Chains: Models, Algorithms and Applications has been completely reformatted as a text, complete with end-of-chapter exercises, a new focus on management science, new applications of the models, and new examples with applications in financial risk management and modeling of financial data.This book consists of eight chapters. Chapter 1 gives a brief introduction to the classical theory on both discrete and continuous time Markov chains. The relationship between Markov chains of finite states and matrix theory will also be highlighted. Some classical iterative methods for solving linear systems will be introduced for finding the stationary distribution of a Markov chain. The chapter then covers the basic theories and algorithms for hidden Markov models (HMMs) and Markov decision processes (MDPs).Chapter 2 discusses the applications of continuous time Markov chains to model queueing systems and discrete time Markov chain for computing the PageRank, the ranking of websites on the Internet. Chapter 3 studies Markovian models for manufacturing and re-manufacturing systems and presents closed form solutions and fast numerical algorithms for solving the captured systems. In Chapter 4, the authors present a simple hidden Markov model (HMM) with fast numerical algorithms for estimating the model parameters. An application of the HMM for customer classification is also presented. Chapter 5 discusses Markov decision processes for customer lifetime values. Customer Lifetime Values (CLV) is an important concept and quantity in marketing management. The authors present an approach based on Markov decision processes for the calculation of CLV using real data.Chapter 6 considers higher-order Markov chain models, particularly a class of parsimonious higher-order Markov chain models. Efficient estimation methods for model parameters based on linear programming are presented. Contemporary research results on applications to demand predictions, i. Read more... Introduction.- Manufacturing and Re-manufacturing Systems.- A Hidden Markov Model for Customer Classification.- Markov Decision Processes for Customer Lifetime Value.- Higher-order Markov Chains.- Multivariate Markov Chains.- Hidden Markov Chains

✦ Table of Contents

Cover......Page 1
Markov Chains......Page 4
Preface......Page 8
Contents......Page 10
List of Figures......Page 14
List of Tables......Page 16
1.1 Markov Chains......Page 18
1.1.1 Examples of Markov Chains......Page 19
1.1.2 The nth-Step Transition Matrix......Page 22
1.1.3 Irreducible Markov Chain and Classifications of States......Page 24
1.1.4 An Analysis of the Random Walk......Page 25
1.1.5 Simulation of Markov Chains with EXCEL......Page 27
1.1.6 Building a Markov Chain Model......Page 28
1.1.7 Stationary Distribution of a Finite Markov Chain......Page 30
1.1.8 Applications of the Stationary Distribution......Page 35
1.2 Continuous Time Markov Chain Process......Page 36
1.2.1 A Continuous Two-State Markov Chain......Page 38
1.3 Iterative Methods for Solving Linear Systems......Page 39
1.3.1 Some Results on Matrix Theory......Page 40
1.3.2 Splitting of a Matrix......Page 41
1.3.3 Classical Iterative Methods......Page 43
1.3.4 Spectral Radius......Page 45
1.3.5 Successive Over-Relaxation (SOR) Method......Page 46
1.3.6 Conjugate Gradient Method......Page 47
1.3.6.1 Conjugate Gradient Squared Method......Page 50
1.3.7 Toeplitz Matrices......Page 51
1.4 Hidden Markov Models......Page 52
1.5 Markov Decision Process......Page 54
1.5.1 Stationary Policy......Page 58
1.6 Exercises......Page 59
2.1 Markovian Queueing Systems......Page 64
2.1.1 An M/M/1/n-2 Queueing System......Page 65
2.1.2 An M/M/s/n-s-1 Queueing System......Page 66
2.1.3 Allocation of the Arrivals in a Systemof M/M/1/∞ Queues......Page 68
2.1.4 Two M/M/1 Queues or One M/M/2 Queue?......Page 70
2.1.5 The Two-Queue Free System......Page 71
2.1.6 The Two-Queue Overflow System......Page 72
2.1.7 The Preconditioning of Complex Queueing Systems......Page 73
2.1.7.1 Circulant-Based Preconditioners......Page 74
2.1.7.2 Toeplitz-Circulant-Based Preconditioners......Page 75
2.2 Search Engines......Page 77
2.2.1 The PageRank Algorithm......Page 79
2.2.2 The Power Method......Page 80
2.2.3 An Example......Page 82
2.2.4 The SOR/JOR Method and the Hybrid Method......Page 83
2.2.5 Convergence Analysis......Page 85
2.3 Summary......Page 89
2.4 Exercise......Page 90
3.1 Introduction......Page 94
3.2.1.1 One-Machine Manufacturing System......Page 96
3.2.1.2 Two-Machine Manufacturing System......Page 97
3.2.1.3 Multiple Unreliable Machines Manufacturing System......Page 99
3.3 An Inventory Model for Returns......Page 100
3.4 The Lateral Transshipment Model......Page 104
3.5.1 The Hybrid System......Page 106
3.5.2 The Generator Matrix of the System......Page 107
3.5.3 The Direct Method......Page 109
3.5.5 Special Case Analysis......Page 112
3.7 Exercises......Page 113
4.1.1 A Simple Example......Page 114
4.2 Parameter Estimation......Page 115
4.3 An Extension of the Method......Page 116
4.4 A Special Case Analysis......Page 118
4.5 Applying HMM to the Classification of Customers......Page 120
4.7 Exercises......Page 122
5.1 Introduction......Page 124
5.2 Markov Chain Models for Customer Behavior......Page 126
5.2.1 Estimation of the Transition Probabilities......Page 127
5.2.2 Retention Probability and CLV......Page 128
5.3 Stochastic Dynamic Programming Models......Page 129
5.3.1 Infinite Horizon Without Constraints......Page 130
5.3.2 Finite Horizon with Hard Constraints......Page 132
5.3.3 Infinite Horizon with Constraints......Page 133
5.4 An Extension to Multi-period Promotions......Page 138
5.4.2 The Infinite Horizon Without Constraints......Page 140
5.4.3 Finite Horizon with Hard Constraints......Page 142
5.5 Higher-Order Markov Decision Process......Page 148
5.5.1 Stationary Policy......Page 149
5.5.2 Application to the Calculation of CLV......Page 151
5.6 Summary......Page 152
5.7 Exercises......Page 154
6.1 Introduction......Page 157
6.2 Higher-Order Markov Chains......Page 158
6.2.1 The New Model......Page 159
6.2.2 Parameter Estimation......Page 162
6.2.3 An Example......Page 166
6.3 Some Applications......Page 168
6.3.1 The Sales Demand Data......Page 169
6.3.2.1 Web Log Files and Preprocessing......Page 171
6.3.2.2 Prediction Models......Page 172
6.4 Extension of the Model......Page 174
6.5 The Newsboy Problem......Page 178
6.5.1 A Markov Chain Model for the Newsboy Problem......Page 179
6.6 Higher-Order Markov Regime-Switching Model for Risk Measurement......Page 183
6.6.1 A Snapshot for Markov Regime-Switching Models......Page 184
6.6.2 A Risk Measurement Framework Based on a HMRSModel......Page 186
6.6.3 Value at Risk Forecasts......Page 190
6.7 Summary......Page 191
6.8 Exercise......Page 192
7.2 Construction of Multivariate Markov Chain Models......Page 193
7.2.1 Estimations of Model Parameters......Page 197
7.2.2 An Example......Page 199
7.3 Applications to Multi-product Demand Estimation......Page 200
7.4 Applications to Credit Ratings Models......Page 203
7.4.1 The Credit Transition Matrix......Page 204
7.5 Extension to a Higher-Order Multivariate Markov Chain......Page 206
7.6 An Improved Multivariate Markov Chain and Its Application to Credit Ratings......Page 208
7.6.1 Convergence Property of the Model......Page 209
7.6.2 Estimation of Model Parameters......Page 211
7.6.3 Practical Implementation, Accuracy and ComputationalEfficiency......Page 213
7.7 Summary......Page 215
7.8 Exercise......Page 216
8.2 Higher-Order HMMs......Page 217
8.2.1 Problem 1......Page 219
8.2.2 Problem 2......Page 221
8.2.3 Problem 3......Page 223
8.2.4 The EM Algorithm......Page 224
8.2.5 Heuristic Method for Higher-Order HMMs......Page 226
8.3 The Double Higher-Order Hidden Markov Model......Page 228
8.4.1 An Example......Page 230
8.4.2 Estimation of Parameters......Page 231
8.4.3 Extension to the General Case......Page 233
8.5 The Binomial Expansion Model for Portfolio Credit Risk Modulated by the IHMM......Page 234
8.5.1 Examples......Page 237
8.5.2 Estimation of the Binomial Expansion ModelModulated by the IHMM......Page 238
8.5.3 Numerical Examples and Comparison......Page 240
8.7 Exercises......Page 246
References......Page 247
Index......Page 256