[CS 70] Markov Chains – Finding Stationary Distributions

1. Formula
   Observation

   The board shows the handwritten equation $\pi_n = \pi_0 P^n$.

2. Audio
   Observation

   The speaker says, "So as we've seen earlier, pi sub n is going to be equal to pi sub zero times p to the n."

$\pi_n$

The probability distribution row vector at time step $n$.

A row vector of probabilities over the states of a Markov chain.

1. Formula
   Observation

   The board shows $\pi_0$ in the equation $\pi_n = \pi_0 P^n$.

2. Audio
   Observation

   The speaker refers to it as "pi sub zero".

$\pi_0$

The initial probability distribution row vector at time step 0.

A row vector of probabilities over the states of a Markov chain.

1. Formula
   Observation

   The board shows $P$ in the equation $\pi_n = \pi_0 P^n$.

2. Audio
   Observation

   The speaker refers to it as "p to the n" and later as the "transition matrix".

$P$

The transition matrix of the Markov chain.

A square matrix where each row sums to 1.

1. Formula
   Observation

   The board shows $P^n$ in the equation $\pi_n = \pi_0 P^n$.

2. Audio
   Observation

   The speaker says "p to the n".

$P^n$

The $n$-th power of the transition matrix $P$, representing the probabilities of transitioning between states in exactly $n$ steps.

A square matrix where each row sums to 1.

1. Formula
   Observation

   The board shows the equation $\pi P = \pi$.

2. Audio
   Observation

   The speaker says, "when the row vector pi when multiplied by this p does not change... pi times p is equal to pi."

$\pi$

A stationary (or invariant) distribution, which is a probability distribution row vector that remains unchanged after being multiplied by the transition matrix.

A row vector of probabilities over the states of a Markov chain.

1. Diagram
   Observation

   The board shows a circle labeled 'A' representing a state in a Markov chain.

2. Audio
   Observation

   The speaker says, "with two states A and B."

$A$

One of the two states in the example Markov chain.

State space of the Markov chain.

1. Diagram
   Observation

   The board shows a circle labeled 'B' representing a state in a Markov chain.

2. Audio
   Observation

   The speaker says, "with two states A and B."

$B$

The other of the two states in the example Markov chain.

State space of the Markov chain.

1. Formula
   Observation

   $P = [[0.3, 0.7], [0.4, 0.6]]$

P

Transition probability matrix for a two-state Markov chain with states A and B.

2x2 matrix of real numbers

1. Diagram
   Observation

   State node labeled 'A' in the transition diagram.

2. Formula
   Observation

   Row label 'A' in the matrix P.

A

One of the two states in the Markov chain.

Discrete state space element

1. Diagram
   Observation

   State node labeled 'B' in the transition diagram.

2. Formula
   Observation

   Column label 'B' in the matrix P.

B

The other state in the Markov chain.

Discrete state space element

1. Formula
   Observation

   $π = [π(a), π(b)]$

2. Audio
   Observation

   "set our pi to be equal to the row vector pi a and pi b"

π

Row vector representing the stationary distribution over states A and B.

1x2 row vector of real numbers

1. Formula
   Observation

   $π(a)$ appears as the first component of the vector π.

$π(a)$

Stationary probability of being in state A.

Real number (probability)

1. Formula
   Observation

   The board shows the equation $\pi P = \pi$.

2. Audio
   Observation

   The speaker says, "there's a special case when the row vector pi when multiplied by this p does not change... we call pi a stationary distribution. Or in other words, we call it an invariant distribution."

A stationary distribution (also called an invariant distribution) is a probability distribution row vector $\pi$ that remains unchanged when multiplied by the transition matrix $P$ of a Markov chain. This means that if the system starts in this distribution, it will remain in this distribution at all future time steps.

1. $\pi$ is a row vector.

2. $P$ is the transition matrix of the Markov chain.

3. The elements of $\pi$ are non-negative and sum to 1.

1. $\pi$
2. $P$

1. Audio
   Observation

   The speaker says, "And to find such a distribution, we typically just solve this system of linear equations, pi P is equal to pi."

To find a stationary distribution for a Markov chain, one solves the system of linear equations given by $\pi P = \pi$, subject to the constraint that the probabilities in $\pi$ sum to 1.

