← Stat 110: Probability

Unit 11: Markov Chains

A process that forgets everything but where it is now — transition matrices, which states keep getting revisited, and the long-run distribution it settles into.

9 topics · 29 questions

Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.

11.1 Defining a Markov Chain

  1. How it worksHow does the Markov property let one transition matrix summarize an entire random process?
  2. Worked exampleFind the probability of going from sunny to rainy to sunny over two days when P(rain given sun)=0.3 and P(sun given rain)=0.5.
  3. Common mistakeWhy doesn't the Markov property mean the process is memoryless about everything, only about the present?
Your turn1 of 2
Find the probability of going from sunny to rainy to sunny over two days when P(rain given sun) = 0.448 and P(sun given rain) = 0.619.

11.2 Transition Matrices and n-Step Transitions

  1. How it worksHow does matrix multiplication sum over every possible intermediate state a chain could pass through?
  2. Worked exampleFind the two-step transition probability from A to B in a 2-state chain with rows 0.7, 0.3 and 0.4, 0.6.
  3. Going furtherWhat happens to the n-step transition matrix as n grows very large?
Your turn1 of 2
Find the two-step transition probability from A to B in a 2-state chain where P(stay in A) = 0.718 and P(stay in B) = 0.489.

11.3 Classifying States: Recurrent, Transient, and Periodic

  1. How it worksHow does the chance of ever returning to a state sort every state into recurrent or transient?
  2. Common mistakeWhy doesn't a state need to be visited on every single step to still be classified as recurrent?
  3. Worked exampleFind whether a state is recurrent or transient when, once left, there's a 0.4 chance of never returning.
  4. Going furtherWhat happens to a Markov chain's classification of states when the chain splits into two disconnected pieces?
Your turn1 of 2
A state, once left, has probability 0.642 of never being visited again. Find the probability that the state IS eventually revisited.

11.3 Irreducibility

  1. How it worksHow does the ability to eventually reach any state from any state define an irreducible chain?
  2. Worked exampleFind whether a 3-state chain is irreducible when state 3 is reachable from 1 and 2 but only leads back to itself.
  3. Common mistakeWhy doesn't a chain need a direct one-step link between two states to still be irreducible?
Your turn1 of 2
In a chain where each state has a self-loop probability of 0.433 (staying put) and otherwise moves to another reachable state, find the probability the chain moves away from its current state in one step.

11.4 The Stationary Distribution

  1. How it worksHow does solving π times the transition matrix equals π turn the stationary distribution into equations?
  2. Common mistakeWhy doesn't a chain need to start in its stationary distribution for that distribution to still be meaningful?
  3. Worked exampleFind the stationary distribution of a 2-state chain with rows 0.9, 0.1 and 0.2, 0.8.
  4. Going furtherWhat happens to the stationary distribution when every state's transition probabilities are made equal?
Your turn1 of 2
Find the stationary distribution's first component (pi1) for a 2-state chain with P(stay in state 1) = 0.829 and P(stay in state 2) = 0.81.

11.4 Convergence to the Stationary Distribution

  1. How it worksHow does repeatedly multiplying by the transition matrix wash out the memory of the starting distribution?
  2. Worked exampleFind the distribution after 3 steps starting entirely in state 1, using rows 0.9, 0.1 and 0.2, 0.8.
  3. Ties togetherHow does convergence to stationarity connect to the law of large numbers settling toward a long-run average?
Your turn1 of 2
A 2-state chain has P(stay in 1) = 0.829 and P(stay in 2) = 0.81. Starting entirely in state 1, find the probability of being in state 1 after 14 steps.

11.5 Reversible Markov Chains

  1. How it worksHow does the detailed balance equation let you find a stationary distribution without solving the full system?
  2. Worked exampleFind the stationary distribution of a random walk on a 3-node path graph using detailed balance.
  3. Common mistakeWhy doesn't every Markov chain with a stationary distribution automatically satisfy detailed balance?
Your turn1 of 2
A random walk on a graph visits nodes with degrees 3, 5, and 4. Using detailed balance for a random walk on a graph, find the stationary probability of the node with degree 5.

11.5 Random Walks on Undirected Graphs

  1. How it worksHow does a node's degree directly determine its share of the stationary distribution on an undirected graph?
  2. Worked exampleFind the stationary probability of a node with degree 4 in a graph whose total degree across all nodes is 20.
  3. Going furtherWhat happens to a random walk's stationary distribution when every node in the graph has the same degree?
Your turn1 of 2
Find the stationary probability of a node with degree 7 in a graph whose total degree across all nodes is 72.

11.6 Google PageRank as a Markov Chain

  1. How it worksHow does a random surfer clicking links at random turn the web's link structure into a transition matrix?
  2. Worked exampleFind the PageRank-style weight of a page linked from two pages, each holding rank 0.1 and splitting it across 2 outgoing links.
  3. Ties togetherHow does PageRank's damping factor connect to guaranteeing the web's Markov chain is irreducible and aperiodic?
Your turn1 of 2
Find the PageRank-style weight of a page linked from two pages holding ranks 0.224 and 0.212, splitting their rank across 5 and 3 outgoing links respectively.