[CS 70] Markov Chains – Finding Stationary Distributions

Computer Science Mentors

30 Apr 201806:43

Summary

TLDRThe video script explains the concept of a stationary or invariant distribution in a Markov chain. It demonstrates how to find such a distribution by solving a system of linear equations where the multiplication of the transition matrix and the row vector of probabilities yields the same distribution. The example involves a simple Markov chain with two states, A and B, with given transition probabilities. The solution involves simplifying the equations and using the property that the probabilities must sum to 1, leading to the stationary distribution vector (4/11, 7/11).

Takeaways

📚 Pi sub n is the probability distribution at time step n, calculated as Pi sub 0 times P to the power of n.
🔄 The row vector Pi changes at each time step in a Markov chain, but there is a special case where it remains constant.
🌟 A stationary or invariant distribution is when multiplying the transition matrix P with Pi results in the same Pi.
🧩 To find a stationary distribution, solve the system of linear equations Pi P = Pi.
🔍 An example Markov chain is provided with two states A and B, with specific transition probabilities.
📉 The transition matrix is a 2x2 matrix, and rows must sum to 1 for the matrix to be correct.
🔢 The equations derived from Pi P = Pi are 0.3 Pi A + 0.4 Pi B = Pi A and 0.7 Pi A + 0.6 Pi B = Pi B.
🔄 Simplifying the equations leads to redundant equations, indicating a need for additional constraints.
🔄 The sum of elements in Pi must equal 1, which provides the necessary second equation to solve for Pi A and Pi B.
🔑 The solution to the equations is Pi A = 4/11 and Pi B = 7/11, forming the stationary distribution for the given Markov chain.

Q & A

What is a stationary distribution in the context of a Markov chain?
-A stationary distribution, also known as an invariant distribution, is a probability distribution that remains unchanged when multiplied by the transition matrix of a Markov chain. This means that if you apply the transition probabilities to the distribution, you get the same distribution back.
How do you determine if a distribution is stationary in a Markov chain?
-To determine if a distribution is stationary, you solve the system of linear equations where the product of the transition matrix and the distribution vector equals the distribution vector itself. If such a solution exists, the distribution is stationary.
What is the condition for the rows of a transition matrix to be valid?
-The rows of a transition matrix must sum to 1. This ensures that the probabilities of transitioning from one state to all possible states add up to the certainty of a transition occurring.
What is the significance of the transition matrix in a Markov chain?
-The transition matrix in a Markov chain represents the probabilities of moving from one state to another in the chain. Each element in the matrix corresponds to the probability of transitioning from one specific state to another.
How many states does the Markov chain in the example have?
-The Markov chain in the example has two states, labeled as 'a' and 'b'.
What are the probabilities of transitioning from state 'a' to state 'b' and vice versa in the given example?
-In the example, the probability of transitioning from state 'a' to state 'b' is 0.7, and the probability of transitioning from state 'b' to state 'a' is 0.4.
What is the self-loop probability for state 'a' in the example Markov chain?
-The self-loop probability for state 'a', which is the probability of staying in state 'a', is 0.3.
What is the self-loop probability for state 'b' in the example Markov chain?
-The self-loop probability for state 'b', which is the probability of staying in state 'b', is 0.6.
Why can't the system of equations be solved directly in the example provided?
-The system of equations in the example is redundant, meaning that the equations do not provide enough independent information to solve for both unknowns (PI_a and PI_b). This redundancy occurs because the equations essentially state the same relationship.
How is the second equation used to solve for the stationary distribution in the example?
-The second equation is derived from the requirement that the elements of the probability distribution must sum to 1. This non-redundant equation, combined with the relationship between PI_a and PI_b, allows for the calculation of the stationary distribution.
What is the final stationary distribution for the Markov chain in the example?
-The final stationary distribution for the Markov chain in the example is a row vector with elements 4/11 and 7/11, representing the probabilities of being in states 'a' and 'b', respectively.

Outlines

00:00

🧩 Introduction to Stationary Distributions in Markov Chains

This paragraph introduces the concept of a stationary distribution in the context of Markov chains. It explains that the row vector \( \pi \), representing the probability distribution, changes at each time step when multiplied by the transition matrix \( P \). However, there is a special case where the multiplication of \( \pi \) and \( P \) results in the same distribution, making \( \pi \) a stationary or invariant distribution. The method to find such a distribution involves solving the system of linear equations \( \pi P = \pi \). The paragraph also sets the stage for an example involving a Markov chain with two states, A and B, and their respective transition probabilities.

05:04

🔍 Solving for the Stationary Distribution in a Two-State Markov Chain