1. $P$ is the transition matrix of the Markov chain.

1. Stationary Distribution

1. Formula
   Observation

   $πP = π$

2. Audio
   Observation

   "solve the equation pi P is equal to pi"

The stationary distribution π of a Markov chain with transition matrix P satisfies the linear system $πP = π$, where π is a row vector of probabilities.

1. π is a row vector

2. P is the transition matrix

1. Audio
   Observation

   "is one and point four plus point six is also one."

1. The beginning of the sentence is cut off; it likely refers to the first row sum $0.3 + 0.7 = 1$.

Each row of a valid transition probability matrix must sum to 1, ensuring that from any state, the total probability of transitioning to all possible next states is 1.

1. P is a stochastic matrix

1. Formula
   Observation

   The board explicitly writes $πP = π$.

2. Audio
   Observation

   The speaker says he will erase the Markov chain to have more room, indicating the displayed setup is the starting point for solving the stationary distribution.

For this two-state chain, the stationary distribution π is defined by the fixed-point equation $πP = π$, where P is the transition matrix. The video uses this equation to generate componentwise balance relations.

1. π is a row vector.

2. P is the transition matrix of the Markov chain.

1. Audio
   Observation

   The speaker says, 'Well we know that it's a valid probability distribution. So its elements must sum to one.'

2. Formula
   Observation

   He writes $π(a) + π(b) = 1$.

Because π is a probability distribution over the two states, its entries must add to 1. This supplies the second independent equation needed to solve for $π(a)$ and $π(b)$.

1. π is a valid probability distribution.

2. The state space has exactly two states, a and b.

1. Stationary distribution equation

1. Audio
   Observation

   The speaker calls $π(a)+π(b)=1$ 'the equation that we can use as our second non-redundant equation.'

After deriving a relation between $π(a)$ and $π(b)$ from the balance equations, the method is to pair that relation with the normalization condition to obtain a solvable system.

1. One equation comes from stationarity/balance.

2. The other comes from total probability equaling 1.

1. Normalization condition for a probability distribution

1. Audio
   Observation

   The speaker explains that while the distribution $\pi$ typically changes at each time step, there is a special case where it does not change when multiplied by the transition matrix $P$.

2. Formula
   Observation

   The board shows the equation $\pi P = \pi$.

1. Expression

   $$$$
   Explanation

   Start with the general formula for the distribution at time $n$: $\pi_n = \pi_0 P^n$.

   Justification

   This is a previously established property of Markov chains.

   Shown in the video
2. Expression

   $$$$
   Explanation

   Consider the case where the distribution does not change from one time step to the next, i.e., $\pi_{n+1} = \pi_n$.

   Justification

   This is the definition of a special, unchanging case.

   Derived from the video
3. Expression

   $$\pi P = \pi$$
   Explanation

   If we let $\pi_n = \pi$, then $\pi_{n+1} = \pi P$. Setting them equal gives $\pi P = \pi$.

   Justification

   Algebraic substitution based on the condition for no change.

   Derived from the video
4. Expression

   $$$$
   Explanation

   A distribution $\pi$ satisfying $\pi P = \pi$ is called a stationary or invariant distribution.

   Justification

   This is the definition provided by the speaker.

   Shown in the video

A stationary distribution $\pi$ is defined by the equation $\pi P = \pi$, meaning it is a left eigenvector of the transition matrix $P$ with eigenvalue 1.

1. Formula
   Observation

   Step-by-step algebraic manipulation shown on the whiteboard.

2. Audio
   Observation

   Narrator explains each step of multiplying the vector by the matrix and simplifying.

1. Expression

   $$[\pi(a), \pi(b)] \begin{bmatrix} 0.3 & 0.7 \\ 0.4 & 0.6 \end{bmatrix} = [\pi(a), \pi(b)]$$
   Explanation

   Substitute the specific matrix P and vector π into the stationary equation $πP = π$.

   Justification

   Definition of stationary distribution.

   Shown in the video
2. Expression

   $$0.3\pi(a) + 0.4\pi(b) = \pi(a)$$
   Explanation

   Perform matrix-vector multiplication for the first component.

   Justification

   Matrix multiplication rule.

   Shown in the video
