16 Markov processes and the Metropolis algorithm
The chapter introduces Markov processes as a general way to generate random sequences by starting in an initial state and repeatedly moving to a new state based only on the current one. It uses intuitive examples such as walking through a city, gambling with chips, and generating text to show that a state can be almost anything, discrete or continuous. A general Markov process is then implemented as a distribution over sequences, with an initial distribution and a transition function that produces the next-state distribution or ends the sequence.
The text then explores Markov text generation by treating words as states and learning initial-word and next-word distributions from a corpus such as Shakespeare. By parsing sentences, counting transitions, and building categorical distributions, the program can generate new text that sounds plausibly Shakespearean even if it is often nonsensical. This serves as a small-scale model of modern language generation and highlights both the power and the limits of memoryless random processes.
Finally, the chapter turns to Bayesian inference for continuous distributions and shows how the Metropolis algorithm makes posterior sampling possible when only a non-normalized probability density is known. Using Bayes’ theorem, the posterior density is formed from a prior and a likelihood, then sampled by proposing nearby values and accepting or rejecting them based on relative weight. The prior can serve as the initial distribution, a centered normal distribution can serve as the proposal, and the resulting Markov chain produces samples from the posterior, enabling practical probabilistic reasoning from observed evidence.
Summary
- Sampling a Markov process generates a random sequence of values. The generated sequence can be finite or infinite, and the values can be discrete or continuous.
- Markov processes generate a random sequence of states, which can be anything. The first state is chosen randomly by sampling from an initial distribution. Each subsequent state is chosen by calling a transition function with the most recently generated state and sampling from the resulting distribution.
- If states are words, Markov processes generate texts. An easy way to create an initial distribution and transition function is to analyze an existing text and record the distributions of initial words in sentences and word pairs in those sentences.
- This basic technique generates implausible texts; we can generate more plausible texts (texts more likely to fool the reader) by using a variety of techniques, some of which are expensive or unethical. The intent to generate plausible random text lies with the author of the model, not the model.
- If we have the PDF of a target distribution and know basic facts about the areas with high weight and the size of the highly probable portions of the support, we can use the Metropolis algorithm to create a Markov process in which the sequence of states is the sequence of samples from the target distribution.
- The Metropolis algorithm is particularly useful for generating continuous posterior distributions. Given a distribution that represents our beliefs prior to observations and a likelihood function which models how the world works, we can obtain a posterior distribution that precisely updates our uncertainty in the context of newly observed evidence.
Fabulous Adventures in Data Structures and Algorithms ebook for free