This paragraph delves into the process of finding a stationary distribution for a specific two-state Markov chain with states A and B. The transition probabilities are given, and the transition matrix is constructed accordingly. The rows of the matrix are checked to ensure they sum to 1, which is a necessary condition for a valid transition matrix. The equation \( \pi P = \pi \) is then used to set up a system of equations to solve for the probabilities \( \pi_A \) and \( \pi_B \). Initially, the equations appear redundant, but by recognizing that the elements of \( \pi \) must sum to 1, a second equation is derived. This leads to the solution where \( \pi_A = \frac{4}{11} \) and \( \pi_B = \frac{7}{11} \), thus identifying the stationary distribution for the given Markov chain.

Mindmap

Keywords

💡pi sub n

In the context of the video, 'pi sub n' refers to the probability distribution at a specific time step 'n' in a Markov chain. It is a vector that represents the probabilities of being in each state at time 'n'. The video discusses how 'pi sub n' evolves over time, typically changing with each step, but in special cases, it remains constant, which leads to the concept of a stationary distribution.

💡transition matrix

The 'transition matrix' is a fundamental concept in the video, representing the probabilities of transitioning from one state to another in a Markov chain. It is a matrix where each row sums to 1, ensuring that the total probability of transitioning to any state from a given state is 100%. The video uses a 2x2 transition matrix to illustrate the process of finding a stationary distribution.

💡stationary distribution

A 'stationary distribution' is a key concept in the video, defined as a probability distribution that remains unchanged in the Markov chain over time when multiplied by the transition matrix. This occurs when the row vector representing the distribution satisfies the equation pi times P equals pi, making it an invariant distribution within the system.

💡invariant distribution

An 'invariant distribution' is synonymous with a 'stationary distribution'. It is a special type of distribution in a Markov chain that does not change as the chain evolves. The video explains that this happens when the distribution vector, when multiplied by the transition matrix, yields the same distribution vector.

💡linear equations

The video discusses solving a 'system of linear equations' to find a stationary distribution. This involves setting up equations based on the condition that the product of the probability distribution vector and the transition matrix equals the original distribution vector. The solution to these equations provides the stationary distribution.

💡Markov chain

A 'Markov chain' is a mathematical system that describes a sequence of possible events where the probability of each event depends only on the state attained in the previous event. The video script uses a Markov chain with two states, A and B, to demonstrate the concept of a stationary distribution.

💡probability distribution

A 'probability distribution' in the video refers to the set of probabilities for each possible outcome in an experiment. In the context of a Markov chain, it is represented by the vector 'pi', which includes the probabilities of being in each state. The video emphasizes that for a valid probability distribution, the elements must sum to 1.

💡self-loop

A 'self-loop' in the video script refers to a transition within a state that does not lead to another state. For example, state A has a self-loop with a probability of 0.3, meaning there is a 30% chance that the system will remain in state A after a transition.

💡sanity check

The term 'sanity check' in the video is used to describe a quick verification process to ensure that the transition matrix is correctly set up. This involves checking that the sum of the probabilities in each row of the matrix equals 1, which is a necessary condition for a valid Markov chain.

💡redundant equations

In the context of solving for the stationary distribution, 'redundant equations' refer to equations that do not provide new information or are duplicates of other equations in the system. The video script mentions that after setting up the equations, it is found that one of the equations is redundant, leaving only one useful equation to solve for the distribution.

💡row vector

A 'row vector' in the video is used to represent the initial or current state probabilities in a Markov chain. It is a one-dimensional array of numbers written as a row rather than a column. The video uses a row vector to denote the probabilities of being in states A and B and to solve for the stationary distribution.

Highlights

Pi sub n is defined as the product of pi sub 0 and P to the power of n, representing the evolution of a probability distribution over time in a Markov chain.

A row vector PI is expected to change at each time step in a Markov chain due to the multiplication by the transition matrix P.

A stationary or invariant distribution is a special case where the multiplication of PI by the transition matrix P yields the same probability distribution.

To find a stationary distribution, one must solve the system of linear equations PI P equals PI.

An example Markov chain with states A and B is introduced, with specific transition probabilities between them.

The transition matrix for the example Markov chain is a 2x2 matrix with probabilities summing to 1 for each row.

The sanity check for the transition matrix involves ensuring that the sum of probabilities in each row equals 1.

The solution for the stationary distribution involves setting up and solving the equation PI P equals PI for the row vector PI.

The multiplication of the row vector PI by the transition matrix results in two equations that need to be solved.

Simplifying the equations by multiplying by ten makes the calculations more manageable.

The resulting equations after simplification are redundant, indicating that there is only one useful equation for solving the system.

The elements of the stationary distribution must sum to 1, providing a second non-redundant equation to solve the system.

The solution to the stationary distribution is found by using the relationship between PI(A) and PI(B) and the sum-to-one constraint.

The final stationary distribution for the example Markov chain is a row vector with probabilities 4/11 for state A and 7/11 for state B.

The process of finding a stationary distribution involves understanding the properties of Markov chains and applying linear algebra techniques.

The example demonstrates the practical application of finding a stationary distribution in a simple two-state Markov chain scenario.

The concept of a stationary distribution is crucial for understanding long-term behavior in stochastic processes modeled by Markov chains.