3. Expression

   $$0.7\pi(a) + 0.6\pi(b) = \pi(b)$$
   Explanation

   Perform matrix-vector multiplication for the second component.

   Justification

   Matrix multiplication rule.

   Shown in the video
4. Expression

   $$3\pi(a) + 4\pi(b) = 10\pi(a)$$
   Explanation

   Multiply the first equation by 10 to clear decimals.

   Justification

   Algebraic equivalence.

   Shown in the video
5. Expression

   $$7\pi(a) + 6\pi(b) = 10\pi(b)$$
   Explanation

   Multiply the second equation by 10 to clear decimals.

   Justification

   Algebraic equivalence.

   Shown in the video
6. Expression

   $$4\pi(b) = 7\pi(a)$$
   Explanation

   Rearrange the first simplified equation by moving $3π(a)$ to the right side.

   Justification

   Algebraic manipulation.

   Shown in the video
7. Expression

   $$7\pi(a) = 4\pi(b)$$
   Explanation

   Rearrange the second simplified equation by moving $6π(b)$ to the left side.

   Justification

   Algebraic manipulation.

   Shown in the video
8. Expression

   $$4\pi(b) = 7\pi(a) \iff 7\pi(a) = 4\pi(b)$$
   Explanation

   Observe that both derived equations are identical.

   Justification

   Logical equivalence.

   Shown in the video

The system $πP = π$ yields only one independent linear equation relating $π(a)$ and $π(b)$, making the system underdetermined without an additional constraint like normalization.

1. Audio
   Observation

   "we can't actually solve this system... because we have two unknowns... but we only have one useful equation. So what do we do?"

1. Expression

   $$\text{Unknowns: } \pi(a), \pi(b)$$
   Explanation

   Identify the variables to be solved for.

   Justification

   Problem setup.

   Shown in the video
2. Expression

   $$\text{Independent Equations: } 1$$
   Explanation

   Count the number of linearly independent equations derived from $πP = π$.

   Justification

   Result of previous derivation.

   Shown in the video
3. Expression

   $$1 < 2$$
   Explanation

   Compare the number of equations to the number of unknowns.

   Justification

   Arithmetic comparison.

   Derived from the video

The system cannot be uniquely solved using only $πP = π$; a second independent equation is required.

1. Formula
   Observation

   The board already contains $10\times (0.3π(a)+0.4π(b)=π(a))$, $10\times (0.7π(a)+0.6π(b)=π(b))$, then $3π(a)+4π(b)=10π(a)$, $7π(a)+6π(b)=10π(b)$, and finally $4π(b)=7π(a)$.

2. Audio
   Observation

   The speaker says, 'So I previously had 4 pi b is equal to 7 pi a.'

1. The earlier derivation of these balance equations occurs before this clip; only the final consequence $4π(b)=7π(a)$ is reused here.

1. Expression

   $$10\times(0.3\pi(a)+0.4\pi(b)=\pi(a))$$
   Explanation

   The first displayed line multiplies the a-component balance equation by 10 to clear decimals.

   Justification

   Algebraic scaling of an equality.

   Shown in the video
2. Expression

   $$10\times(0.7\pi(a)+0.6\pi(b)=\pi(b))$$
   Explanation

   The second displayed line does the same for the b-component balance equation.

   Justification

   Algebraic scaling of an equality.

   Shown in the video
3. Expression

   $$3\pi(a)+4\pi(b)=10\pi(a)$$
   Explanation

   This is the simplified form of the first scaled equation.

   Justification

   Arithmetic simplification after multiplying by 10.

   Shown in the video
4. Expression

   $$7\pi(a)+6\pi(b)=10\pi(b)$$
   Explanation

   This is the simplified form of the second scaled equation.

   Justification

   Arithmetic simplification after multiplying by 10.

   Shown in the video
5. Expression

   $$4\pi(b)=7\pi(a)$$
   Explanation

   Rearranging the two simplified balance equations yields the same proportionality relation between $π(a)$ and $π(b)$.

   Justification

   Subtract terms on each side and simplify.

   Shown in the video

The stationary probabilities satisfy $4π(b)=7π(a)$.

