Chapter 16: Markov processes and the Metropolis algorithm

Introduction

This chapter introduces Markov processes and uses them as the foundation for Metropolis sampling of continuous posterior distributions.

• Chapter roadmap: Describe the chapter's progression from Markov processes and random text generation to using the Metropolis algorithm to sample continuous posterior distributions.
  Why it matters: This roadmap connects the chapter's text-generation example to its main probabilistic application.
• Posterior sampling objective: Explain that the chapter aims to start with a prior model of the world, condition it on observations, and sample the resulting posterior distribution for decision-making under uncertainty.
  Why it matters: Posterior sampling lets a program update an uncertain model using evidence rather than rely on unprincipled guesses.
• Markov foundation for Metropolis: State that a Markov process can generate random sequences such as language-model text and that this same kind of process is the basis of the Metropolis algorithm for sampling continuous posterior distributions.
  Why it matters: Recognizing this shared foundation explains why the chapter studies Markov processes before introducing Metropolis sampling.

Key terms: Markov process, Markov texts, Metropolis algorithm, continuous posterior distributions, prior distribution, observations, posterior distribution, continuous distribution, language models

16.1 What is a Markov process?

This section defines Markov processes, represents one as a distribution of state sequences, and illustrates the idea with gambler’s ruin and practical applications.

• Markov process properties: Explain a Markov process as a randomly generated sequence of states in which each next-state choice depends only on the current state. Describe its initial state, possible termination, and the fact that its states may be discrete or continuous.
  Why it matters: This is the defining idea needed to recognize and model processes whose future behavior is determined probabilistically by their present state.
• Generic Markov distribution design: Describe the general-purpose representation of a Markov process as a distribution of sequences of generic states T. Explain that it samples an initial state from an initial distribution and uses a transition function from the current state to a distribution of possible new states; an empty returned distribution terminates the sequence.
  Why it matters: This design turns the mathematical definition into a reusable programmatic distribution that can generate many kinds of state sequences.
• Gambler's ruin simulation: Trace the gambler's ruin Markov process in which the state is the gambler's chip count, states 0 and 10 terminate the process, and every other state transitions by a coin flip to one chip less or one chip more. Describe the initial distribution as a random count from four through seven chips.
  Why it matters: This concrete simulation shows how a transition rule generates finite sample sequences with potentially long runs.
• Markov process applications: Describe how real systems can be modeled as Markov processes by choosing a current state and a random transition based on it. Give an application from the section, such as Brownian motion, DNA mutation, a work queue, weather, stock prices, or Markov text generation.
  Why it matters: Modeling a system this way allows repeated samples to reveal behavior such as queue growth and client waiting time.

Key terms: Markov process, state, initial state, transition function, sample, Markov distribution, T, initial distribution, likelihood function, empty distribution

16.2 Markov texts

This section builds a word-level Markov process from Shakespeare sentences, explains why its generated text is limited, and contrasts its random generation with human intention.

• Word-level Markov text model: Describe how sentences from a text corpus define a Markov process whose states are words and whose samples are newly generated sentences.
  Why it matters: This shows how an abstract Markov process can generate observable sequences from learned transition probabilities.
• Sentence boundaries and parsing: Explain the simple parsing and termination rules used for the text model: lines are split into words, unwanted punctuation is trimmed while sentence-ending punctuation is retained, and a final word has no outgoing transition.
  Why it matters: The parser and sentence boundaries determine which word transitions the model learns and when generated output stops.
• Frequency-weighted transition learning: Describe how the model learns initial and transition distributions by counting observed first words and observed immediate word followers, using the counts as categorical-distribution weights.
  Why it matters: Frequency-weighted counts let the process favor transitions that occurred more often in the source text without manually assigning probabilities.
• Markov text limitations: Explain why a single-word-state Markov text generator can sound locally Shakespearean yet produce implausible or incoherent sentences, and describe how using pairs or triples of words as states can provide more context.
  Why it matters: Understanding the memory limit explains both the weaknesses of simple Markov text and the trade-off behind context-based language models.
• Random generation and intention: Distinguish the random word-by-word operation of a Markov text generator from the intentions of its designers or a human author, including the process's inability to plan, revise, or backtrack.
  Why it matters: This distinction prevents readers from attributing goals or understanding to an algorithm that only samples successive words.

Key terms: Markov process, state, initial distribution, transition function, categorical distribution, sentences, words, sentence terminators, empty distribution, mutable builder

16.3 Computing posteriors of continuous distributions

This section derives an unnormalized posterior PDF for continuous Bayesian updating and explains why the Metropolis algorithm is needed to sample from it.

• Continuous posterior construction: Explain how to construct a function that takes evidence of any type and returns a continuous posterior distribution from a continuous prior and a likelihood function. Describe the posterior PDF as the prior's Weight at a value multiplied by the likelihood distribution's Weight of the observed evidence.
  Why it matters: This construction turns a prior and statistical model into the posterior distribution that represents updated beliefs after evidence.
