Setting Up a Markov Chain

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?