1. Formula
   Observation

   The board writes $4π(b)=7π(a)$, then $π(b)=7/4 π(a)$, then $π(a)+7/4 π(a)=1$, then $11/4 π(a)=1$, then $π(a)=4/11$.

2. Audio
   Observation

   The speaker says he will plug this into the equation to get $π(a)+7/4 π(a)=1$, then $11/4 π(a)=1$, hence $π(a)=4/11$.

1. Expression

   $$4\pi(b)=7\pi(a)$$
   Explanation

   Start from the proportionality relation obtained from the balance equations.

   Justification

   Previously derived result.

   Shown in the video
2. Expression

   $$\pi(b)=\frac{7}{4}\pi(a)$$
   Explanation

   Divide both sides by 4 to express $π(b)$ in terms of $π(a)$.

   Justification

   Algebraic rearrangement.

   Shown in the video
3. Expression

   $$\pi(a)+\frac{7}{4}\pi(a)=1$$
   Explanation

   Substitute $π(b)=7/4 π(a)$ into the normalization equation $π(a)+π(b)=1$.

   Justification

   Substitution into a known equation.

   Shown in the video
4. Expression

   $$\frac{11}{4}\pi(a)=1$$
   Explanation

   Combine like terms: $1 + 7/4 = 11/4$.

   Justification

   Fraction addition.

   Shown in the video
5. Expression

   $$\pi(a)=\frac{4}{11}$$
   Explanation

   Multiply both sides by $4/11$ to isolate $π(a)$.

   Justification

   Solving a linear equation.

   Shown in the video

$π(a)=4/11$.

1. Formula
   Observation

   The board writes $π(b)=1-π(a)=7/11$.

2. Audio
   Observation

   The speaker says, 'And therefore pi of b is equal to 1 minus pi of a, which is equal to 7 over 11.'

1. Expression

   $$\pi(b)=1-\pi(a)$$
   Explanation

   Rearrange the normalization equation $π(a)+π(b)=1$.

   Justification

   Algebraic rearrangement.

   Shown in the video
2. Expression

   $$\pi(b)=1-\frac{4}{11}=\frac{7}{11}$$
   Explanation

   Insert the value just found for $π(a)$ and compute the difference.

   Justification

   Substitution and arithmetic.

   Shown in the video

$π(b)=7/11$.

1. Formula
   Observation

   The board writes $π = [4/11, 7/11]$.

2. Audio
   Observation

   The speaker says, 'So our stationary distribution pi is just equal to the row vector 4 over 11 and 7 over 11.'

1. Expression

   $$\pi(a)=\frac{4}{11},\quad \pi(b)=\frac{7}{11}$$
   Explanation

   Collect the two solved component values.

   Justification

   Results of the previous derivations.

   Shown in the video
2. Expression

   $$\pi=\left[\frac{4}{11},\frac{7}{11}\right]$$
   Explanation

   Write the stationary distribution as the row vector whose entries correspond to states a and b.

   Justification

   Definition of π as [$π(a)$, $π(b)$].

   Shown in the video

The stationary distribution is $π=[4/11, 7/11]$.

1. Diagram
   Observation

   The board shows a state diagram for a Markov chain with two states, A and B, and transition probabilities: A->$A (0.3)$, A->$B (0.7)$, B->$A (0.4)$, B->$B (0.6)$.

2. Formula
   Observation

   The board shows the corresponding transition matrix $P = \begin{bmatrix} 0.3 & 0.7 \\ 0.4 & 0.6 \end{bmatrix}$.

3. Audio
   Observation

   The speaker describes the states and transition probabilities and then writes out the matrix, explaining how each entry corresponds to a transition probability.

Given a Markov chain with two states, A and B, and the following transition probabilities: P(A->A)=0.3, P(A->B)=0.7, P(B->A)=0.4, P(B->B)=0.6. Construct the transition matrix P.

1. States: A, B

2. Transition probabilities: P(A->A)=0.3, P(A->B)=0.7, P(B->A)=0.4, P(B->B)=0.6

To write down the 2x2 transition matrix P.

1. Expression

   $$P = \begin{bmatrix} P(A \to A) & P(A \to B) \\ P(B \to A) & P(B \to B) \end{bmatrix}$$
   Explanation

   The transition matrix P is structured such that the entry in row i and column j represents the probability of moving from state i to state j.

   Justification

   Definition of a transition matrix for a Markov chain.

   Derived from the video
