One where the Future is only dependent on the Present
What are Markov Chains and Steady-State Probabilities
All about Markov chains and steady-state probabilities.
In addition to proving the central limit theorem, Andrey Andreyevich Markov played a pivotal role in developing Markov chains. Markov chains are used to model discrete-time, discrete space random processes with applications across multiple domains including Finance, Advertising, NLP, SEO, Physics, etc. In this blog post, we shall discuss the in and outs of Markov Chains with a specific focus on computing the steady-state probabilities for a given Markov chain.
Recap:
Before we jump into the nitty-gritty of the Markov chain, let us take a moment to define the fundamental concepts of probability theory.
- Random Variable:
- A Random variable is a variable whose outcome is dependent on a random phenomenon. For example, a coin flip or temperatures throughout the year.
- A continuous random variable is one that can take an infinite number of possible values. Temperatures throughout are year can take infinite values within a range and can be considered as a continuous random variable.
- A discrete random variable is one that can take a finite number of possible values.
- For example, a coin flip can result in heads or tails, and hence it is an example of a discrete random variable.
2. Random Process:
- A Random Process is a collection of random variables. It is usually indexed by time.
- When we have a random process X(t) where t can take real values in an interval on a real line, then X(t) is a continuous-time random process.
- Similarly, a discrete-time random process is a process
Where J is a countable (finite) set.
- A continuous-valued random process is a process where each random variable in the process is a continuous random variable.
- Similarly, a discrete-valued random process is a process where each random variable is a discrete random variable.
Markov Chain:
- A Markov chain is a discrete-time discrete-valued random process that follows that Markov property.
- Mathematically, a Markov chain is denoted as
Where for each time instant n, the process takes a value from a discrete set defined by
- Given a Markov chain, the Markov property states that the probability distribution of the next state (future) depends only on the probability distribution of the current state.
Mathematically,
Lets us consider a simple 2-state Markov chain as follows:
The visual explanation of a Markov Chain by Victor Powell and Lewis Lehe is the best I have come across until now. It can be seen that the Markov chain can transition from a given state to another state (including itself) with a probability of 0.5.
State Space Transition Matrix (AKA Transition Matrix):
- A state-space transition matrix is a n x n square matrix that describes the stochastic behavior of a Markov chain.
- For instance, a 2-state Markov chain can be mathematically expressed using a 2 x 2 transition matrix.
- Consider a Markov chain with states A, B, and C. The Markov chain can transition from one state to another with a certain probability.
- The state-space transition matrix can then be defined by:
State Vector:
- A state vector at any step n is a vector of probabilities of each state that adds up to 1.
Transitioning the Markov Chain:
Given a transition matrix corresponding to a Markov chain and an initial state vector, we can find the state vector at step 1 using the following formula:
Similarly, the probability state vectors for subsequent steps can be found using results from the previous step.
Steady-State Probability:
- A steady-state behavior of a Markov chain is the long-term probability that the system will be in each state.
- In other words, any number of transitions applied to the systems has no impact on the state vector i.e the current behavior of the system will continue into the future.
Mathematically,
Finding the Steady State Probabilities:
- It is often desirable to understand the long-term behavior of a Markov chain.
- For computing the steady-state probabilities of a Markov chain, we shall piggyback on some old friends from Linear Algebra — Eigenvalues and Eigenvectors.
- An Eigenvector is a vector whose direction remains unchanged when a linear transformation is applied to it.
Mathematically,
- Comparing the equations of steady-state probabilities and eigenvectors, it is easy to see that the steady-state vector is the eigenvector with eigenvalue 1.
- It is fairly straightforward to compute the eigenvectors of a Matrix programmatically.
[Bonus] Do all Markov Chains converge to a unique steady state regardless of the initial state?
- Turns out, only Irreducible and Aperiodic Markov chains converge to a unique steady-state probability.
- Such Markov chains are termed Ergodic Markov Chains.
- A Markov Chain is irreducible if in the transition graph there exists a path from every state to every other state.
- Edit: As pointed out by Xmaster, it is important to note that irreducibility implies that regardless of the present state, we can reach any other state in finite time. Reference: here
- An irreducible Markov chain is called periodic of there is some t such that there exists a state “s” that can be visited only at time t, 2t, 3t, … steps. If a Markov chain is not periodic, it is termed aperiodic.
