Introduction to Probability · Problem 11.9
Random Walks — Grinstead & Snell
Mathematics — Probability · markov-chains-random-walk-circle
Problem
Consider a random walk on a circle of circumference . The walker takes one unit step clockwise with probability and one unit counterclockwise with probability . Modify the program ErgodicChain to allow you to input and and compute the basic quantities for this chain. (a) For which values of is this chain regular? ergodic? (b) What is the limiting vector ? (c) Find the mean first passage matrix for and . Verify that , where is the clockwise distance from to .Intuitive explanation
A random walk on a circle is a finite Markov chain where the key insight is that regularity and ergodicity depend on whether the chain can reach all states and return to them predictably. For a circle, you need to think about the greatest common divisor of possible step sizes—if and , the walker can move both directions, making all states communicating. The limiting distribution reveals whether the chain "forgets" its starting position, and the mean first passage times expose the beautiful symmetry of circular geometry: distance matters more than the specific path.
Intuitive explanation
A random walk on a circle is a finite Markov chain where the key insight is that regularity and ergodicity depend on whether the chain can reach all states and return to them predictably. For a circle, you need to think about the greatest common divisor of possible step sizes—if and , the walker can move both directions, making all states communicating. The limiting distribution reveals whether the chain "forgets" its starting position, and the mean first passage times expose the beautiful symmetry of circular geometry: distance matters more than the specific path.