2. Expression

   $$P = \begin{bmatrix} 0.3 & 0.7 \\ 0.4 & 0.6 \end{bmatrix}$$
   Explanation

   Substitute the given transition probabilities into the matrix structure.

   Justification

   Direct substitution from the problem statement.

   Shown in the video
3. Expression

   $$0.3 + 0.7 = 1 \text{ and } 0.4 + 0.6 = 1$$
   Explanation

   Check that the sum of probabilities in each row equals 1.

   Justification

   A fundamental property of a valid transition matrix is that its rows must sum to 1.

   Shown in the video

The transition matrix is $P = \begin{bmatrix} 0.3 & 0.7 \\ 0.4 & 0.6 \end{bmatrix}$.

The speaker performs a sanity check by confirming that the rows of the constructed matrix sum to 1.

1. Diagram
   Observation

   A two-state transition diagram is shown with states A and B, self-loops 0.3 and 0.6, and cross transitions 0.7 and 0.4.

2. Formula
   Observation

   The corresponding matrix $P=[[0.3,0.7],[0.4,0.6]]$ and the equation $πP=π$ are written on the board.

3. Audio
   Observation

   The speaker erases the diagram and matrix to make room, then solves for the stationary distribution.

Given the two-state Markov chain with transition matrix $P=[[0.3,0.7],[0.4,0.6]]$, find its stationary distribution π.

1. States are a and b (written A and B in the diagram).

2. $P = [[0.3, 0.7], [0.4, 0.6]]$.

3. $π = [π(a), π(b)]$.

4. $πP = π$.

Compute the explicit values of $π(a)$ and $π(b)$.

1. Expression

   $$4\pi(b)=7\pi(a)$$
   Explanation

   From the balance equations already on the board, the stationary probabilities satisfy this proportionality.

   Justification

   Derived from $πP=π$.

   Shown in the video
2. Expression

   $$\pi(a)+\pi(b)=1$$
   Explanation

   Because π is a probability distribution, its entries sum to 1.

   Justification

   Normalization of a probability vector.

   Shown in the video
3. Expression

   $$\pi(b)=\frac{7}{4}\pi(a)$$
   Explanation

   Rewrite the proportionality relation to substitute into the normalization equation.

   Justification

   Algebraic rearrangement of $4π(b)=7π(a)$.

   Shown in the video
4. Expression

   $$\pi(a)+\frac{7}{4}\pi(a)=1$$
   Explanation

   Substitute $π(b)=7/4 π(a)$ into $π(a)+π(b)=1$.

   Justification

   Substitution.

   Shown in the video
5. Expression

   $$\frac{11}{4}\pi(a)=1$$
   Explanation

   Combine coefficients of $π(a)$.

   Justification

   Fraction addition: $1 + 7/4 = 11/4$.

   Shown in the video
6. Expression

   $$\pi(a)=\frac{4}{11}$$
   Explanation

   Solve the resulting linear equation.

   Justification

   Multiply both sides by $4/11$.

   Shown in the video
7. Expression

   $$\pi(b)=1-\frac{4}{11}=\frac{7}{11}$$
   Explanation

   Use normalization to find the remaining component.

   Justification

   Substitution into $π(a)+π(b)=1$.

   Shown in the video
8. Expression

   $$\pi=\left[\frac{4}{11},\frac{7}{11}\right]$$
   Explanation

   Assemble the final stationary distribution vector.

   Justification

   By definition $π=[π(a),π(b)]$.

   Shown in the video

$π = [4/11, 7/11]$.

The entries are nonnegative and sum to 1; also $4π(b)=7π(a)$ holds because $4\cdot (7/11)=28/11=7\cdot (4/11)$.

1. Diagram
   Observation

   A state diagram is drawn with two circles labeled 'A' and 'B'. Arrows indicate transitions with associated probabilities: a self-loop on A with 0.3, an arrow from A to B with 0.7, an arrow from B to A with 0.4, and a self-loop on B with 0.6.

1. State A

2. State B

3. Transition arrows

4. Probability labels

1. The diagram is progressively drawn, first showing the states, then the transitions and their probabilities.

