core

This file contains some useful objects for handling a finite-state discrete-time Markov chain.

Definitions and Some Basic Facts about Markov Chains

Let \(\{X_t\}\) be a Markov chain represented by an \(n \times n\) stochastic matrix \(P\). State \(i\) has access to state \(j\), denoted \(i \to j\), if \(i = j\) or \(P^k[i, j] > 0\) for some \(k = 1, 2, \ldots\); \(i\) and j communicate, denoted \(i \leftrightarrow j\), if \(i \to j\) and \(j \to i\). The binary relation \(\leftrightarrow\) is an equivalent relation. A communication class of the Markov chain \(\{X_t\}\), or of the stochastic matrix \(P\), is an equivalent class of \(\leftrightarrow\). Equivalently, a communication class is a strongly connected component (SCC) in the associated directed graph \(\Gamma(P)\), a directed graph with \(n\) nodes where there is an edge from \(i\) to \(j\) if and only if \(P[i, j] > 0\). The Markov chain, or the stochastic matrix, is irreducible if it admits only one communication class, or equivalently, if \(\Gamma(P)\) is strongly connected.

A state \(i\) is recurrent if \(i \to j\) implies \(j \to i\); it is transient if it is not recurrent. For any \(i, j\) contained in a communication class, \(i\) is recurrent if and only if \(j\) is recurrent. Therefore, recurrence is a property of a communication class. Thus, a communication class is a recurrent class if it contains a recurrent state. Equivalently, a recurrent class is a SCC that corresponds to a sink node in the condensation of the directed graph \(\Gamma(P)\), where the condensation of \(\Gamma(P)\) is a directed graph in which each SCC is replaced with a single node and there is an edge from one SCC \(C\) to another SCC \(C'\) if \(C \neq C'\) and there is an edge from some node in \(C\) to some node in \(C'\). A recurrent class is also called a closed communication class. The condensation is acyclic, so that there exists at least one recurrent class.

For example, if the entries of \(P\) are all strictly positive, then the whole state space is a communication class as well as a recurrent class. (More generally, if there is only one communication class, then it is a recurrent class.) As another example, consider the stochastic matrix \(P = [[1, 0], [0,5, 0.5]]\). This has two communication classes, \(\{0\}\) and \(\{1\}\), and \(\{0\}\) is the only recurrent class.

A stationary distribution of the Markov chain \(\{X_t\}\), or of the stochastic matrix \(P\), is a nonnegative vector \(x\) such that \(x' P = x'\) and \(x' \mathbf{1} = 1\), where \(\mathbf{1}\) is the vector of ones. The Markov chain has a unique stationary distribution if and only if it has a unique recurrent class. More generally, each recurrent class has a unique stationary distribution whose support equals that recurrent class. The set of all stationary distributions is given by the convex hull of these unique stationary distributions for the recurrent classes.

A natural number \(d\) is the period of state \(i\) if it is the greatest common divisor of all \(k\)’s such that \(P^k[i, i] > 0\); equivalently, it is the GCD of the lengths of the cycles in \(\Gamma(P)\) passing through \(i\). For any \(i, j\) contained in a communication class, \(i\) has period \(d\) if and only if \(j\) has period \(d\). The period of an irreducible Markov chain (or of an irreducible stochastic matrix) is the period of any state. We define the period of a general (not necessarily irreducible) Markov chain to be the least common multiple of the periods of its recurrent classes, where the period of a recurrent class is the period of any state in that class. A Markov chain is aperiodic if its period is one. A Markov chain is irreducible and aperiodic if and only if it is uniformly ergodic, i.e., there exists some \(m\) such that \(P^m[i, j] > 0\) for all \(i, j\) (in this case, \(P\) is also called primitive).

Suppose that an irreducible Markov chain has period \(d\). Fix any state, say state \(0\). For each \(m = 0, \ldots, d-1\), let \(S_m\) be the set of states \(i\) such that \(P^{kd+m}[0, i] > 0\) for some \(k\). These sets \(S_0, \ldots, S_{d-1}\) constitute a partition of the state space and are called the cyclic classes. For each \(S_m\) and each \(i \in S_m\), we have \(\sum_{j \in S_{m+1}} P[i, j] = 1\), where \(S_d = S_0\).

class quantecon.markov.core.MarkovChain(P, state_values=None)

Bases: object

Class for a finite-state discrete-time Markov chain. It stores useful information such as the stationary distributions, and communication, recurrent, and cyclic classes, and allows simulation of state transitions.

Parameters:

Parray_like or scipy sparse matrix (float, ndim=2)

The transition matrix. Must be of shape n x n.

state_valuesarray_like(default=None)

Array_like of length n containing the values associated with the states, which must be homogeneous in type. If None, the values default to integers 0 through n-1.

Notes

In computing stationary distributions, if the input matrix is a sparse matrix, internally it is converted to a dense matrix.

Attributes:

Pndarray or scipy.sparse.csr_matrix (float, ndim=2)

See Parameters

stationary_distributionsarray_like(float, ndim=2)

Array containing stationary distributions, one for each recurrent class, as rows.

is_irreduciblebool

Indicate whether the Markov chain is irreducible.

num_communication_classesint

The number of the communication classes.

communication_classes_indiceslist(ndarray(int))

List of numpy arrays containing the indices of the communication classes.

communication_classeslist(ndarray)

List of numpy arrays containing the communication classes, where the states are annotated with their values (if state_values is not None).

num_recurrent_classesint

The number of the recurrent classes.

recurrent_classes_indiceslist(ndarray(int))

List of numpy arrays containing the indices of the recurrent classes.

recurrent_classeslist(ndarray)

List of numpy arrays containing the recurrent classes, where the states are annotated with their values (if state_values is not None).

is_aperiodicbool

Indicate whether the Markov chain is aperiodic.

periodint

The period of the Markov chain.

cyclic_classes_indiceslist(ndarray(int))

List of numpy arrays containing the indices of the cyclic classes. Defined only when the Markov chain is irreducible.

cyclic_classeslist(ndarray)

List of numpy arrays containing the cyclic classes, where the states are annotated with their values (if state_values is not None). Defined only when the Markov chain is irreducible.

Methods

get_index(value)	Return the index (or indices) of the given value (or values) in state_values.
simulate(ts_length[, init, num_reps, ...])	Simulate time series of state transitions, where the states are annotated with their values (if state_values is not None).
simulate_indices(ts_length[, init, ...])	Simulate time series of state transitions, where state indices are returned.

property cdfs

property cdfs1d

property communication_classes

property communication_classes_indices

property cyclic_classes

property cyclic_classes_indices

property digraph

get_index(value)

Return the index (or indices) of the given value (or values) in state_values.

Parameters:

value

Value(s) to get the index (indices) for.

Returns:

idxint or ndarray(int)

Index of value if value is a single state value; array of indices if value is an array_like of state values.

property is_aperiodic

property is_irreducible

property num_communication_classes

property num_recurrent_classes

property period

property recurrent_classes

property recurrent_classes_indices

simulate(ts_length, init=None, num_reps=None, random_state=None)

Simulate time series of state transitions, where the states are annotated with their values (if state_values is not None).

Parameters:

ts_lengthscalar(int)

Length of each simulation.

initscalar or array_like, optional(default=None)

Initial state values(s). If None, the initial state is randomly drawn.

num_repsscalar(int), optional(default=None)

Number of repetitions of simulation.

random_stateint or np.random.RandomState/Generator, optional

Random seed (integer) or np.random.RandomState or Generator instance to set the initial state of the random number generator for reproducibility. If None, a randomly initialized RandomState is used.

Returns:

Xndarray(ndim=1 or 2)

Array containing the sample path(s), of shape (ts_length,) if init is a scalar (integer) or None and num_reps is None; of shape (k, ts_length) otherwise, where k = len(init) if (init, num_reps) = (array, None), k = num_reps if (init, num_reps) = (int or None, int), and k = len(init)*num_reps if (init, num_reps) = (array, int).

simulate_indices(ts_length, init=None, num_reps=None, random_state=None)

Simulate time series of state transitions, where state indices are returned.

Parameters:

ts_lengthscalar(int)

Length of each simulation.

initint or array_like(int, ndim=1), optional

Initial state(s). If None, the initial state is randomly drawn.

num_repsscalar(int), optional(default=None)

Number of repetitions of simulation.

random_stateint or np.random.RandomState/Generator, optional

Random seed (integer) or np.random.RandomState or Generator instance to set the initial state of the random number generator for reproducibility. If None, a randomly initialized RandomState is used.

Returns:

Xndarray(ndim=1 or 2)

Array containing the state values of the sample path(s). See the simulate method for more information.

property state_values

property stationary_distributions

quantecon.markov.core.mc_compute_stationary(P)

Computes stationary distributions of P, one for each recurrent class. Any stationary distribution is written as a convex combination of these distributions.

Returns:

stationary_distsarray_like(float, ndim=2)

Array containing the stationary distributions as its rows.

quantecon.markov.core.mc_sample_path(P, init=0, sample_size=1000, random_state=None)

Generates one sample path from the Markov chain represented by (n x n) transition matrix P on state space S = {{0,…,n-1}}.

Parameters:

Parray_like(float, ndim=2)

A Markov transition matrix.

initarray_like(float ndim=1) or scalar(int), optional(default=0)

If init is an array_like, then it is treated as the initial distribution across states. If init is a scalar, then it treated as the deterministic initial state.

sample_sizescalar(int), optional(default=1000)

The length of the sample path.

random_stateint or np.random.RandomState/Generator, optional

Random seed (integer) or np.random.RandomState or Generator instance to set the initial state of the random number generator for reproducibility. If None, a randomly initialized RandomState is used.

Returns:

Xarray_like(int, ndim=1)

The simulation of states.