# 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)[source]

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)[source]

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)[source]

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)[source]

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)[source]

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)[source]

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.