Valid Changepoint p-values When the Noise Has Memory

When a dynamic program — an exact search that finds the best way to cut a sequence into pieces — picks changepoints in a time series, analysts then want to know which cuts are real. Recent work computes honest p-values for those cuts. These p-values account for the fact that the same data chose the cuts and then tested them. But they assume the noise is independent from one time step to the next. Real signals such as genomic copy-number profiles, pollution records and stock prices have noise with memory: today's error partly repeats yesterday's. That memory couples the errors across time. Independence-based segmenters mistake it for structure and cut too often. The p-values attached to those cuts then report significance that is not there.

We propose to extend exact post-selection inference for dynamic-programming segmentation to first-order autoregressive noise. In that setting each error is a fraction $\phi$ of the previous error plus fresh noise, which is the simplest first-order Markov error process. We pair this with a benchmark that measures false-alarm rates on real change-free stretches of data rather than on clean synthetic noise. In two sentences: we make the segmenter's cost and the p-value's null distribution both use the correlated-noise covariance, which keeps the test exact. We then show, on real data, how badly independence-based methods that look calibrated on standard synthetic suites actually behave.

Core Claim

Computing Valid p-value for Optimal Changepoint by Selective Inference using Dynamic Programming (OptSeg-SI) supplies the method. It shows that if you slide the data along one line $x(z) = a + b z$, the optimal dynamic-programming loss is piecewise quadratic in $z$. The set of $z$ that reproduce the observed segmentation can therefore be computed exactly, which yields a valid conditional p-value. That derivation uses independent Gaussian errors, so $b$ is proportional to the contrast vector $\eta$. The contrast vector is the weights that turn the data into the tested quantity, for example the difference between two adjacent segment means.

Our claim is that the same machinery stays exact under the model

$$x_t = \mu_t + e_t,\qquad e_t = \phi\, e_{t-1} + \varepsilon_t,\quad \varepsilon_t \sim N(0,\sigma^2),$$

where $\mu_t$ is the piecewise-constant signal and $e_t$ is autoregressive noise with coefficient $\phi$. Two changes are required. First, the dynamic program's segment cost must be the correlated-noise (generalized least squares) cost, whose loss is still quadratic in $x$ and hence in $z$. Second, the line direction must become $b = \Sigma_\phi \eta / (\eta^\top \Sigma_\phi \eta)$, where $\Sigma_\phi$ is the noise covariance. That direction is what makes $\eta^\top x$ independent of the component of the data held fixed.

Using the correlated cost without the corrected direction, or the reverse, leaves a residual coupling. We expect it to inflate false positives in proportion to $\phi$. What is new is exact selective inference for dynamic-programming changepoints under Markov-correlated errors. The main difficulty, and the part we treat as the real research problem, is a second layer of coupling: $\phi$ itself is estimated from the same data.

Research Program

The build has three parts.

Part one: two segmenters with correlated-noise costs. The first is cheap. It uses the conditional-intercept cost $\sum_{t=j+1}^{i}(x_t - c - \phi x_{t-1})^2$, minimized over an intercept $c$ for each segment. Because $x_j$ is observed data, this cost depends only on the segment endpoints $(j,i)$. It is therefore additive, and the standard recursion from Computational Complexity of Segmentation applies unchanged.

The second is exact but harder. It uses the full piecewise-constant-mean likelihood. Here the first residual of each segment depends on the previous segment's mean, which breaks the additivity that dynamic programming relies on. Changepoint detection in non-exchangeable data identifies this obstacle and switches to reversible-jump sampling instead. We keep dynamic programming. The coupling touches only one term per boundary, so we carry the previous segment's mean as a continuous state and track the loss as a quadratic function of it. This is the device behind DeCAFS, which appears in the file only as a baseline in that paper. Making this functional recursion also parametric in $z$ produces loss surfaces that are piecewise quadratic in two variables. Tractability is the main engineering risk. If the exact version proves too slow beyond a few thousand points, we fall back to the conditional-intercept cost and report the power we lose.

