Contents

1 Introduction 1

1.1 Markov Chains 1

1.1.1 Examples of Markov Chains 2

1.1.2 The nth-Step Transition Matrix 5

1.1.3 Irreducible Markov Chain and Classifications of States 7

1.1.4 An Analysis of the Random Walk 8

1.1.5 Simulation of Markov Chains with EXCEL 10

1.1.6 Building a Markov Chain Model11

1.1.7 Stationary Distribution of a Finite Markov Chain 14

1.1.8 Applications of the Stationary Distribution 16

1.2 Continuous Time Markov Chain Process 16

1.2.1 A Continuous Two-state Markov Chain 18

1.3 Iterative Methods for Solving Linear Systems 19

1.3.1 Some Results on Matrix Theory 20

1.3.2 Splitting of a Matrix 21

1.3.3 Classical Iterative Methods 22

1.3.4 Spectral Radius 24

1.3.5 Successive Over-Relaxation (SOR) Method 26

1.3.6 Conjugate Gradient Method 26

1.3.7 Toeplitz Matrices 30

1.4 Hidden Markov Models 32

1.5 Markov Decison Process 33

1.5.1 Stationary Policy 35

2 Queueing Systems and the Web 37

2.1 Markovian Queueing Systems 37

2.1.1 An M/M/1/n − 2 Queueing System 37

2.1.2 An M/M/s/n − s − 1 Queueing System 39

2.1.3 The Two-Queue Free System 41

2.1.4 The Two-Queue Overflow System 42

2.2 Search Engines 47

2.2.1 The PageRank Algorithm 49

2.2.2 The Power Method 50

2.2.3 An Example 51

2.2.4 The SOR/JOR Method and the Hybrid Method 52

2.2.5 Convergence Analysis 54

2.3 Summary 58

3 Re-manufacturing Systems 61

3.1 Introduction 61

3.2 An Inventory Model for Returns 62

3.3 The Lateral Transshipment Model 66

3.4 The Hybrid Re-manufacturing Systems 68

3.4.1 The Hybrid System 69

3.4.2 The Generator Matrix of the System 69

3.4.3 The Direct Method 71

3.4.4 The Computational Cost 74

3.4.5 Some Special Cases Analysis 74

3.5 Summary 75

4 Hidden Markov Model for Customers Classification77

4.1 Introduction 77

4.1.1 A Simple Example77

4.2 Parameter Estimation 78

4.3 Extension of the Method 79

4.4 Special Case Analysis 80

4.5 Application to Classification of Customers 82

4.6 Summary 85

5 Markov Decision Process for Customer Lifetime Value 87

5.1 Introduction 87

5.2 Markov Chain Models for Customers’ Behavior 89

5.2.1 Estimation of the Transition Probabilities 90

5.2.2 Retention Probability and CLV 91

5.3 Stochastic Dynamic Programming Models 92

5.3.1 Infinite Horizon without Constraints 93

5.3.2 Finite Horizon with Hard Constraints 95

5.3.3 Infinite Horizon with Constraints 96

5.4 Higher-order Markov decision process 102

5.4.1 Stationary policy 103

5.4.2 Application to the calculation of CLV 105

6 Higher-order Markov Chains 111

6.1 Introduction 111

6.2 Higher-order Markov Chains 112

6.2.1 The New Model 113

6.2.2 Parameters Estimation 116

6.2.3 An Example 119

6.3 Some Applications 121

6.3.1 The DNA Sequence 122

6.3.2 The Sales Demand Data 124

6.3.3 Webpages Prediction126

6.4 Extension of the Model 129

6.5 Newboy’s Problems 134

6.5.1 A Markov Chain Model for the Newsboy’s Problem 135

6.5.2 A Numerical Example 138

6.6 Summary 139

7 Multivariate Markov Chains 141

7.1 Introduction 141

7.2 Construction of Multivariate Markov Chain Models 141

7.2.1 Estimations of Model Parameters 144

7.2.2 An Example 146

7.3 Applications to Multi-product Demand Estimation 148

7.4 Applications to Credit Rating 150

7.4.1 The Credit Transition Matrix 151

7.5 Applications to DNA Sequences Modeling 153

7.6 Applications to Genetic Networks 156

7.6.1 An Example 161

7.6.2 Fitness of the Model 163

7.7 Extension to Higher-order Multivariate Markov Chain 167

7.8 Summary 169

8 Hidden Markov Chains 171

8.1 Introduction 171

8.2 Higher-order HMMs 171

8.2.1 Problem 1 173

8.2.2 Problem 2 175

8.2.3 Problem 3 176

8.2.4 The EM Algorithm 178

8.2.5 Heuristic Method for Higher-order HMMs 179

8.2.6 Experimental Results 182

8.3 The Interactive Hidden Markov Model 183

8.3.1 An Example 183

8.3.2 Estimation of Parameters 184

8.3.3 Extension to the General Case 186

8.5 Summary 189

References 191