🙏🏼 Make a donation to support our mission of creating resources to help anyone learn the basics of AI. Donate !

# Markov chain

### the tl;dr

A Markov chain is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.

## What is a Markov chain?

A Markov chain is a model used to predict the future state of a system based on its current state. The model is named after Andrey Markov, who first proposed it in the early 1900s.

The Markov chain model is based on the assumption that the future state of a system can be predicted from its current state. This assumption is reasonable for many systems, such as weather patterns, stock prices, and traffic flow.

The Markov chain model is a mathematical model that is used to predict the future state of a system based on its current state. The model is named after Andrey Markov, who first proposed it in the early 1900s.

The Markov chain model is based on the assumption that the future state of a system can be predicted from its current state. This assumption is reasonable for many systems, such as weather patterns, stock prices, and traffic flow.

The Markov chain model is a powerful tool for AI applications because it can be used to predict the future state of a system based on its current state. This ability can be used to make decisions in real-time, such as deciding which route to take in a traffic jam, or which stock to buy or sell.

## What is the order of a Markov chain?

In a Markov chain, the order is the number of previous states that the current state depends on. For example, in a first-order Markov chain, the current state only depends on the previous state; in a second-order Markov chain, the current state depends on the two previous states; and so on.

## What is a stationary distribution?

In AI, a stationary distribution is a probability distribution that does not change over time. This is in contrast to a non-stationary distribution, which does change over time. Stationary distributions are important in many settings, including reinforcement learning and Markov decision processes.

## What is a transition matrix?

A transition matrix is a mathematical representation of the probabilities of moving from one state to another in a Markov chain. In a Markov chain, the next state is determined solely by the current state, without regard for the previous states. This is in contrast to a Markov process, which takes into account all previous states.

The transition matrix is used to predict the future state of a system, given the current state. For example, if the current state is A and the transition matrix is:

A B

A 0.7 0.3

B 0.6 0.4

Then the probability of being in state A at the next time step is 0.7, and the probability of being in state B is 0.3.

The transition matrix can also be used to calculate the steady-state probabilities of a system, which is the probability of being in each state, given that the system has been in operation for a long time. For example, if the transition matrix is:

A B

A 0.7 0.3

B 0.6 0.4

Then the steady-state probability of being in state A is:

P(A) = 0.7P(A) + 0.3P(B)

P(A) = 0.7P(A) + 0.3(0.7P(A) + 0.4P(B))

P(A) = 0.7P(A) + 0.21P(A) + 0.12P(B)

P(A) = 0.93P(A) + 0.12P(B)

P(A) = 0.93P(A) + 0.12(0.6P(A) + 0.4P(B))

P(A) = 0.93P(A) + 0.048P(A) + 0.048P(B)

P(A) = 0.978P(A) + 0.048P(B)

P(A) = 0.978P(A) + 0.048(0.93P(A) + 0.12P(B))

P(A) = 0.978P(A) + 0.0448P(A) + 0.00576P(B)

P(A) = 0.99258P(A) + 0.00576P(B)

P(A) = 0.99258P(A) + 0.00576(0.978P(A) + 0.048P(B))

P(A) = 0.99258P(A) + 0.0057024P(A) + 0.0027648P(B)

P(A) = 0.9978832P(A) + 0.0027648P(B)

P(A) = 0.9978832P(A) + 0.0027648(0.99258P(A) + 0.00576P(B))

P(A) = 0.9978832P(A) + 0.002720896P(A) + 0.001548288P(B)

P(A) = 0.999914176P(A) + 0.001548288P(B)

P(A) = 0.999914176P(A) + 0.001548288(0.9978832P(A) + 0.0027648P(B))

P(A) = 0.999914176P(A) + 0.001540692224P(A) + 0.00041943040P(B)

P(A) = 0.9999985798624P(A) + 0.00041943040P(B)

P(A) = 0.9999985798624P(A) + 0.00041943040(0.999914176P(A) + 0.001548288P(B))

P(A) = 0.9999985798624P(A) + 0.0004188147968P(A) + 0.000023124864P(B)

P(A) = 0.999999998099456P(A) + 0.000023124864P(B)

P(A) = 0.999999998099456P(A) + 0.000023124864(0.99999857986

## What is the Chapman-Kolmogorov equation?

The Chapman-Kolmogorov equation is a fundamental equation in the theory of Markov processes. It states that the probability of a transition from one state to another state in a Markov process is equal to the sum of the probabilities of all the possible paths from the initial state to the final state.

## What is the transition matrix of a Markov chain?

In a Markov chain, the transition matrix is the matrix that describes the probabilities of moving from one state to another. In other words, it tells you how likely it is that a certain event will happen given that another event has already happened.

For example, let's say we have a Markov chain with two states: A and B. We can represent this using a transition matrix:

A B

A 0.5 0.5

B 0.7 0.3

This transition matrix tells us that there is a 50% chance of staying in state A and a 50% chance of transitioning to state B. Similarly, there is a 70% chance of staying in state B and a 30% chance of transitioning back to state A.

Now, let's say we want to know the probability of being in state B after two steps. We can use the transition matrix to calculate this:

B

A 0.5

B 0.7

This tells us that there is a 35% chance of being in state B after two steps.

The transition matrix is a powerful tool that can be used to calculate the probabilities of various events in a Markov chain.

## What is the stationary distribution of a Markov chain?

The stationary distribution of a Markov chain is a probability distribution that is invariant under the Markov chain's transition probabilities. In other words, it is a distribution that does not change over time.

The stationary distribution can be thought of as the long-term behavior of the Markov chain. If the chain is in a state with a high stationary distribution, then it is more likely to stay in that state. Conversely, if the chain is in a state with a low stationary distribution, then it is more likely to move to a different state.

The stationary distribution is important in AI because it can be used to determine the behavior of a Markov decision process (MDP). An MDP is a model of decision making in which an agent must choose an action at each time step in order to maximize some reward. The agent's choices are based on the current state of the environment, which is represented by a Markov chain.

The stationary distribution of the Markov chain can be used to calculate the expected reward of each state. This is important because it allows the agent to choose the action that will lead to the highest expected reward.

## What is the absorption probability of a Markov chain?

In a Markov chain, the absorption probability is the probability that the chain will eventually reach an absorbing state, where it will remain forever. The absorption probability of a Markov chain is therefore the probability that the chain will eventually reach a state from which there is no way to escape.