reading

This edition first published 2017

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Paul A. Gagniuc to be identified as the author(s) of this work has been asserted in accordance with law.

Registered Offices

John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA

Editorial Office

111 River Street, Hoboken, NJ 07030, USA

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Wiley also publishes its books in a variety of electronic formats and by print-on-demand. Some content that appears in standard print versions of this book may not be available in other formats.

Limit of Liability/Disclaimer of Warranty

The publisher and the authors make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties; including without limitation any implied warranties of fitness for a particular purpose. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for every situation. In view of on-going research, equipment modifications, changes in governmental regulations, and the constant flow of information relating to the use of experimental reagents, equipment, and devices, the reader is urged to review and evaluate the information provided in the package insert or instructions for each chemical, piece of equipment, reagent, or device for, among other things, any changes in the instructions or indication of usage and for added warnings and precautions. The fact that an organization or website is referred to in this work as a citation and/or potential source of further information does not mean that the author or the publisher endorses the information the organization or website may provide or recommendations it may make. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this works was written and when it is read. No warranty may be created or extended by any promotional statements for this work. Neither the publisher nor the author shall be liable for any damages arising here from.

Library of Congress Cataloging-in-Publication Data

Names: Gagniuc, Paul A., author.

Title: Markov chains : from theory to implementation and experimentation / Paul A. Gagniuc.

Description: Hoboken, NJ : John Wiley & Sons, 2017. | Includes bibliographical references and index. |

Identifiers: LCCN 2017011637 (print) | LCCN 2017018061 (ebook) | ISBN 9781119387572 (pdf) | ISBN 9781119387589 (epub) | ISBN 9781119387558 (cloth)

Subjects: LCSH: Markov processes.

Classification: LCC QA274.7 (ebook) | LCC QA274.7 .G34 2017 (print) | DDC 519.2/33--dc23

LC record available at https://lccn.loc.gov/2017011637

Cover image: © KTSDESIGN/SCIENCE PHOTO LIBRARY/Gettyimages

Cover design by Wiley

Contents

Abstract

Preface

Acknowledgments

About the Companion Website

1 Historical Notes

1.1 Introduction
1.2 On the Wings of Dependent Variables
1.3 From Bernoulli to Markov

2 From Observation to Simulation

2.1 Introduction
2.2 Stochastic Matrices
2.3 Transition Probabilities
2.4 The Simulation of a Two-State Markov Chain

3 Building the Stochastic Matrix

3.1 Introduction
3.2 Building a Stochastic Matrix from Events
3.3 Building a Stochastic Matrix from Percentages

4 Predictions Using Two-State Markov Chains

4.1 Introduction
4.2 Performing the Predictions by Using the Stochastic Matrix
4.3 The Steady State of a Markov Chain
4.4 The Long-Run Distribution of a Markov Chain

5 Predictions Using n-State Markov Chains

5.1 Introduction
5.2 Predictions by Using the Three-State Markov Chain
5.3 Predictions by Using the Four-State Markov Chain
5.4 Predictions by Using n-State Markov Chains
5.5 Markov Chain Modeling on Measurements

6 Absorbing Markov Chains

6.1 Introduction
6.2 The Absorbing State

7 The Average Time Spent in Each State

7.1 Introduction
7.2 The Proportion of Balls in the System
7.3 The Average Time Spent in A Particular State
7.4 Exemplification of the Average Time and Proportions

8 Discussions on Different Configurations of Chains

8.1 Introduction
8.2 Examples of Two-State Diagrams
8.3 Examples of Three-State Diagrams
8.4 Examples of Four-State Diagrams
8.5 Examples of State Diagrams Divided into Classes
8.6 Examples of State Diagrams with Absorbing States
8.7 The Gambler's Ruin

9 The Simulation of an n-State Markov Chain

9.1 Introduction
9.2 The Simulation of Behavior
9.3 Simulation of Different Chain Configurations

A Supporting Algorithms in PHP

