Barry-Hartigan (1993) A Bayesian Analysis for Change Point Problems

Summary

This paper develops a Bayesian treatment of multiple change points using the product partition model (PPM). A sequence of observations is modeled as arising from an underlying parameter sequence that is piecewise constant on contiguous blocks; the start of each block is a change point. The PPM assigns a partition probability proportional to a product of prior cohesions — one per block — and, given the partition, treats block parameters as independent. The key structural result is that the posterior is again a product partition model (with cohesions multiplied by block marginal likelihoods), which lets the data reweight partitions automatically. Inference about any parameter proceeds by conditioning on the partition and then averaging over all partitions; this is computable exactly in $O(n^2)$ or approximately in $O(n)$ per sweep by Gibbs/Markov sampling. The method is shown to outperform competitors at detecting sharp, short-lived changes.

Key Claims

• Product partition model. The probability of a partition $p$ into blocks is $\propto\prod_{\text{blocks }ij} c_{ij}$, a product of prior cohesions $c_{ij}$; given the blocks, the block parameters $\theta_{ij}$ are independent with block prior densities. The number of blocks $b$ (from 1 to $n$) is random.
• Conjugacy of partitions. Given the data the posterior is also a product partition model, with posterior cohesions $c_{ij}f_{ij}(X_{ij})$ (prior cohesion times the block marginal likelihood) and updated independent block posteriors — the analytic engine that makes change-point inference tractable.
• Change-point prior as constant per-point probability. A natural cohesion choice corresponds to each position being a change point with probability $p$ independently; equivalently the parameter sequence is a Markov chain that stays constant with probability $1-p$ and jumps otherwise. Small $p$ yields few, long blocks.
• Shrinkage-aware block prior. For normal data the block mean has prior $\mathcal N(\mu_0,\sigma_0^2/(j-i))$ — larger deviations are expected (and detectable) in short blocks than long ones, a scaling built into the prior; nuisance scale parameters are integrated out.
• Estimate by averaging, not selecting. Rather than choosing one "best" set of change points, posterior means average over all partitions weighted by their posterior probability — a Bayesian model average that avoids overcommitting to a single break configuration.
• Computation. Exact posterior means cost $O(n^2)$; for long series, Gibbs sampling over the change-point indicators is $O(n)$ per iteration and practical.
• Performance. Against Schwarz (BIC-type maximum-likelihood partition), Chernoff-Zacks, and Yao, the PPM avoids the "disasters" of the others and is superior for sharp, short-lived changes, provided $p$ is estimated from the data.

Concepts Introduced or Extended

• Change-Point Analysis

Entities Mentioned

• Daniel Barry
• John A. Hartigan

Quotes

"The probability of any partition is proportional to a product of prior cohesions, one for each block in the partition… Given the observations a new product partition model holds, with posterior cohesions for the blocks."

"Inference about particular parameters may then be made by first conditioning on the partition, and then averaging over all partitions."

My Take

The elegance here is the closure property: because the product form of the partition prior survives multiplication by a product-form likelihood, the posterior stays a product partition model and the whole change-point problem collapses to computing block marginal likelihoods and cohesions. That is what buys the exact $O(n^2)$ recursion and the clean model-averaged estimates — no reversible-jump machinery required, in contrast to the RJMCMC route the wiki already documents. The averaging-over-partitions stance is also the philosophically honest one for change-point data, where the exact break locations are rarely identified; reporting a single segmentation overstates certainty. The main practical lever is the cohesion / $p$ specification, which encodes how many breaks you expect and to which the short-block detections are sensitive.