Change-point detection

Change-point detection estimates locations where a sequence's distribution or mean changes. A piecewise-constant mean has a sparse vector of adjacent differences; one-dimensional total variation denoising exploits this sparsity without fixing the number of changes in advance.

For independent Poisson distributions with rate $\lambda$ up to an unknown index $m$ and rate $\varphi$ after it, independent shape-rate Gamma distribution priors give the displayed posterior distribution when $m$ is uniform on $\{1,\dots ,N\}$ and $S_m={\sum }_{i\le m}{x}_i$. The model differs from a continuous-time Poisson change-point posterior. The endpoint $m=N$ represents no observed change: the second segment is empty and its rate keeps its prior law.

Integrating the two rates out of the Poisson count change-point model with gamma priors gives these weights up to a common factor, by the defining Gamma function integral. Normalizing across the finitely many possible indices gives the exact marginal posterior distribution of $m$, providing a check on Markov chain Monte Carlo estimates. One can also draw $m$ from these weights and then draw both rates from their conditional Gamma distributions, producing independent exact joint posterior samples.

The full conditional distributions are $\lambda \mid m,x\sim \mathrm{Gamma}(\alpha +S_m,\beta +m)$ and $\varphi \mid m,x\sim \mathrm{Gamma}(\gamma +S_N-S_m,\delta +N-m)$, in shape-rate notation. Conditional on the two rates, $m$ has weights $w_j=\exp [j(\varphi -\lambda )+S_j\log (\lambda /\varphi )]$. A Gibbs sampler cycles through these three draws. Each update preserves the joint posterior distribution; subtracting the largest log weight before exponentiation stabilizes the categorical draw. Averages of $1_{\{m=N\}}$ estimate the posterior probability of no observed change.

Take independent proper normal prior distributions for the two segment means and a proper inverse-gamma distribution for the common variance. A uniform prior distribution over $m=1,\dots ,n$ may then retain the empty second segment. The posterior distribution is proper: its likelihood function is bounded above by $(2\pi {)}^{-n/2}{v}^{-n/2}$, whose integral against $\mathrm{IG}(a_0,b_0)$ is finite for $a_0,b_0>0$. At $m=n$ the second mean has its unchanged proper prior distribution as its full conditional distribution. The configuration's posterior probability now has the meaningful interpretation of no change inside the observed sample.

For independent means $\theta \sim N({\mu }_{\theta },t_{\theta })$ and $\varphi \sim N({\mu }_{\varphi },t_{\varphi })$, the first mean's conditional precision is $m/v+1/t_{\theta }$ and conditional precision-weighted mean is ${\sum }_{i\le m}{x}_i/v+{\mu }_{\theta }/t_{\theta }$; replace $m$ by $n-m$ for the second mean. With $v\sim \mathrm{IG}(a_0,b_0)$ its conditional law is $\mathrm{IG}(a_0+n/2,b_0+S_m/2)$. The discrete split has conditional probabilities proportional to $e^{-S_m/(2v)}$. These full conditional distributions give a Gibbs sampler including $m=n$. Averaging the sampled indicators of that configuration estimates its probability; averaging its conditional probabilities gives an estimate by Rao-Blackwellization.

For an Inhomogeneous Poisson process whose known positive intensity changes from ${\lambda }_1$ to ${\lambda }_2$ at an unknown time $\theta \in (0,T)$, the ordered arrival-time likelihood function isUnder a uniform prior, each interval between successive arrivals has an exponential posterior density with rate in the exponent ${\lambda }_2-{\lambda }_1$. Its integrated weights allow exact interval selection followed by a truncated exponential draw; when the two rates coincide, the Bayesian posterior is uniform and the data contain no change-time information.