The objective of this section is to present one of the main tools of applied probability---Markov chains, also known as Markov processes. They are named in honor of the Russian mathematician Andrey (Andrei) Andreyevich Markov (1856 -- 1922), a student of P. Chebyshev. We consider a very important version of a discrete stochastic process that can be in one of a finite number of states---similarly to definition of a finite state automaton. Markov chains give a universal approach to the problems considered in the previous section. Because of its generality, computational tractability, and adequate representation of problems in applications, the Markov chains have become an important part of almost every course in probability or operations research.

Markov Chains

14

Subsection: Histprical Notes

 Often we are given the information that a particular event A has occurred, in which case the probability of occurrence of another event B will be effected. This gives rise to the concept of the conditional probability of the event A given that B has occurred, which is denoted by \( \Pr [A\,|\,B] \) and defined as

provided that \( \Pr [B] \ne 0. \)

Stochastic process is a process in which changing of the system from one state to another is not predetermined but can only be specified in terms of certain probabilities which are obtained from the past behavior or history of the system.

We now are going to define a first-order Markov process or a Markov Chain as a stochastic process where the transition probability of a state depends exclusively on its immediately preceding state. A more explicit definition can be given as follows.

 Markov chains have many applications as statistical models of real-world processes, such as studying cruise control systems in motor vehicles, queues or lines of customers arriving at an airport, exchange rates of currencies, storage systems such as dams, and population growths of certain animal species. The algorithm known as PageRank, which was originally proposed for the internet search engine Google, is based on a Markov process. Furthermore, Markov processes are the basis for general stochastic simulation methods known as Gibbs sampling and Markov Chain Monte Carlo, are used for simulating random objects with specific probability distributions, and have found extensive application in Bayesian statistics.

To understand a system described by a Markov process or a Markov chain the following concepts are necessary.

Note that in probability theory, it is customary to consider row-vectors in opposite to engineering where vecors are column-verctors.

If a discrete dynamical system v_{t + 1} = T v_t is such that T has an eigenvalue of 1, then something interesting happens. If v_t happens to be an eigenvector for the eigenvalue 1, then

If T is a regular probability matrix, then the state v_t of the system is ever an eigenvector for the eigenvalue 1, then the system will stay in that state forever: This unique probability vector is also called as a steady state vector (also known as a stationary distribution). A common occurrence is when matrix T is diagonalizable, has the eigenvalue 1 and when every other eigenvalue of T satisfies | λ | < 1. In this case, the long-term behaviour of the system will be to converge to a steady state.

    Example 1: Ehrenfest model of diffusion     Example 2: Two state Markov chain     Example 3: Election simulation     Example 4: ????     Example 6: Mathematica helps

This definition is naturally extended to countable number of states. The Markovian property just assures us that it is memoryless: transition from a state v_t to v_t+1 does not depend on how the system arrives to the state v_t. It is convenient and does not lose any generality to assume that finite state space of the Markov chain is { 0, 1, 2, … , n }, which is customarily denoted as [0..n] (from Maple).

To make our exposition clear and succinct, we use matrix notations. First, we distinguish between vectors and matrices, denoted by upper case letters in bold font. We use lower case letters to denote vectors: column-vectors are written in bold font whereas row-vectors are identified by putting arrows above the letters. For instance, \( \displaystyle \quad \vec{a} = \langle a_1 , a_2 , \ldots , a_n \rangle \quad \) is a row-vector, but its transposition, \( \displaystyle \quad \vec{a}^{\mathrm T}, \ \) which is a column-vector, will be denoted by a letter in bold font. However, it will be clear from exposition when we use row vecors or column vectors, which gives us a power to use the same letter for both.

