## Markov Chain Modeling

### Discrete-Time Markov Chain Object Framework Overview

The `dtmc`

object framework provides basic tools for modeling and analyzing discrete-time Markov chains. The object supports chains with a finite number of states that evolve in discrete time with a time-homogeneous transition structure.

`dtmc`

identifies each Markov chain with a `NumStates`

-by-`NumStates`

transition matrix *P*, independent of initial state *x*_{0} or initial distribution of states *π*_{0}. You can specify *P* as either a right-stochastic matrix or a matrix of empirical counts.

As a right-stochastic matrix:

*P*is the nonnegative probability of a transition from state_{ij}*i*to state*j*.Each row of

*P*sums to 1.$${\pi}_{t+1}={\pi}_{t}P$$ describes the evolution of the state distribution from time

*t*to time*t*+ 1.

The state distribution at time

*t*,*π*is a row vector of length_{t}`NumStates`

.As a matrix of empirical counts,

*P*is the observed number of times state_{ij}*i*transitions to state*j*. The`dtmc`

object normalizes the rows of*P*so that it is a right-stochastic matrix.

The `mcmix`

function is an alternate Markov chain object creator; it generates a chain with a specified zero pattern and random transition probabilities. `mcmix`

is well suited for creating chains with different mixing times for testing purposes.

To visualize the directed graph, or digraph, associated with a chain, use the `graphplot`

object function. `graphplot`

is similar to the `plot`

object function of a MATLAB^{®}
`digraph`

object, but it includes additional functionality for analyzing Markov chain structure. Parameter settings highlight communicating classes (that is, *strongly connected* components of the digraph) and specific characteristics affecting convergence, such as recurrence, transience, and periodicity. You can highlight transition probabilities in *P* by coloring the graph edges using heatmap intensities.

To visualize large-scale structure in the chain, `graphplot`

can condense communicating classes to representative nodes. This option is based on the `condensation`

object function of a `digraph`

object.

The `classify`

object function is a numerical analog of class highlighting in the graph. `classify`

returns characteristics of the communicating classes that determine limiting behavior. State classification combines graph-theoretic algorithms, such as the `bfsearch`

(breadth-first search) object function of a MATLAB
`graph`

object, but with more direct matrix computations specific to Markov chain theory. The `subchain`

method allows you to extract specific communicating classes from the chain for further analysis.

The `isreducible`

and `isergodic`

object functions give concise summaries of chain structure. Together, they provide necessary and sufficient conditions for the existence of a unique limiting distribution $${\pi}^{\ast}$$, where $${\pi}^{\ast}={\pi}^{\ast}P$$ and $${\pi}_{0}\to {\pi}^{\ast}$$ for every initial distribution *π*_{0}. The `asymptotics`

object function computes $${\pi}^{\ast}$$, if it exists, and estimates the mixing time using eigenvalue analysis. The `eigplot`

object function plots the eigenvalues of *P*. This figure shows an example of an eigenvalue plot returned by `eigplot`

.

One obstacle to convergence is periodicity. The `lazy`

object function eliminates periodicity by adjusting state inertia (that is, by weighting the diagonal elements of *P*) to produce specified amounts of “laziness” in the chain. Limiting distributions are unaffected by these transformations.

The `simulate`

and `redistribute`

object functions provide realizations of the process as it evolves from a specified initial state or distribution. The `simplot`

and `distplot`

object functions provide various visualizations. This figure is an example of a distribution plot showing the evolution of the state distribution starting from a uniform initial state distribution.

### Markov Chain Analysis Workflow

You can start building a Markov chain model object in two ways:

Identify pertinent discrete states in a process, and then estimate transition probabilities among them. In the simplest case, theory suggests chain structure and the transition matrix

*P*. In this situation, you are interested primarily in how the theory plays out in practice—something that is not always obvious from theory. Once you know*P*, create a Markov chain object by passing*P*to`dtmc`

, which implements a theoretical chain.If you have less specific information on a process, then you must experiment with various numbers of states and feasible transition patterns to reproduce empirical results. The

`mcmix`

function provides insight into the skeletal structure of a chain, which can capture essential features in the data. Through an iterative process, you can adjust the randomly generated transition matrix*P*to suit modeling goals.

For an econometric model builder, the most important consequence of the choice of *P* is the asymptotic behavior of the chain. To understand this behavior, identify and separate the transient states (those states whose return-time probabilities go to zero asymptotically) from the recurrent states (those states whose return-time probabilities go to one asymptotically). Transience and recurrence are properties shared by all states in a communicating class. To determine visually whether states are transient or recurrent, pass the Markov chain object to the `graphplot`

object function and specify `'ColorNodes',true`

