# Markov Chains: From Theory to Implementation and Experimentation

## Books

A fascinating and instructive guide to Markov chains for experienced users and newcomers alike

This unique guide to Markov chains approaches the subject along the four convergent lines of mathematics, implementation, simulation, and experimentation. It introduces readers to the art of stochastic modeling, shows how to design computer implementations, and provides extensive worked examples with case studies.

Markov Chains: From Theory to Implementation and Experimentation begins with a general introduction to the history of probability theory in which the author uses quantifiable examples to illustrate how probability theory arrived at the concept of discrete-time and the Markov model from experiments involving independent variables. An introduction to simple stochastic matrices and transition probabilities is followed by a simulation of a two-state Markov chain. The notion of steady state is explored in connection with the long-run distribution behavior of the Markov chain. Predictions based on Markov chains with more than two states are examined, followed by a discussion of the notion of absorbing Markov chains. Also covered in detail are topics relating to the average time spent in a state, various chain configurations, and n-state Markov chain simulations used for verifying experiments involving various diagram configurations.

• Fascinating historical notes shed light on the key ideas that led to the development of the Markov model and its variants

• Various configurations of Markov Chains and their limitations are explored at length

• Numerous examples—from basic to complex—are presented in a comparative manner using a variety of color graphics

• All algorithms presented can be analyzed in either Visual Basic, Java Script, or PHP

• Designed to be useful to professional statisticians as well as readers without extensive knowledge of probability theory

Covering both the theory underlying the Markov model and an array of Markov chain implementations, within a common conceptual framework, Markov Chains: From Theory to Implementation and Experimentation is a stimulating introduction to and a valuable reference for those wishing to deepen their understanding of this extremely valuable statistical tool.

Paul A. Gagniuc, PhD, is Associate Professor at Polytechnic University of Bucharest, Romania. He obtained his MS and his PhD in genetics at the University of Bucharest. Dr. Gagniuc’s work has been published in numerous high profile scientific journals, ranging from the Public Library of Science to BioMed Central and Nature journals. He is the recipient of several awards for exceptional scientific results and a highly active figure in the review process for different scientific areas.

Abstract ix

Preface xi

Acknowledgments xiii

1 Historical Notes 1

1.1 Introduction 1

1.2 On theWings of Dependent Variables 2

1.3 From Bernoulli to Markov 5

2 FromObservation to Simulation 9

2.1 Introduction 9

2.2 Stochastic Matrices 9

2.3 Transition Probabilities 11

2.4 The Simulation of a Two-State Markov Chain 14

3 Building the Stochastic Matrix 25

3.1 Introduction 25

3.2 Building a Stochastic Matrix from Events 25

3.3 Building a Stochastic Matrix from Percentages 32

4 Predictions Using Two-State Markov Chains 37

4.1 Introduction 37

4.2 Performing the Predictions by Using the Stochastic Matrix 37

4.3 The Steady State of a Markov Chain 46

4.4 The Long-Run Distribution of a Markov Chain 55

5 Predictions Using n-State Markov Chains 61

5.1 Introduction 61

5.2 Predictions by Using the Three-State Markov Chain 61

5.3 Predictions by Using the Four-State Markov Chain 71

5.4 Predictions by Using n-State Markov Chains 80

5.5 Markov Chain Modeling on Measurements 84

6 AbsorbingMarkov Chains 93

6.1 Introduction 93

6.2 The Absorbing State 93

7 The Average Time Spent in Each State 99

7.1 Introduction 99

7.2 The Proportion of Balls in the System 99

7.3 The Average Time Spent in A Particular State 100

7.4 Exemplification of the Average Time and Proportions 101

8 Discussions on Different Configurations of Chains 107

8.1 Introduction 107

8.2 Examples of Two-State Diagrams 113

8.3 Examples of Three-State Diagrams 115

8.4 Examples of Four-State Diagrams 117

8.5 Examples of State Diagrams Divided into Classes 123

8.6 Examples of State Diagrams with Absorbing States 127

8.7 The Gambler’s Ruin 128

9 The Simulation of an n-State Markov Chain 131

9.1 Introduction 131

9.2 The Simulation of Behavior 131

9.3 Simulation of Different Chain Configurations 145

A Supporting Algorithms in PHP 165

B Supporting Algorithms in Javascript 193

C Syntax Equivalence between Languages 223

Glossary 225

References 227

Index 231

View all

View all