Let p_ij be the probability of transition from state i to state j in one time step. The square matrix P = [ p_ij ] is called the transition probability matrix or simply transition matrix. It has stochastic property that the sum of entries in every row is 1. For m > 0, let \( \displaystyle \quad p_{ij}^{(m)} \stackrel{\tiny def}{=} \Pr [\,X_{t+m} = j \mid X_t = i \,] \quad \) be the conditional probability that the system will be in state j after exactly m time steps, given that it starts in state i at time t. When m = 1, p⁽¹⁾_ij = p_ij. The corresponding matrix P^(m) = [ p^(m)_ij ] is expressed as P^(m) = P P^(m-1). So by induction, we get P^(m) = P^m. Therefore, the probability of passing from state i to j in m steps (without specifying the intermediate states) is given by raising P to the power m and picking the corresponding element: p^(m)_ij. The following Chapman-Kolmogorov equations provide a method for computing these m-step transition probabilities:

    Example 5: ????

Let p_i(t) denote the probability that the process is at state i at time t, then (n+1)-tuple, \( \displaystyle \quad \vec{p} (t) =\langle p_0 (t), p_1 (t), p_2 (t), \ldots, p_n (t) \rangle ,\ \) is the row vector giving the distribution of the chain at time t. Summing over all possible intermediate states at time t−1, we get This relation allows us to express the probability distribution at (integer) time t via the initial distribution \( \displaystyle \quad \vec{\pi}_0 : \)

    Example 6: ????

We bring some terminology and basic results from the general theory of Markov chains. A good compact treatment of Markov chains is in books of Feller [Chapter XV], Ross [Chapter IV], and Mitzenmacher & Upfal, where the reader can find many examples of problems solved with Markov chains.

Since the communication relation is an equivalence relation (that is, it is reflexive, symmetric, and transitive), all states may be partitioned into one or more disjoint classes such that those states that communicate with each other are in the same class. It might exist a transition from one class to another one, but it is impossible to return to the previous class. This is entirely analogous to viewing the graphical description of the chain as a directed graph, and finding its strongly-connected components.     Example 7: ????

A state is recurrent if the chain with probability 1 visits this state. This means that the chain visits a recurrent state infinitely many times. On the other hand, if state i is transient, then the time of next visit of state i is a geometric random variable.

    Example 8: ???? Periodicity is a class property, that is, if state i in a communication class has period d, then the all states in that class have period d.     Example 9: ????     If a Markov chain has the only one communication class, then for every pair of indices i,j ∈ [0..n] there exists m = m(i,j) such that p^(m)_i,j > 0. If a chain has no transient states, then no matter where the process starts, after sufficient lapse of time it would be in any state. Therefore, for sufficiently large m, all entries of P^m are strictly positive.

When a Markov chain is reducible having r recurrent classes, R₁, R₂, … , R_r, then its transition matrix can be written in the following canonical form (after, perhaps, reordering the states): \begin{equation} \label{E.markov5} {\bf P} = \left[ \begin{array}{c|c} {\bf Q} & {\bf S} \\ \hline {\bf 0} & \tilde{\bf P} \end{array} \right] , \end{equation} where \( \displaystyle \quad \tilde{\bf P} \ \) is a block-diagonal matrix corresponding to each R_k, k = 1, 2, … , r (the submatrix obtained from considering only the rows and columns for states in R_k).

    Example 10: ????

If the chain has s transient states, then s × s submatrix Q concerns the process as long as it stays in transient states. The matrix Q is a substochastic matrix, that is, a matrix with nonnegative entries whose row sums are less than or equal 1. This implies that all the eigenvalues of Q have absolute values strictly less than 1. Therefore, Q^k → 0 as k → ∞, and I − Q is an invertible matrix, where I denotes the identity s ×. s matrix.

Formula \eqref{E.markov6} follows from the Maclaurin series, for the function \( \displaystyle \quad \frac{1}{1-x} = 1 + x + x^2 + \cdots = \sum_{k\ge 0} x^k . \quad \) Similarly, if a Markov chain has at least one absorbing state, then I − Q is invertible with inverse \( \displaystyle \quad \mathbf{N} = \sum_{k\ge 0} \mathbf{Q}^k . \quad \) The (i,j)-th entry of the fundamental matrix N represents the expected time that the Markov chain stays in state X_j given that it starts in X_i.

