Markov Chains

by Ching, Wai-Ki; Ng, Michael K.

• ISBN13: 9780387293356
• ISBN10: 0387293353
• Format: Hardcover
• Copyright: 2006-01-31
• Publisher: Springer-Verlag New York Inc

Summary

MARKOV CHAINS: Models, Algorithms and Applications outlines recent developments of Markov chain models for modeling queueing sequences, Internet, re-manufacturing systems, reverse logistics, inventory systems, bio-informatics, DNA sequences, genetic networks, data mining, and many other practical systems.The book consists of eight chapters. Chapter 1 is 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 is also discussed. Chapter 2 discusses the applications of continuous time Markov chains to model queueing systems and discrete time Markov chains for computing. Chapter 3 studies re-manufacturing systems and presents Markovian models for reverse manufacturing applications. In Chapter 4, Hidden Markov models are applied to classify customers. Chapter 5 discusses the Markov decision process for customer lifetime values. Customer Lifetime Values (CLV) is an important concept and quantity in marketing management. Chapter 6 covers higher-order Markov chain models. Multivariate Markov models are discussed in Chapter 7. It presents a class of multivariate Markov chain models with a lower order of model parameters. Chapter 8 studies higher-order hidden Markov models. It proposes a class of higher-order hidden Markov models with an efficient algorithm for solving the model parameters.This book is aimed at students, professionals, practitioners, and researchers in applied mathematics, scientific computing, and operational research, who are interested in the formulation and computation of queueing and manufacturing systems.

Table of Contents