Supporting algorithm (PHP alternative) 1.
Supporting algorithm (PHP alternative) 2.
Supporting algorithm (PHP alternative) 3.
Supporting algorithm (PHP alternative) 4.
Supporting algorithm (PHP alternative) 5.
Supporting algorithm (PHP alternative) 6.
Supporting algorithm (PHP alternative) 7.
Supporting algorithm (PHP alternative) 8.
Supporting algorithm (PHP alternative) 9.
Supporting algorithm (PHP alternative) 10.
Supporting algorithm (PHP alternative) 11.
Supporting algorithm (PHP alternative) 12.
Supporting algorithm (PHP alternative) 13.
Supporting algorithm (PHP alternative) 14.
Supporting algorithm (PHP alternative) 15.
Supporting algorithm (PHP alternative) 16.
Supporting algorithm (PHP alternative) 17.

B Supporting Algorithms in JavaScript

Supporting algorithm (JS alternative) 1.
Supporting algorithm (JS alternative) 2.
Supporting algorithm (JS alternative) 3.
Supporting algorithm (JS alternative) 4.
Supporting algorithm (JS alternative) 5.
Supporting algorithm (JS alternative) 6.
Supporting algorithm (JS alternative) 7.
Supporting algorithm (JS alternative) 8.
Supporting algorithm (JS alternative) 9.
Supporting algorithm (JS alternative) 10.
Supporting algorithm (JS alternative) 11.
Supporting algorithm (JS alternative) 12.
Supporting algorithm (JS alternative) 13.
Supporting algorithm (JS alternative) 14.
Supporting algorithm (JS alternative) 15.
Supporting algorithm (JS alternative) 16.
Supporting algorithm (JS alternative) 17.

C Syntax Equivalence between Languages

Glossary

References

Index

EULA

List of Illustrations

Figure 1.1 From Bernoulli model to the Markov model. (a) The Bernoulli model with a single jar filled with different proportions of black and white balls. The curved arrows show from which jar the extraction was done and to which jar the next draw will be made. Black curved arrows show the extraction and observation of black balls whereas white curved arrows show the extraction and observation of white balls. (b) Two Bernoulli jars. A white jar and a black jar, each filled with different proportions of black and white balls. Here, draws are still independent from one another. (c–f) Shows how dependence occurs between the two jars if the color of the curved arrows is “attracted” to the color of the jars. (g–j) Shows how the two jars system is transformed into a Markov diagram by changing the angle of viewing of the jars, from the side view to the top view.
Figure 1.2 The two jars seen independently when disconnected from the Markov diagram. (a) The Markov model represented by two jars. (b) The white jar observed independently from the black jar. (c) The black jar observed independently from the white jar. The black arrows signify the transitions to the black jar, and the white arrows signify the transitions to the white jar.

Figure 2.1 From the Markov diagram to the Markov matrix. (a) The Markov diagram. (b–i) Gradual deformation of the Markov diagram arrows until they are taking the form of the matrix cells. (j) The transition matrix, also named the Markov matrix.
Figure 2.2 Types of stochastic matrices. (a) A right stochastic matrix, in which values from rows sum up to 1; (b) a left stochastic matrix, in which values from columns sum up to 1. (c) A doubly stochastic matrix, in which values from both rows and columns sum up to 1.
Figure 2.3 From jars to their representation in electronic format. (a) Linear representation of Jar “W”. (b) Linear representation of Jar “B”. Each jar contains 10 balls of different colors. The balls from each jar are linearly arranged by color in a string (the order does not matter). The string of balls is replaced with a string of letters. Each string of letters is then stored in a vector designated as “Jar”.