1. The states A and B remain fixed in their positions.

The visual representation defines the structure and parameters of the Markov chain example, showing all possible state transitions and their probabilities.

1. Formula
   Observation

   The transition matrix $P$ is written as a 2x2 matrix. The rows are labeled 'A' and 'B', and the columns are implicitly 'A' and 'B'. The entries are filled in one by one: 0.3, 0.7, 0.4, 0.6.

1. Matrix brackets

2. Row labels A, B

3. Matrix entries

1. The matrix is built element by element, with the speaker verbally confirming each value as it is written.

1. The overall 2x2 structure of the matrix remains constant.

The visual construction of the matrix directly translates the information from the state diagram into a formal algebraic object, reinforcing the relationship between the graphical and matrix representations of a Markov chain.

1. Diagram
   Observation

   Directed graph with nodes A and B, showing self-loops and transitions with probabilities.

1. Node A

2. Node B

3. Arrow A->$A (0.3)$

4. Arrow A->$B (0.7)$

5. Arrow B->$A (0.4)$

6. Arrow B->$B (0.6)$

1. Topology of the graph

2. Probability values on edges

Visual representation of the transition probabilities defined in matrix P.

1. Animation
   Observation

   Handwriting appears sequentially on the digital whiteboard as the narrator speaks.

1. Vector definition

2. Matrix equation

3. Simplified linear equations

1. New lines of math appear at the bottom of the board

1. Previous steps remain visible

Demonstrates the process of expanding the matrix equation into scalar linear equations.

1. Diagram
   Observation

   At the start, the upper left shows a two-state transition diagram with A and B, arrows labeled 0.3, 0.7, 0.4, and 0.6; below it are $P=[[0.3,0.7],[0.4,0.6]]$ and $πP=π$.

2. Formula
   Observation

   The right half already contains the worked balance equations ending in $4π(b)=7π(a)$.

1. State diagram with nodes A and B

2. Transition matrix P

3. Equation $πP=π$

4. Balance-equation work on the right

1. Nothing new is written yet; the board presents the setup and prior derivation.

1. The transition probabilities remain fixed at 0.3, 0.7, 0.4, 0.6.

2. The relation $4π(b)=7π(a)$ is already established.

The visual setup identifies the Markov chain and shows that the stationary-distribution problem has already been reduced to a proportionality between $π(a)$ and $π(b)$.

1. Audio
   Observation

   The speaker says, 'I'm going to erase this Markov chain so I have more room to work with.'

2. Animation
   Observation

   The diagram, matrix P, and $πP=π$ are erased from the upper-left area, leaving blank space.

1. Transition diagram

2. Matrix P

3. Equation $πP=π$

1. The upper-left setup is removed from view.

2. The right-side algebra remains visible.

1. The previously derived relation $4π(b)=7π(a)$ stays on the board.

2. The problem remains the same two-state stationary-distribution computation.

This is a practical board-management step, not a mathematical change; it creates room for the final solution steps.

1. Formula
   Observation

   In the cleared upper-left area, the presenter writes $π=[π(a),π(b)]$, then $π(a)+π(b)=1$, then $4π(b)=7π(a)$, then $π(b)=7/4 π(a)$, then the substitution chain leading to $π(a)=4/11$, $π(b)=7/11$, and finally $π=[4/11,7/11]$.

2. Animation
   Observation

   A curved arrow is drawn from the final boxed vector back toward the earlier balance-equation work.

1. $π=[π(a),π(b)]$

2. $π(a)+π(b)=1$

3. $4π(b)=7π(a)$

4. $π(b)=7/4 π(a)$

5. $π(a)=4/11$

6. $π(b)=7/11$

7. $π=[4/11,7/11]$

1. The solution is rewritten compactly in the newly cleared space.

2. Each substitution step is added sequentially until the final vector is boxed.

1. The underlying transition matrix and balance relation do not change.

2. The normalization condition remains $π(a)+π(b)=1$ throughout.

The visual progression shows how one independent balance relation plus normalization determines the full stationary distribution.

1. Audio
   Observation

   The speaker says, "And just a quick sanity check to make sure that your transition matrix is correct is to check that the rows sum to one."