1 Introduction	1	(36)
1.1 Markov Chains	1	(15)
1.1.1 Examples of Markov Chains	2	(3)
1.1.2 The nth-Step Transition Matrix	5	(2)
1.1.3 Irreducible Markov Chain and Classifications of States	7	(1)
1.1.4 An Analysis of the Random Walk	8	(2)
1.1.5 Simulation of Markov Chains with EXCEL	10	(1)
1.1.6 Building a Markov Chain Model	11	(3)
1.1.7 Stationary Distribution of a Finite Markov Chain	14	(2)
1.1.8 Applications of the Stationary Distribution	16	(1)
1.2 Continuous Time Markov Chain Process	16	(3)
1.2.1 A Continuous Two-state Markov Chain	18	(1)
1.3 Iterative Methods for Solving Linear Systems	19	(13)
1.3.1 Sonic Results on Matrix Theory	20	(1)
1.3.2 Splitting of a Matrix	21	(1)
1.3.3 Classical Iterative Methods	22	(2)
1.3.4 Spectral Radius	24	(2)
1.3.5 Successive Over-Relaxation (SOR) Method	26	(1)
1.3.6 Conjugate Gradient Method	26	(4)
1.3.7 Toeplitz Matrices	30	(2)
1.4 Hidden Markov Models	32	(1)
1.5 Markov Decison Process	33	(4)
1.5.1 Stationary Policy	35	(2)
2 Queueing Systems and the Web	37	(24)
2.1 Markovian Queueing Systems	37	(10)
2.1.1 An M/M/1/n — 2 Queueing System	37	(2)
2.1.2 An M/M/s/n — s — 1 Queueing System	39	(2)
2.1.3 The Two-Queue Free System	41	(1)
2.1.4 The Two-Queue Overflow System	42	(1)
2.1.5 The Preconditioning of Complex Queueing Systems	43	(4)
2.2 Search Engines	47	(11)
2.2.1 The PageRank Algorithm	49	(1)
2.2.2 The Power Method	50	(1)
2.2.3 An Example	51	(1)
2.2.4 The SOR/JOR Method and the Hybrid Method	52	(2)
2.2.5 Convergence Analysis	54	(4)
2.3 Summary	58	(3)
3 Re-manufacturing Systems	61	(16)
3.1 Introduction	61	(1)
3.2 An Inventory Model for Returns	62	(4)
3.3 The Lateral Transshipment Model	66	(2)
3.4 The Hybrid Re-manufacturing Systems	68	(7)
3.4.1 The Hybrid System	69	(1)
3.4.2 The Generator Matrix of the System	69	(2)
3.4.3 The Direct Method	71	(3)
3.4.4 The Computational Cost	74	(1)
3.4.5 Some Special Cases Analysis	74	(1)
3.5 Summary	75	(2)
4 Hidden Markov Model for Customers Classification	77	(10)
4.1 Introduction	77	(1)
4.1.1 A Simple Example	77	(1)
4.2 Parameter Estimation	78	(1)
4.3 Extension of the Method	79	(1)
4.4 Special Case Analysis	80	(2)
4.5 Application to Classification of Customers	82	(3)
4.6 Summary	85	(2)
5 Markov Decision Process for Customer Lifetime Value	87	(24)
5.1 Introduction	87	(2)
5.2 Markov Chain Models for Customers' Behavior	89	(3)
5.2.1 Estimation of the Transition Probabilities	90	(1)
5.2.2 Retention Probability and CLV	91	(1)
5.3 Stochastic Dynamic Programming Models	92	(10)
5.3.1 Infinite Horizon without Constraints	93	(2)
5.3.2 Finite Horizon with Hard Constraints	95	(1)
5.3.3 Infinite Horizon with Constraints	96	(6)
5.4 Higher-order Markov decision process	102	(4)
5.4.1 Stationary policy	103	(2)
5.4.2 Application to the calculation of CLV	105	(1)
5.5 Summary	106	(5)
6 Higher-order Markov Chains	111	(30)
6.1 Introduction	111	(1)
6.2 Higher-order Markov Chains	112	(9)
6.2.1 The New Model	113	(3)
6.2.2 Parameters Estimation	116	(3)
6.2.3 An Example	119	(2)
6.3 Some Applications	121	(8)
6.3.1 The DNA Sequence	122	(2)
6.3.2 The Sales Demand Data	124	(2)
6.3.3 Webpages Prediction	126	(3)
6.4 Extension of the Model	129	(5)
6.5 Newboy's Problems	134	(5)
6.5.1 A Markov Chain Model for the Newsboy's Problem	135	(3)
6.5.2 A Numerical Example	138	(1)
6.6 Summary	139	(2)
7 Multivariate Markov Chains	141	(30)
7.1 Introduction	141	(1)
7.2 Construction of Multivariate Markov Chain Models	141	(7)
7.2.1 Estimations of Model Parameters	144	(2)
7.2.2 An Example	146	(2)
7.3 Applications to Multi-product Demand Estimation	148	(2)
7.4 Applications to Credit Rating	150	(3)
7.4.1 The Credit Transition Matrix	151	(2)
7.5 Applications to DNA Sequences Modeling	153	(3)
7.6 Applications to Genetic Networks	156	(11)
7.6.1 An Example	161	(2)
7.6.2 Fitness of the Model	163	(4)
7.7 Extension to Higher-order Multivariate Markov Chain	167	(2)
7.8 Summary	169	(2)
8 Hidden Markov Chains	171	(20)
8.1 Introduction	171	(1)
8.2 Higher-order HMMs	171	(12)
8.2.1 Problem 1	173	(2)
8.2.2 Problem 2	175	(1)
8.2.3 Problem 3	176	(2)
8.2.4 The EM Algorithm	178	(1)
8.2.5 Heuristic Method for Higher-order HMMs	179	(3)
8.2.6 Experimental Results	182	(1)
8.3 The Interactive Hidden Markov Model	183	(4)
8.3.1 An Example	183	(1)
8.3.2 Estimation of Parameters	184	(2)
8.3.3 Extension to the General Case	186	(1)
8.4 The Double Higher-order Hidden Markov Model	187	(2)
8.5 Summary	189	(2)
References	191	(12)
Index	203