Skip to content
Preprint

Nonparametric Multi Change Point Detection for Markov Chains via Adaptive Clustering

Jul 2026 · 2 citations · 43 references
Mathematics

TL;DR

A non-parametric clustering algorithm which can accurately obtain the change points from a given Markovian dataset of length $n$ is proposed by bridging together two different components of mathematical statistics; Rademacher complexities of Markov chains, and adaptive clustering via penalisation.

Abstract

Offline change point detection tries to detect time points of distribution change in a given data sequence; and is now routinely used in signal processing, speech processing, climatology etc. Despite this broad applicability across economics, computer science, and planetary sciences, rigorous, nonparametric techniques for change point detection with non-independent and identically distributed (i.i.d.) datasets has remained elusive. This paper establishes such guarantees by proposing a non-parametric clustering algorithm which can accurately obtain the change points from a given Markovian dataset of length $n$. It does so by bridging together two different components of mathematical statistics; Rademacher complexities of Markov chains, and adaptive clustering via penalisation. Our first result uses recent advances in Rademacher complexities of regenerating Markov chains to derive a Dvoretzky Kiefer Wolfowitz (DKW) type inequality for the empirical distribution of the Markov chain. We then use this to show that an adaptive clustering algorithm recovers the correct change points for a Markovian sequence. We establish the tightness of our rates by showing that they essentially coincide with the best known rates for i.i.d. data. We end the paper by discussing the computational considerations of the problem.

View source

Similar papers

Preprint Aug 2026

Change Point Detection and Localization in High-Dimensional Time Series

High-dimensional analogue: H\"older-Gauss-approximations, which can be (roughly) interpreted as the Gaussian approximation for a H\"older-norm of the high-dimensional partial sum process of the high-dimensional partial sum process is presented.

Patrick Bastian, Daria Tieplova, Nina Dörnemann et al. · 0 citations
Preprint Aug 2026

SCAN: Sequentially Detecting Change-points via Adaptive Nonparametric Inference

SCAN is introduced, an offline method for detecting multiple distributional change-points in long, serially dependent univariate time series and achieves higher covering and F1-scores than competing methods across mean and joint mean-variance shifts, particularly under serial dependence.

Ashoka Prabashwara, P. Menéndez, Liam Hodgkinson et al. · 0 citations
Preprint Aug 2026

Recursive Multiple Change Point Detection of Nonstationary Time Series: Instability Tests, Estimation and Confidence Intervals

We develop bootstrap-assisted robust binary segmentation (BARBS), a recursive binary segmentation method for multiple change point detection under general nonstationary temporal dynamics. A novel Gaussian multiplier bootstrap for the CUSUM statistics is proposed, offering robustness to complex dependence structures. Th...

Le-Heng Cai, Zhou Zhou · 0 citations
Preprint Sep 2026

Simultaneous Change-Point Inference for High-Dimensional Functional Time Series

We develop a framework for simultaneous change-point inference of high-dimensional functional time series. The observations are modeled as temporally dependent vectors whose coordinates take values in possibly different separable Hilbert spaces, thereby covering a broad class of functional data. Heterogeneous mean chan...

A. Bücher, Colin Decker · 0 citations
Preprint Sep 2026

Nonparametric Change-Point Detection and Inference for High-Dimensional Distributions

High-dimensional distributions can change without altering means or covariances, while the number of affected coordinates is often unknown. We propose nonparametric procedures that address both challenges through standardized rank comparisons of marginal distributions. Sum and maximum scans target dense and sparse chan...

Ping Zhao, Long Feng · 0 citations
Preprint Sep 2026

Multiple change-point detection via bottom-up scanning

We study nonparametric multiple change-point detection for high-dimensional sequences, aiming to identify time points at which the underlying distribution changes. While many existing methods perform well when change-points are well-separated, their performance can deteriorate when structural breaks are densely cluster...

Jinhyeok Park, Hyeyoung Maeng, Ho-Seung Song · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.