Figure 3.1 An overall view for building a transition matrix from known events. Each icon in the sequence of E represents an observation made for an entire day. The transition matrix is schematically illustrated on the right side of the figure. The left side of the figure illustrates the conditional probability functions associated with the matrix.
Figure 3.2 Building a right stochastic matrix. (a) Transition probabilities from events a to events b. (b) Events a are represented by letters from which the transition is made and events b are represented by letters to which the transition is made. (c) Following the examples above, by calculating T_S_→_R the transition probability from “S” to “R” has been found.
Figure 3.3 Filling the unknowns inside the transition matrix. A right stochastic matrix is made from two probability vectors positioned one over the other. Inside the matrices, these probability vectors are viewed independently of each other. (a) Known transitions from a sunny day to a sunny day (P[S|S] = 0.9) and from a rainy day to a rainy day (P[R|R] = 0.5). (b) Known transitions from a sunny day to a rainy day (P[S|R] = 0.2) and from a rainy day to a sunny day (P[R|S] = 0.4). (c) Known transitions from a sunny day to a sunny day (P[S|S] = 0.2) and from a rainy day to a sunny day (P[R|S] = 0.3).

Figure 4.1 The Markov diagram for sequence E = “SRRSRSRRSRSRRSS”.
Figure 4.2 The prediction rules. The initial state vector (v⁽⁰⁾) and the transition matrix (P) are multiplied. The first component (x₁) of the new vector (v⁽¹⁾) is calculated as x₁ = (x₀ × m₁₁) + (y₀ × m₁₂). The second component (y₁) of the new vector (v⁽¹⁾) is calculated as y₁ = (x₀ × m₂₁) + (y₀ × m₂₂).
Figure 4.3 The graphical representation of a Markov chain.
Figure 4.4 The long-run distribution of a two-state Markov chain. (a) The vertical axis represents the probability value of the x component and the horizontal axis represents the probability value of the y component. Each circle has the x and y coordinates dictated by the two components of the probability vector. (b) The convergence path toward the steady-state vector. The vertical axis represents the probability value for both vector components and the horizontal axis represents the long-run behavior of the vector components over 40 steps (k iterations). The red line represents the x component and the blue line represents the y component, (c) the red bar represents the x component and the blue bar represents the y component of the steady-state vector (equilibrium). The vertical axis represents the probability values.

Figure 5.1 A three-state Markov chain. (a) Shows how the three-jar system is equivalent to the (b) Markov diagram representing the weather, by changing the angle of viewing of the jars from the side view to the top view.
Figure 5.2 Markov diagram representing the DNA sequence.
Figure 5.3 From measurements to events. (a) Glycemic values from measurements are plotted on a classic graph in the form of 42 vertical bars. The black dotted line shows the halfway between the upper limit (L_u = 60) and the lower limit (L_d = 200). (b) Shows the same glycemic values plotted as points interconnected with orange lines. Dotted lines represent the thresholds calculated for a diagram with two states (n = 2). The red dotted lines represent the upper limit (L_u) and the lower limit (L_d). Between these dotted lines are the state regions of size Pr(n) corresponding to each state. Each region has an associated letter. Glycemic values entering one or the other region are associated with a letter representative of a state. At the bottom of the chart, the 42 letters shown on the x-axis correspond to the glycemic values plotted above the letters.
Figure 5.4 From measurements to events by using a variable number of states. (a) Shows the glycemic values divided into two state regions of size Pr(n), where n = 2 (uses a two-state diagram). (b) Shows the glycemic values divided into three state regions of size Pr(n), where n = 3 (uses a three-state diagram). (c) Shows the glycemic values divided into four state regions of size Pr(n), where n = 4 (uses a four-state diagram). Dotted lines represent the thresholds calculated for a state diagram. In each case, the red dotted lines represent the upper limit (L_u) and the lower limit (L_d). Between these dotted lines are the state regions of size Pr(n). Depending on the number of states, each region has an associated letter. Glycemic values entering these regions are associated with a letter. Therefore, the letter represents the final observation for a glycemic value. At the bottom of each chart, the 42 letters (x-axis) correspond to the glycemic values plotted above.

Figure 6.1 Absorbing state example. (a) The state diagram of a chain with three states. (b) The matrix lines represent the inside of the orange, blue and gray jars. The matrix columns represent the proportion of balls of different colors, namely orange balls, blue balls, and gray balls.
Figure 6.2 The convergence path of an absorbing Markov chain. (a) Convergence path if the system starts in state “A” (b) Convergence path if the system starts in state “B”.