Part two: handling the estimated $\phi$. Plugging in $\hat\phi$ breaks exactness, because $\hat\phi$ depends on the data that also set the selection event. We will compare three estimators. The first is a difference-based estimator computed from lag-two differences, which is largely insensitive to a small number of mean shifts. The second estimates $\phi$ from a held-out neighbouring stretch where one is available, such as another chromosome or another year. The third conditions on the sufficient statistic that $\hat\phi$ uses. Each is judged by how far realized Type I error moves from nominal as sequence length grows. The file motivates this concern: Effects of estimation errors on cause-selecting charts and Linear Regression with Stationary Errors: the R Package slm both show that estimated nuisance parameters and serial correlation corrupt error rates when they are ignored.

Part three: a real-null calibration benchmark. This is the synthetic-reliance lens. Standard suites inject clean shifts into independent noise at fixed indices. Examples are the 400-point sets with changes at 100, 200 and 300 used by Offline Changepoint Detection With Gaussian Processes, and the step-400 Gaussian sequences in Conformal changepoint localization. On such data, independence-based inference looks calibrated by construction.

We will build null stretches from real data. Sources are copy-number regions from GSE11976 and GSE29172 with no annotated aberration, Turing Changepoint Dataset series or sub-windows with no annotated change, Sainsbury plc returns, and Los Alamos network counts between annotated events. We will also build semi-synthetic sequences by planting known mean shifts into real residuals via block resampling. For every generator we report its lag-1 through lag-5 residual autocorrelation next to the real data's. This is the diagnostic the file notes is missing: whether a synthetic generator preserves the dependence structure of the real errors.

This design follows the lesson of On the Equivalency, Substitutability, and Flexibility of Synthetic Data. There, synthetic data that lacked realistic dynamics actually hurt DanceTrack tracking, while adding multi-group behaviour raised HOTA (a tracking accuracy score) from 68.8 to 73.5. Synthetic data was useful only when it reproduced the structure that matters. For segmentation, that structure is error memory.

Baselines

Naive reference. The do-nothing baseline has two versions. The first runs the independence-cost dynamic program and a classical t-test on each adjacent-segment mean difference, ignoring both selection and correlation. The second is the ZERO detector, which never declares a change. Offline Changepoint Detection With Gaussian Processes notes that ZERO scores deceptively well on Turing-benchmark F1. We include it so our metrics cannot be gamed that way, and we report Type I error and power rather than F1 alone.

Strongest existing method. This is OptSeg-SI run exactly as published. On GSE11976 and GSE29172 its authors report statistical power of 0.71 to 0.75, against 0.53–0.62 for SMUCE (Computing Valid p-value for Optimal Changepoint by Selective Inference using Dynamic Programming). It is the right competitor because it already solves the double-dipping problem and is exact under its own assumptions. Any gain we show must therefore come from handling error memory.

No Type I error for OptSeg-SI under autocorrelated noise is reported on Lacuna. Measuring it is our first experiment. For fairness, OptSeg-SI and our method receive the same sequences, the same number of segments or penalty chosen by the same rule, and the same noise-variance estimator. They differ only in the covariance used in the cost and in the line direction. Beating OptSeg-SI means two things. On AR(1) nulls with $\phi \ge 0.3$ and on real null stretches, we must keep realized Type I error within Monte Carlo error of 0.05 where OptSeg-SI exceeds it. On planted-shift semi-synthetic data, our power must stay within a few points of OptSeg-SI's power measured at matched realized error.

Prewhitening baseline. Transform the data by $y_t = x_t - \hat\phi x_{t-1}$, then run OptSeg-SI on $y$. This is described under "Why not just…?" below.

Other comparators. We also run the reversible-jump moving-sum model of Changepoint detection in non-exchangeable data, thresholded at posterior changepoint probabilities, as the dependence-aware Bayesian comparator. We record its runtime and false-discovery rate on the same nulls.

