16 Markov processes and the Metropolis algorithm
This chapter covers
- Generating random sequences with Markov processes
- Random Markov texts
- Posterior sampling with the Metropolis algorithm
The final step in this long introduction to principled techniques for using randomness in programs is sampling from an arbitrary continuous distribution. In particular, we want to start with a prior distribution which models the world, condition that distribution on observations of the world, and thereby deduce a posterior distribution which correctly updates the model. Programs that make decisions in the face of an uncertain world should use principled, mathematically sound algorithms. The algorithms in this chapter can help us do that.
The Markov process—which language models use to generate random text—is also the basis of the Metropolis algorithm for sampling from continuous posterior distributions. We’ll start this final fabulous adventure by looking at Markov processes in general; then we’ll see how to use them to sample continuous distributions.