. Alternatively, the outputs of the `classify`

object function provide numerical tools for evaluation. This figure is an example of a digraph with classified nodes.

The condensed view of the digraph simplifies this evaluation by consolidating each communicating class into a “supernode.” In the condensed graph, you can easily recognize transience and recurrence by the out degree of the supernode (an out degree greater than 0 implies transience). *Irreducible chains* consist of a single, necessarily recurrent, communicating class. *Unichains* consist of a single recurrent class and any number of satellite transient classes. Unichains maintain the desirable limiting behavior of an irreducible chain. Consideration of the condensed graph is often a precursor to trimming a chain of irrelevant transient states. The `subchain`

function trims chains of transient classes. This figure is the condensed view of the digraph in the previous figure.

The two principle obstacles to uniform limiting behavior are:

*Reducibility*, the existence of more than one communicating class*Periodicity*, the tendency to cycle among subclasses within a single class

A combination of the `graphplot`

and `classify`

object functions can identify these issues. If a chain is reducible and not a unichain, it is common to split the analysis among the independent recurrent classes or reformulate the chain altogether. If a chain is periodic (that is, it contains a periodic recurrent class), but the overall structure captures the essential details of an application, the `lazy`

object function provides a remedy. Lazy chains perturb the diagonal elements of *P* to eliminate periodicity, leaving asymptotics unaffected.

The `isreducible`

and `isergodic`

object functions summarize state classification. Every chain has a *stationary distribution*
$${\pi}^{\ast}$$, where $${\pi}^{\ast}={\pi}^{\ast}P$$, as a result of *P* being stochastic and having an eigenvalue of one. If the chain is irreducible, the stationary distribution is unique. However, irreducibility, while sufficient, is not a necessary condition for uniqueness. Unichains also lead to a unique stationary distribution having zero probability mass in the transient states. In this regard, state classification analysis is essential because `isreducible`

returns `true`

only if the chain as a whole consists of a single communicating class. `isreducible`

returns `false`

for arbitrary unichains, in which case you must decide whether transient classes are a relevant part of the model.

*Ergodicity*, or *primitivity*, is the combination of irreducibility and aperiodicity. An ergodic chain has a unique limiting distribution, that is, *π*_{0} converges to $${\pi}^{\ast}$$ for every initial distribution *π*_{0}. You can determine whether the chain, as a whole, is ergodic by using `isergodic`

. The function identifies ergodic unichains by evaluating the sole recurrent class. A chain is periodic if it is irreducible and not ergodic, that is, if `~tfirreduc`

+ `~tfergo`

= `false`

, where `tfirreduc`

and `tfergo`

are returned by `isreducible`

and `isergodic`

, respectively.

Once you have confirmed that a chain is ergodic, you can determine the unique limiting distribution by using the `asymptotics`

object function. `asymptotics`

returns the limiting distribution $${\pi}^{\ast}$$ and an estimate of the mixing time, which is a time constant for the decay of transient behavior. The Perron-Frobenius theorem for irreducible nonnegative matrices (see [1]) is useful for interpreting these results. Any stochastic matrix has a spectral radius of one. Periodic matrices, of period *k*, have *k* eigenvalues distributed uniformly around the unit circle at the *k* roots of unity. The magnitude of the largest eigenvalue inside the unit circle determines the decay rate of transient states. The `eigplot`

object function provides quick visualization of this information. This figure is an eigenvalue plot of a Markov chain with a period of three.

Regardless of the asymptotic properties of the chain, you can study its mixing rate by applying finite-step analysis. The `hitprob`

and `hittime`

functions return hitting probabilities and expected first hitting times for a subset of target states, beginning from each state in the chain. Both functions optionally plot a digraph with node colors specifying the hitting probabilities or times. This figure shows an example of a digraph with node colors specifying the expected first hitting times. The digraph also indicates whether the beginning states are remote for the target.

Simulation and redistribution allow you to generate statistical information on the chain that is difficult to derive directly from the theory. The `simulate`

and `simplot`

object functions, and the `redistribute`

and `distplot`

object functions, provide computational and graphical tools for such analyses. `simulate`

, for example, generates independent random walks through the chain. As with `simulate`

and object functions elsewhere in Econometrics Toolbox™, ensemble averages of dependent statistics play an important role in forecasting. The corresponding `simplot`

object function offers several approaches to visualization. This figure displays the proportion of states visited after 100 random walks of length 10 steps through the periodic Markov chain in the previous figure.

## References

[1] Horn, R., and C. R.
Johnson. *Matrix Analysis.* Cambridge, UK: Cambridge University Press,
1985.

## See Also

### Objects

### Functions

`mcmix`

|`graphplot`

|`condensation`

|`bfsearch`