Figure 7.1 Example of state diagram. (a) The state diagram with associated probabilities. (b) The matrix lines represent the inside of the orange, blue, and gray jars. The matrix columns represent the proportion of balls of different colors over the system.
Figure 7.2 The convergence path of a three-state Markov chain. (a) Convergence path if the system starts in state “A”; (b) the convergence path if the system starts in state “B”; and (c) the convergence path if the system starts in state “C”.

Figure 8.1 The state diagram of case A.
Figure 8.2 The state diagram of case B. (a) The behavior of the system on 25 steps. The orange line represents the probability that the system will be in state “A” while the blue line represents the probability that the system will be in state “B”. (b) The state diagram of case B. The red arrow indicates the state (the jar) from which the first draw begins.
Figure 8.3 The state diagram of case C.
Figure 8.4 The state diagram of case D. (a) The behavior of the system on 50 steps. The orange line represents the probability that the system will be in state “A”. The blue line represents the probability that the system will be in state “B”. The gray line represents the probability that the system will be in state “C”. (b) The state diagram of case D. The red arrow indicates the state (the jar) from which the first draw begins, in this case, state “B”.
Figure 8.5 The state diagram of case E. (a) The behavior of the system on 50 steps. The orange line represents the probability that the system will be in state “A”. The blue line represents the probability that the system will be in state “B”. The gray line represents the probability that the system will be in state “C”. The burgundy line represents the probability that the system will be in state “D”. (b) The state diagram of case E. The red arrow indicates the state (the jar) from which the first draw begins, in this case, state “B”.
Figure 8.6 The state diagram of case F. (a) The behavior of the system on 50 steps. The orange line represents the probability that the system will be in state “A”. The blue line represents the probability that the system will be in state “B”. The gray line represents the probability that the system will be in state “C”. The burgundy line represents the probability that the system will be in state “D”. (b) The state diagram of case F. The red arrow indicates the state (the jar) from which the first draw begins.
Figure 8.7 The state diagram of case G. (a) The behavior of the system on 50 steps. The orange line represents the probability that the system will be in state “A”. The blue line represents the probability that the system will be in state “B”. The gray line represents the probability that the system will be in state “C”. The burgundy line represents the probability that the system will be in state “D”. (b) The state diagram of case G. The red arrow indicates the state from which the first draw begins.
Figure 8.8 The state diagram of case H. (a) The behavior of the system on 50 steps. The orange line represents the probability that the system will be in state “A”. The blue line represents the probability that the system will be in state “B”. The gray line represents the probability that the system will be in state “C”. The burgundy line represents the probability that the system will be in state “D”. (b) The state diagram of case H. The red arrow indicates the state (the jar) from which the first draw begins.
Figure 8.9 The state diagram of case I. (a) The behavior of the system on 50 steps. The orange line represents the probability that the system will be in state “A”. The blue line represents the probability that the system will be in state “B”. The gray line represents the probability that the system will be in state “C”. The burgundy line represents the probability that the system will be in state “D”. (b) The state diagram of case I. The red arrow indicates the state (the jar) from which the first draw begins, in this case, state “A”.
Figure 8.10 The state diagram of case J. (a) The behavior of the system on 25 steps. The orange line represents the probability that the system will be in state “A”. The blue line represents the probability that the system will be in state “B”. The gray line represents the probability that the system will be in state “C”. The burgundy line represents the probability that the system will be in state “D”. (b) The state diagram of case J. The red arrow indicates the state (the jar) from which the first draw begins, in this case, state “A”.
Figure 8.11 The state diagram of case K.
Figure 8.12 The state diagram and the convergence path of case L. (a) The behavior of the system on 50 steps when starting from state “A”. (b) The behavior of the system on 50 steps when starting from state “B”. (c) The behavior of the system on 50 steps when starting from state “C”. In any of the three charts, the orange line represents the probability that the system will be in state “A”. The blue line represents the probability that the system will be in state “B”. The gray line represents the probability that the system will be in state “C”, and the burgundy line represents the probability that the system will be in state “D”. The red arrows indicate the state (the jar) from which the first draw begins.
Figure 8.13 The state diagram and the convergence path for case M. (a) The behavior of the system on 50 steps when starting from state “A”. (b) The behavior of the system on 50 steps when starting from state “B”. The orange line represents the probability that the system will be in state “A”. The blue line represents the probability that the system will be in state “B”. The gray line represents the probability that the system will be in state “C”, and the burgundy line represents the probability that the system will be in state “D”. The red arrows indicate the state (the jar) from which the first draw begins.