• Normalization constant omission: Justify why the posterior PDF can omit the Bayes denominator P(evidence) when the sampler accepts a non-normalized PDF. Explain that, for fixed observed evidence, this denominator is a constant that changes total area but not the relative weights across the support.
  Why it matters: Avoiding the evidence denominator makes it possible to define the posterior even when its normalized density is not available.
• Likelihood weighting consistency: Describe the consistency requirement for non-normalized likelihood distributions: calls to the likelihood function must use the same overall weighting scale. Explain that differing total areas for distributions returned at different possible values would incorrectly distort the posterior PDF.
  Why it matters: A likelihood with inconsistent scaling makes some candidate values appear too likely or too unlikely for reasons unrelated to the evidence.
• Metropolis sampling motivation: Explain why rejection sampling is not suitable for this task and state the problem delegated to the Metropolis algorithm: sampling a continuous distribution when only its non-normalized PDF is available. Mention that rejection sampling requires many details about the PDF's shape, whereas Metropolis requires only a few facts about that shape.
  Why it matters: This identifies why the chapter moves from deriving a posterior density to the Metropolis algorithm.

Key terms: prior, likelihood function, posterior, continuous distribution, PDF, Weight, P(evidence), non-normalized PDF, relative weight, support

16.4 The Metropolis algorithm

This section explains how the Metropolis algorithm uses a Markov process and accept-or-reject proposals to sample a target distribution from only its non-normalized PDF.

• Metropolis acceptance rule: Explain how each Metropolis step proposes a value near the current sample and accepts it with probability equal to the proposed weight divided by the current weight, otherwise retaining the current sample.
  Why it matters: This acceptance rule is the small mechanism that makes a random walk produce samples matching the target distribution.
• Non-normalized weight sampling: Explain why Metropolis can sample a target using a non-normalized PDF: its acceptance test needs only the quotient of proposed and current weights, so a shared normalization constant cancels out.
  Why it matters: Many useful targets, especially posterior distributions, are available only up to a proportional weight rather than as normalized distributions.
• Markov-chain implementation: Describe the Metropolis output as a Markov-process sequence: the first state comes from an initial distribution, and each transition returns either a proposal or the previous state through a coin-flip distribution.
  Why it matters: Viewing Metropolis as a Markov process provides the implementation structure for producing samples on demand.
• Initial and proposal choices: Describe the requirements for the initial and proposal distributions: initial samples must lie in the target support, while proposals must be centered on the current sample, unbiased, and tuned to a reasonable distance.
  Why it matters: Suitable starting and proposal distributions let the chain explore the target effectively instead of clustering excessively or repeatedly rejecting distant proposals.

Key terms: Metropolis algorithm, current sample, proposed sample, proposal distribution, weight, standard uniform sample, non-normalized PDF, weight function, quotient, target distribution

16.5 Sampling posteriors with Metropolis

This section applies the Metropolis algorithm to turn a continuous prior and likelihood into posterior samples, illustrated with inferring a coin’s fairness from observed flips.

• Metropolis posterior construction: Describe how to construct a continuous posterior sampler with Metropolis from a prior and likelihood-derived target weight function. Explain why the prior can serve as the initial distribution and what makes a suitable proposal distribution.
  Why it matters: This is the practical step that turns an unnormalized posterior weight into samples from a posterior distribution.
• Binomial likelihood for flips: Explain how the binomial distribution models evidence consisting of a number of heads in a fixed number of flips of an unfair coin. State that its weight combines the probabilities of successes and failures with the number of permutations producing that count.
  Why it matters: The binomial likelihood connects an assumed coin fairness to the observed count of heads used to update that belief.
• Posterior fairness update: Trace how observing 9 heads in 10 flips changes the modeled belief about a factory coin’s fairness from the clamped-normal prior to a posterior that makes fairness at or below 50% unlikely. Relate this change to evidence updating uncertainty rather than treating the observation as certainty.
  Why it matters: It demonstrates the purpose of Bayesian posterior sampling: evidence can substantially and quantitatively revise an uncertain prior belief.
• Principled Bayesian automation: Explain the section's broader claim that Bayesian reasoning applies when observed evidence can reduce uncertainty, such as distinguishing real user accounts from hostile bot accounts. State why the section frames principled uncertainty-based decision-making as a moral responsibility for software engineers automating decisions at scale.
  Why it matters: The technique is presented not just as a coin example, but as a principled basis for consequential automated decisions under uncertainty.

Key terms: Metropolis algorithm, initial distribution, proposal distribution, support, target distribution, prior, binomial distribution, likelihood, trials, successes

16.6 Summary

This summary recaps how Markov processes generate state sequences, how they can produce text, and how the Metropolis algorithm samples continuous posterior distributions.