The rate of the convergence of series \eqref{E.markov6} is determined by the second-largest (in absolute value) eigenvalue of the matrix Q, which is guaranteed to be less than 1, but could be close. In \eqref{E.markov5}, the matrix \( \displaystyle \quad \tilde{\bf P} \ \) deals with the process after it has reached an ergodic set. The matrix S concerns the transition from transient to ergodic states.

If there are q transient states and r absorbing states, the states of a Markov chain can be renumbered, thus permuting the rows and columns of the transition matrix in order to put the transition matrix into the form

where the q × q matrix Q represents the transition between transient states, the r × r identity matrix I represents absorption, the q × r matrix S represents the transition from a transient state to an absorbing state, and the r × q matrix 0 represents the lack of ability to move from an absorbing state to a transient state.

Recall that we use two forms of transition matrix P in order to please everyone (or no one ?) because some people use matrix multiplication of column vector from left (then it is written in brackets), others perform multiplication of row vectors by a matrix from right (then the transient matrix is written in parethersis). As usual, S^T denoted a transposed matrix to matrix S.

Proof of Theorem 1:     Example 11: ????

Understanding the long-term behavior of a Markov chain boils down to understanding the behavior of P^m for large m values. The crucial role in this issue is played by an invariant probability distribution for the corresponding transition matrix.

Equation \eqref{E.markov3} shows that an invariant probability vector, \( \displaystyle \quad \vec{\pi} = \langle \pi_0 , \pi_1, \ldots , \pi_n \rangle ,\ \) is a left eigenvalue of P corresponding the eigenvalue 1. One way to compute the stationary distribution of a finite Markov chain is to solve the homogeneous system of n+1$ linear equations \eqref{E.markov3}. Since there are n+1 unknowns, the system \( \displaystyle \quad \vec{\pi} =\vec{\pi} \,{\bf P} \ \) has infinite many solutions, but the additional constraint \( \displaystyle \quad \sum_{k=0}^n \pi_k =1\ \) leads to the unique solution.

If a chain ever reaches an equilibrium distribution, then it maintains that distribution for all future time. In particular, a Markov chain with an absorbing state will be in its stationary distribution once it reaches the absorbing state. If k is an absorbing state, and the process starts in state i, the probability of ever going to state k is called the probability of absorption into state k, given that the system started in state i.

It is possible to give a probabilistic interpretation of the elements of the fundamental matrix. Define N_ij to be the number of times the process passes through the transient state j starting at another transient state i till absorption, i,j = 1, 2, … , s. If i = j, the initial sojourn is already counted as one visit. The expected number of steps until the chain enters a recurrent class, assuming that it starts at state i, is the sum \( \displaystyle \quad \sum_j n_{i,j} \ \) over all transient states j.

Proof of Theorem 2:     Example 12: ???? Proof of Theorem 3:     Example 13: ????