Figure 9.1 Example of state diagram. (a) The state diagram of a chain with three states. (b) The matrix lines represent the inside of the orange, blue, and red jars. The matrix columns represent the proportion of balls of different colors, namely orange balls, blue balls, and red balls.
Figure 9.2 Translation of Markov diagrams to jars and balls. Each jar contains 27 balls of different colors. Each graph is showing the proportion of balls in the above jar. The orange Jar “A” contains an equal proportion of balls of each color (33%). The blue Jar “B” contains 50% blue balls and 50% red balls. The red Jar “C” contains in exclusivity orange balls.
Figure 9.3 An imbalance of chances. (a) Shows the row of the transition matrix taken into discussion. The row stores the transition probabilities corresponding to jar “B” which translate into two representations: (b) first, by using a short sequence of 11 letters; (c) second, by using a long sequence of 27 letters. (d) Shows the difference of chance between a short sequence of 11 letters and a long sequence of 27 letters. (e) By using prime numbers, the distribution shows the convergence of the proportions of letters to the actual probability values indicated by the transition matrix. The length of the string (L_tot) is presented on the x-axis and the proportion of “B” (the blue line) and “C” letters (the red line) on the y-axis.
Figure 9.4 Translation of jars and balls to strings of letters. Each jar contains 27 balls of different colors. The balls from each jar are linearly arranged by color in a string (the order does not matter). The string of balls is replaced with a string of letters. Each string of letters is then stored in a vector designated as “Jar”.
Figure 9.5 The mixed format of the matrix. The first row of the matrix (or the identity row of the states) is reserved for letters representative of states. The other rows store the transition probabilities. (a)Shows the format of matrix “P” from the algorithm implementation. (b) Shows the coordinates of the matrix “P” elements and how it relates to the implementation.
Figure 9.6 Framework expansion. It shows that matrix frameworks of n states can be used for a wide range of diagram configurations, ranging between 2 and n states. (a) The orange frame shows the transition matrix of a diagram (case A example) of two states used on a matrix framework of four states. (b) In this panel, the orange frame shows the transition matrix of another diagram (case G example) of four states used on a matrix framework of six states.
Figure 9.7 The verification of the output. (a) Initial transition matrix (T1) of the simulator. (b) Transition probabilities between letters of the output presented in the form of a transition matrix (T2).
Figure 9.8 A window into random processes. Shows the behavior of state diagram from case G on 1000 discrete steps. x-axis indicates the letter frequency for each discrete step as follows: frequency of letter “A” is shown by the red line, frequency of letter “B” is shown by the blue line, frequency of letter “C” is shown by the orange line, and the frequency of letter “D” is shown by the black line. The y-axis represents the number of discrete steps made by the system. The two charts from within the distribution show the frequency of each letter for 250 steps and for 450 steps.
Figure 9.9 A window into randomness. The figure shows the overlapping distribution of a series of experiments made on the state diagram of case G. (a) It shows the distribution of a total of 20 separate experiments on 10,000 discrete steps, (b) shows an enlarged distribution of a distinct set of 20 experiments made on 1000 discrete steps. In both graphs, the frequency of letter “A” is shown by a red line, the frequency of letter “B” is shown by the blue line, the frequency of letter “C” is shown by the orange line, and the frequency of letter “D” is shown by the black line.

From Theory to Implementation and Experimentation