A student might construct a transition matrix incorrectly without verifying its validity.

The speaker explicitly demonstrates a crucial sanity check: the sum of the probabilities in each row of a transition matrix must equal 1. This is a necessary condition for it to be a valid probability distribution for transitions from a given state.

1. Audio
   Observation

   "these two equations are exactly the same equation. They're redundant equations."

Students might expect the two components of $πP = π$ to provide two independent equations sufficient to solve for two unknowns.

For any stochastic matrix, the rows of (P - I) sum to zero, implying the equations from $πP = π$ are always linearly dependent. One equation is lost, necessitating the normalization constraint $Σπ_i = 1$.

1. Audio
   Observation

   The speaker explicitly calls $π(a)+π(b)=1$ the 'second non-redundant equation.'

One might think the componentwise equations from $πP=π$ alone determine the stationary distribution uniquely.

For this two-state chain, the balance equations yield only a proportionality such as $4π(b)=7π(a)$; the normalization condition $π(a)+π(b)=1$ is needed to fix the scale and obtain unique probabilities.

1. Audio
   Observation

   The speaker says, "we call pi a stationary distribution. Or in other words, we call it an invariant distribution."

The terms 'stationary distribution' and 'invariant distribution' are used interchangeably to describe the same concept defined by $\pi P = \pi$.

1. Audio
   Observation

   The speaker says, "And to find such a distribution, we typically just solve this system of linear equations, pi P is equal to pi."

The method for finding a stationary distribution is directly based on solving the defining equation of that distribution.

1. Audio
   Observation

   The speaker says, "So now let's go over an example of how to find a stationary distribution in a Markov chain."

2. Formula
   Observation

   The example involves constructing the matrix $P$ which would be used in the equation $\pi P = \pi$.

The example provides a concrete Markov chain for which a stationary distribution could be found using the previously defined method.

1. Diagram
   Observation

   Diagram and matrix are presented side-by-side.

The state diagram visually encodes the same information as the numerical transition matrix P.

1. Formula
   Observation

   Expansion of $πP = π$ into scalar equations.

The general definition of the stationary distribution is applied to the specific matrix P to generate a solvable system of linear equations.

1. Audio
   Observation

   The speaker moves from the existing balance relation to the fact that π is a valid probability distribution and therefore sums to 1.

2. Formula
   Observation

   The board pairs $4π(b)=7π(a)$ with $π(a)+π(b)=1$.

The stationary equation provides a relation among components, and the probability-distribution property supplies the additional independent constraint needed to solve the system.

1. Audio
   Observation

   The speaker says this is the equation used as the second non-redundant equation.

The normalization identity is not just a fact here; it is used as the practical second equation in the solution method.

1. Audio
   Observation

   The speaker defines a stationary distribution.

1. Stationary Distribution

1. Audio
   Observation

   The speaker explains the method for finding a stationary distribution.

1. Method for Finding Stationary Distribution

1. Audio
   Observation

   The speaker provides an alternative name for a stationary distribution.

1. Stationary Distribution

1. Diagram
   Observation

   A state diagram is shown.

2. Formula
   Observation

   A transition matrix is constructed from the diagram.

1. Constructing a Transition Matrix from a State Diagram

1. Audio
   Observation

   The speaker mentions a sanity check for the transition matrix.

1. Forgetting to Check Row Sums

1. Formula
   Observation

   Expansion of vector-matrix product.

1. Stationary Distribution Equation
2. Derivation of Stationary Distribution System

1. Audio
   Observation

   Discussion of redundant equations and underdetermined system.

1. Redundancy in Stationary Equations
2. Identification of Underdetermined System

1. Audio
   Observation

   The speaker explains that because π is a valid probability distribution, its elements must sum to one.

1. Normalization condition for a probability distribution
2. Use normalization as the second independent equation

1. Formula
   Observation

   The board shows $π(b)=7/4 π(a)$ substituted into $π(a)+π(b)=1$ to get $π(a)=4/11$.

1. Normalization condition for a probability distribution

1. Formula
   Observation

   The final boxed result is $π=[4/11,7/11]$.

2. Audio
   Observation

   The speaker states that the stationary distribution is the row vector $4/11$ and $7/11$.

1. Stationary distribution equation