What is a Markov chain?

What is a Markov chain?

A Markov chain is a stochastic model that describes a sequence of possible events, where the probability of each event depends only on the state attained in the previous event. This property, known as memorylessness or the Markov property, is what distinguishes a Markov chain from a general stochastic process.

Markov chains can be categorized into two types based on the nature of time: discrete-time Markov chains (DTMCs) and continuous-time Markov chains (CTMCs). In a DTMC, the changes in states are considered at discrete time steps, while in a CTMC, the state changes can occur at any time.

The state space of a Markov chain, which is the set of all possible states, can be anything: letters, numbers, weather conditions, baseball scores, or stock performances. The transition from one state to another is governed by a transition matrix, which represents the probability distribution of the state's transitions. The sum of probabilities in each row of the matrix will be one, implying that this is a stochastic matrix.

Markov chains have a wide range of applications in various fields. They are used in statistical models of real-world processes, such as studying cruise control systems in motor vehicles, queues or lines of customers arriving at an airport, currency exchange rates, and animal population dynamics. They are also the basis for general stochastic simulation methods known as Markov chain Monte Carlo, which are used for simulating sampling from complex probability distributions. Early text-prediction systems in natural language processing also relied on Markov chains, though modern predictive text and autocomplete features have largely moved to neural language models.

The concept of Markov chains is attributed to the Russian mathematician Andrey Markov, who pioneered this field of probability theory. Markov chains were first introduced in his 1906 paper, which studied the stochastic processes that involve sequences of random events or states that are not independent of each other. His work laid the foundation for a new branch of probability theory that focuses on the properties of systems that undergo transitions from one state to another in a chain-like fashion.

Key features of Markov chains

• Discrete and Continuous Time — Markov chains can be defined in discrete or continuous time, with the latter being called a continuous-time Markov chain (CTMC).

• Finite or Countably Infinite State Space — The state space, or set of all possible states, can be finite or countably infinite.

• Transition Probability Matrix — The transition probability matrix, denoted as "P," represents the probability distribution of state transitions. The sum of probabilities in each row of the matrix is one, implying that this is a stochastic matrix.

Markov chains are widely used in various fields, including game theory, queueing theory, genetics, and finance, and are particularly useful in statistical and information-theoretical contexts.

What is the order of a Markov chain?

The order of a Markov chain refers to the number of preceding states that influence the probability of a given state in a stochastic process. Order is not limited to a fixed set of categories — it is a continuum, and a chain can in principle be extended to any order:

• First-order Markov chain — The probability of a state depends only on the immediately preceding state. The transition probability is represented as $$P(x_i | x_{i-1})$$.

• Second-order Markov chain — The probability of a state depends on the two preceding states, with the transition probability represented as $$P(x_i | x_{i-1}, x_{i-2})$$. Chains of order three and higher extend this pattern by conditioning on additional preceding states.

• Variable-order Markov model (VOM) — Rather than a specific higher order, a VOM is a distinct modeling approach that lets the number of conditioning states vary depending on the context, using fewer conditional probabilities than a fixed higher-order chain would require.

In practical settings, there is often insufficient data to accurately estimate the order of a Markov chain. Understanding the order is still useful, since higher-order chains can capture more complex, longer-range dependencies, while first-order chains tend to produce simpler and more repetitive sequences.

What is a stationary distribution?

A stationary distribution is a special distribution for a Markov chain, such that if the chain starts with its stationary distribution, the marginal distribution of all states at any time will always be the stationary distribution. In other words, the distribution remains the same even after a long time. This concept is crucial in understanding the long-term behavior of Markov chains.

Key points about stationary distributions include:

• They exist when the Markov chain is irreducible and positive recurrent.
• The stationary distribution is unique if it exists.
• Finding a stationary distribution involves solving the system of equations given by the transition matrix.

For example, consider a two-state Markov chain with transition probabilities pᵢⱼ. The stationary distribution π can be found by solving the system of equations πⱼ = Σᵢ∈S πᵢpᵢⱼ, which can be rewritten as π = πP.

A stationary distribution is a key concept in Markov chain theory, representing the long-term behavior of the chain. It is unique and can be found by solving the appropriate system of equations.

What is a transition matrix?

A transition matrix, also known as a stochastic or probability matrix, is a square (n x n) matrix representing the transition probabilities of a Markov chain, usually denoted as P = (p_ij). Each entry p_ij is a nonnegative real number giving the probability of transitioning from state i to state j: the row represents the initial state, and the column represents the state it transitions to. The sum of probabilities in each row must equal one, which is why the matrix is described as stochastic.

Some properties of the transition matrix include:

• The matrix is a right stochastic matrix, meaning that the product of two right stochastic matrices is also right stochastic.
• The k-th power of a right stochastic matrix is also right stochastic, and the probability of transitioning from i to j in k steps is given by the (i, j)-th element of the k-th power of the matrix.

Transition matrices are used in various contexts, such as linear algebra, control theory, and Markov chain theory. By examining the probabilities of transitioning between states, they let us describe a system's stability and long-term behavior, and make predictions about its future states.

What is the Chapman-Kolmogorov equation?

The Chapman-Kolmogorov equation (CKE) is a mathematical identity in the field of Markovian stochastic processes that relates the joint probability distributions of different sets of coordinates on a stochastic process. It is named after British mathematician Sydney Chapman and Russian mathematician Andrey Nikolaevich Kolmogorov. The CKE is used in various applications, including Variational Bayesian methods.

The Chapman-Kolmogorov equation is particularly useful in understanding the behavior of Markov chains and their applications in various fields, such as probability theory, statistics, and machine learning.

What is the absorption probability of a Markov chain?

The absorption probability of a Markov chain is the probability of eventually reaching an absorbing state, given that the process starts in a particular state. In an absorbing Markov chain, there is at least one absorbing state, and any state can reach this absorbing state.

The absorption probability of a Markov chain is an important concept in probability theory, particularly in the context of absorbing Markov chains. It represents the probability of eventually reaching an absorbing state, given the initial state of the process.