Seyed Masoud Hosseini · Overview · Study log · Weekly summaries · Ideas · Search · Transcript · RSS feed

Probability · Lecture 57 of 76 · 10:36

Setting Up a Markov Chain

Setting Up a Markov Chain on YouTube

Study guide

What this lecture covers

This worked problem builds a Markov chain from scratch for a lake with green and blue fish: each day one fish is caught at random, and if it is green it is painted blue and returned. The lecture verifies the Markov property applies, defines the states as the number of green fish remaining, derives the transition probabilities, and checks the special cases of all-green and all-blue lakes.

You should already know the definition of the Markov property and basic transition-probability notation before watching. Afterward, you'll be able to translate a described random process into a Markov chain: choosing states, arguing the Markov property holds, and computing transition probabilities p_ij from first principles.

Key ideas

  • Markov property check: the number of green fish tomorrow depends only on today's count, not on the history of previous days, because catching is uniformly random over the fish present today.
  • State definition: the state is i, the number of green fish currently in the lake, ranging from 0 to n.
  • Two possible transitions: from state i you can only stay at i (catch a blue fish) or move to i-1 (catch a green fish).
  • Transition probabilities: p_ii = (n-i)/n and p_i,i-1 = i/n, derived from the chance of catching a blue versus green fish.
  • Boundary checks: at state n (all green) the self-transition probability is 0 and you always move to n-1; at state 0 (all blue) the self-transition probability is 1.
  • Transient and recurrent states: states 1 through n are transient because the count can only decrease, while state 0 is recurrent and in fact absorbing.

Before you watch

  • Review the definition of the Markov property and how to argue a process satisfies it.
  • Know what transition probabilities p_ij represent in a Markov chain.
  • Be familiar with the definitions of recurrent, transient, and absorbing states.

Check your understanding

  1. Why does catching fish uniformly at random make this process satisfy the Markov property?
  2. How are the transition probabilities p_ii and p_i,i-1 derived from the number of green and blue fish?
  3. Why is state 0 absorbing while every other state is transient?
  4. How would the chain change if caught fish were not returned to the lake?

Vocabulary

from scratch (phrase)
Starting completely from the beginning, with nothing already built.
This problem builds a Markov chain from scratch.
translate (verb)
To turn a description into a formal mathematical model.
We translate the fish story into a Markov chain.
first principles (phrase)
The most basic facts, used to build up a result without shortcuts.
We derive the transition probabilities from first principles.
self-transition (phrase)
A transition where the chain stays in the same state.
Catching a blue fish is a self-transition.
boundary case (phrase)
A special situation at the edge of the possible range.
All-green and all-blue lakes are boundary cases.
absorbing state (phrase)
A state that, once reached, the chain never leaves.
State 0, all blue fish, is an absorbing state.
Markov property (phrase)
The rule that the future of a process depends only on its current state, not its past.
The lecture checks that the fish-catching process satisfies the Markov property.
transition probability (phrase)
The chance of moving from one state to another in a single step.
The transition probabilities depend on how many green fish remain.
state (noun)
One possible situation a Markov chain can be in at a given time.
The state is the number of green fish in the lake.
recurrent (adjective)
Describing a state a process is guaranteed to return to.
State 0 is recurrent because the chain stays there forever.
transient (adjective)
Describing a state that a process eventually leaves for good.
States 1 through n are transient because the count only decreases.
uniformly at random (phrase)
Chosen so that every option has an equal chance of being picked.
A fish is caught uniformly at random each day.
verify (verb)
To check that something is true or correct.
We verify that the Markov property holds for this process.
special case (phrase)
A specific, simpler version of a more general problem.
All-green and all-blue lakes are special cases of the chain.
chain (noun)
A short way of referring to a Markov chain.
The chain moves down by one state each time a green fish is caught.
argue (verb)
To give reasons showing that something is true.
We argue that the Markov property holds because catching is random each day.
notation (noun)
A system of symbols used to write mathematical ideas.
Transition-probability notation writes p_ij for moving from i to j.
derive (verb)
To work out a result step by step from known rules or facts.
We derive the transition probabilities from the setup.
remaining (adjective)
Left over after part of something has been used or removed.
The state counts the green fish remaining in the lake.
worked problem (phrase)
A full example problem solved step by step to show how a method is used.
This worked problem builds a Markov chain for a fish-catching scenario.
returned (adjective)
Put back into its original place after being taken out.
A caught fish is painted and returned to the lake.
history (noun)
The record of past events leading up to now.
The Markov property means the future doesn't depend on the history of past days.
chance (noun)
The likelihood that something will happen.
The transition probabilities come from the chance of catching each color.
count (noun)
The total number of something.
The state is the count of green fish remaining.
principle (noun)
A basic rule or idea that other reasoning is built on.
First principles means building the answer from basic principles alone.

Chapters

From the YouTube description

MIT 6.041SC Probabilistic Systems Analysis and Applied Probability, Fall 2013
View the complete course: http://ocw.mit.edu/6-041SCF13
Instructor: Jimmy Li

License: Creative Commons BY-NC-SA
More information at http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

← Lecture 16: Markov Chains I · Markov Chain Practice 1 →