The number of transitions made by the process in going from state i to state j for the first time is usually referred to as the first passage time. When i = j, this first passage time is just the number of transitions until the process returns to the initial state. Once it happens, the system recommences the process from scratch, forgetting that it was in the same state before. We denote by r^(m)_i,j the probability that, starting at state i, the first transition to state j occurs at time m: \begin{equation} \label{E.markov2} r^{(m)}_{i,j} = \Pr [\, X_m =j \quad\mbox{and for }\ 1\le k \( \displaystyle \quad r_{i,j} = \sum_{m\ge 1} r^{(m)}_{i,j} \ \) be the probability that, starting from state i, the system ever reaches state j. Then we can claim that state i is recurrent if \( \displaystyle \quad \sum_{m\ge 0} r^{(m)}_{i,i} =1, \quad \) and it is transient if \( \displaystyle \quad \sum_{m\ge 0} r^{(m)}_{i,i} <1. \ \) Whenever \( \displaystyle \quad \sum_{m\ge 0} r^{(m)}_{i,i} =1, \quad \) the expected time to first reach state j from state i, denoted by \( \displaystyle \quad \mu_{i,j} = \sum_{m\ge 1} m\,r^{(m)}_{i,i}, \ \) uniquely satisfies the equation \begin{equation} \label{E.markov9} \mu_{i,j} = 1+ \sum_{k\ne j} p_{i,k} \, \mu_{k,j} . \end{equation} So μ_i,i is the expected time to return to state i. Since we consider only finite Markov chains (with finite number of states), all expected values μ_i,i are finite for all recurrent states, but not for transient ones. A finite Markov chain has at least one recurrent state.

We summarize the properties of stationary distributions in the following statement from the book by Mitzenmacher and Upfa.

Property 3 tells us that the expected number of steps to return to state k, assuming that the chain starts at k, is given by the reciprocal of the kth component of the stationary distribution.

There is a typical way to relate Markov chains to analysis of algorithms. An algorithm starts at some fixed initial state. Then, according to the input, it moves till completion through a finite number of , which we again denote by v_i, i = 0, 1, 2, … , n. A state in this context reflects the values of the variables that the algorithm uses to record the processing that it has performed so far. If a sufficiently large number of states is allowed, we could probably represent in this way any algorithm, but this approach is not really meaningful and effective unless the state space is either small or has a simple structure. Such operation is represented formally as traversal of a directed graph: nodes represent states of the algorithm, edges represent possible transitions. The crucial step in the model formulation is the assignment of probabilities to the edges.

Usually, there are two sources of probabilities in an algorithm. One is induced by the distribution over the input, as would be typically the case in a sorting or searching algorithm. Another scenario arises when the algorithm itself contains a random element, taking action based on sampling a built-in random event generator.

We say that this representation has the Markovian property when the probability that the algorithm goes from a certain state $v_i$ into some other state v_j does not depend on the history of the algorithm execution before it reaches state v_i. It is then equal to the probability assigned to the edge ($i,j$). There are two different mathematical descriptions of such a chain: a directed, labeled graph with weights, and a stochastic matrix of dimensions equal to the number of nodes, with entries that are positive and sum, in each row, to 1.

Definition of a discrete stochastic process is equivalent to saying that the set of states supports a first-order Markov chain, or provides a Markovian description of the algorithm. If the algorithm had in fact a memory of the last two, or some {\em fixed} number of states (say $k$), we would say it is a $k$th-order Markov chain. It is relatively easy to translate any such higher-order chain to a first-order one, at the cost of a significant increase in the size of the state space.

Suppose that the chain has the only one absorbing state, the last one, $v_n$. Since n_i,j is the expected number of visits of the chain in v_j till absorption, starting in state v_i, then summing over the ith row of the fundamental matrix would provide us with d_i, defined as the expected time (counted in state transitions) till absorption, from state v_i. Let us show this by independent calculation, invoking randomization on the first transition: %Randomizing, \begin{equation}\label{E7M.d} d_i =1+\sum_{j=0}^n p_{i,j}d_{j} =1+\sum_{j=0}^{n-1} p_{i,j}d_j =1+\sum_{j=0}^{n-1}{\bf Q}_{i,j}d_j, \quad 0\le i <n. \end{equation} We change the sum above to terminate at n−1 without changing its value, since d_n = 0 is the only value which is meaningful. With our convention that v₀ is the initial state, the first component, d₀, is the expected run-time of the algorithm. Note that \eqref{E7M.d} is identical to \eqref{E923.1}. Using the fundamental n × n matrix, N, we can express the solution of the system of algebraic equations \eqref{E7M.d} in the vector form: \begin{equation}\label{E.markov10} {\bf d} = ({\bf I}-{\bf Q})^{-1}\mathbf{e} ={\bf N}\,\mathbf{e} , \end{equation} where \( \displaystyle \quad \mathbf{d}^{T} = \langle d_0 , d_1 , \ldots , d_{n-1} \rangle\quad \) and \( \displaystyle \quad \mathbf{e}^{T} = \langle 1,1,\ldots , 1 \rangle \quad \) are n-dimensional vectors.

=======================================

Example 1 Transition matrix

It is sometimes helpful in a Markov process to visualize the system with a state diagram, where arrows between states representing the transitions and weights representing the probability of that transition. An example of a state diagram corresponding to the transition matrix can be seen in the following igure.

A long-term behavior of the states is given in the following statement provided that a transition matrix is known.

Proof of Theorem 5: Subsection: Exercises

 

References