We’ve seen what happens when you take a random walk through an unfamiliar landscape. But what happens when you have a set of rules to follow?
The mysterious guide
You are about to embark on another muddy walk in the dark, through the unfamiliar landscape.
This time you are not alone, a mysterious guide appears from the darkness.
The guide has no map and no compass.
Instead, from their coat they pull out a book, titled ‘Rules of the Journey‘.
They tell you to choose your next step randomly and explain that they can use their rule book to calculate whether the step should be taken.
You go ahead and randomly chose steps, conferring with the guide each time and waiting for them to accept or reject your move.
Sometimes you move towards more probable regions of the landscape, at other times you move towards the less probable.
You don’t know where you are going, even with the guide’s help, however you now have a statistical destiny.
As with the random walk, when daylight comes you return to measure the pattern of footprints left behind in the mud.
This time they reveal a probability distribution, one shaped by the rules of the mysterious guide’s rule book.
Rules of the Journey
In this analogy the guide book contains what’s known as the transition rule.
The transition rule determines how you (the wanderer) move from your current position to the next position.
It’s important to remember that you are still randomly choosing steps, but your movements are ultimately structured by the guide’s rules.
You might ask how this is considered ‘random’
Just in case you haven’t stumbled across this before, randomness doesn’t mean the absence of structure.
In fact something can be simultaneously random and structured.
For example, as an observer we don’t know where you will step next but we do know the rules that govern the possible moves you take.
This means that though individual steps are unpredictable, long-term behaviour is predictable.
So what does Markov Chain Monte Carlo (MCMC) mean?
Markov chain
In our analogy the Markov chain is the sequence of positions you visit, as you explore the landscape.
It is named ‘Markov’ after Andrey Markov who studied stochastic process where the next state depends on the current state.
In essence, we don’t need to know the entire journey to determine what happens next. We only need to know where you, the wanderer, currently are.
Your current position becomes the starting point for the next step and so on, eventually creating a chain of connected observations.
Monte Carlo
One journey doesn’t tell us much. But if we let you take thousands of steps on your wanderings, we can collect thousands of observations.
Monte Carlo is the name for a general computational approach that uses random sampling to estimate quantities that might otherwise be difficult to calculate.
In the analogy we use your many footprints to learn about the landscape.
Taken together, MCMC is a chain of connected random samples that allows us to explore a probability distribution.
Next we’ll look at how MCMC is used in practice 🙂