Ablations. Two ablations isolate the key ingredient. The first uses the correlated-noise cost with the independent line direction. The second uses the independent cost with the correlated direction. If only the full combination is calibrated, the claim that both pieces are needed is supported.

Why not just…?

Why not just prewhiten the series and run OptSeg-SI on the residuals? This is the most serious threat, and it might plausibly work. With a known $\phi$, prewhitening is mathematically the conditional-intercept model from part one, so exact selective inference on $y$ is valid for its own selection event. Where it differs is the hypothesis being tested. OptSeg-SI on $y$ tests a contrast of the whitened means $L\mu$, where $L$ is the whitening transform. That contrast mixes a mean shift with a one-step spike at the boundary, and it is not the mean difference in $x$ that the analyst asked about. The misspecified cost near boundaries may also blur localization.

We will report this baseline head to head. If it matches our exact method on power, localization error and calibration, we will say so. We will then recommend it with the corrected estimator of $\phi$ from part two, which remains necessary in either case. In that outcome the contribution narrows to the $\phi$-coupling analysis and the benchmark.

Why not just inflate the standard error with a long-run-variance correction? Linear Regression with Stationary Errors: the R Package slm shows that such corrections bring regression tests back near the nominal 0.05 level. However, they correct only for correlation and not for the fact that the boundaries were chosen to maximize the contrast. That selection bias is exactly what OptSeg-SI exists to remove. Our null experiments will show whether a correction-only test stays inflated after selection, which we expect because the dynamic program picks the most extreme cuts.

Why not just calibrate the detector with block-bootstrap nulls? This controls how often the procedure declares any change on stationary data, and it is cheap. It does not give per-changepoint conditional validity, and it depends on choosing a block length. We include it as a baseline on the real-null benchmark. If it controls family-level false alarms as well as our method, that is a real finding for practitioners who do not need per-cut p-values.

Why not just wrap the detector in conformal localization? Conformal changepoint localization (CONCH) gives distribution-free intervals, but its permutation argument requires exchangeable observations within each regime, and autocorrelation violates that assumption. Its interval width also depends on the base detector, as shown by its CIFAR-100 widths of about 47 steps with a weak classifier versus about 10 with a strong one. We will run CONCH on the AR(1) nulls and report its empirical coverage. We expect coverage to fall below nominal as $\phi$ grows.

Proposed Experiments

Experiment 1: miscalibration curve. On synthetic AR(1) nulls of length 500 to 5000 with $\phi$ from 0 to 0.9, we plot realized Type I error at level 0.05 for the naive test, OptSeg-SI, prewhitened OptSeg-SI, both ablations, and our method, with both known and estimated $\phi$. The decisive check is that OptSeg-SI's error grows with $\phi$ while ours stays flat when $\phi$ is known. The gap between the known-$\phi$ and estimated-$\phi$ curves quantifies the second-layer coupling.

Experiment 2: exchangeability trap on real nulls. We repeat Experiment 1 on the real change-free stretches and report each method's realized error next to its error on the matched i.i.d. synthetic suite. The gap between the two numbers measures directly how much the synthetic benchmark hid.

Experiment 3: power at matched error. On planted-shift semi-synthetic sequences built from real copy-number residuals, and on the full GSE11976 and GSE29172 profiles, we report power and localization error. The published 0.71–0.75 OptSeg-SI power figure serves as the reference point.

Experiment 4: cost and scaling. We report runtime of the exact functional-parametric recursion against the conditional-intercept version and the reversible-jump sampler as length grows. This decides whether the exact variant is practical or only a reference.

A negative result in Experiment 1 would falsify the core claim. Such a result would mean independence-based OptSeg-SI stays calibrated at moderate $\phi$, or that our method inflates even when $\phi$ is known. If prewhitening ties us in Experiment 3, the claim shrinks to the $\hat\phi$ correction and the benchmark, and the note will say so.