Introduction
Suppose we observe a data sequence with a single changepoint. We study the problem of offline changepoint localization. A long line of classical statistical methods provides point estimates of the change location [16 , 10 ] . More recently, modern machine learning methods, including random forests and neural networks, have also been used to estimate changepoint locations [12 ] (Li et al. 2024). However, these estimates typically do not come with a finite-sample reliability certificate. Our goal is to provide distribution-free uncertainty quantification for such estimates, turning a preliminary changepoint estimate into a confidence interval that contains the true changepoint with a user-specified coverage probability.
Problem setup
We now formalize the problem. Suppose we observe a sequence X = ( X 1 , … , X n ) ∈ X n \mathbf{X} = (X_1,\ldots,X_n) \in\mathcal{X}^n X = ( X 1 , … , X n ) ∈ X n for some n ≥ 2 n \ge2 n ≥ 2 , where X \mathcal{X} X is a general measurable space. We assume that the sequence X \mathbf{X} X admits a single changepoint, denoted by ξ ∈ [ n − 1 ] \xi\in[n-1] ξ ∈ [ n − 1 ] , where we write [ K ] [K] [ K ] to denote { 1 , … , K } \{1,\ldots,K\} { 1 , … , K } for any integer K ∈ N K \in\mathbb{N} K ∈ N . We make the following assumption on the joint distribution of X \mathbf{X} X .
Assumption 1. We assume that the segments ( X 1 , … , X ξ ) (X_1,\ldots,X_\xi) ( X 1 , … , X ξ ) and ( X ξ + 1 , … , X n ) (X_{\xi+1},\ldots,X_n) ( X ξ + 1 , … , X n ) are independent and each exchangeable.
We call the changepoint genuine if the one-dimensional marginal distributions induced by the two segments are different. A canonical example is the i.i.d. changepoint model: the observations are drawn i.i.d. from P 0 P_0 P 0 before the change and i.i.d. from P 1 ≠ P 0 P_1 \ne P_0 P 1 = P 0 after the change. No further knowledge of the distributions, their separation, or any particular structure on X \mathcal{X} X is assumed. This in fact poses the main challenge in distribution-free changepoint localization.
Our goal goes beyond obtaining a point estimate of the changepoint ξ \xi ξ . We seek a collection of time points that contains ξ \xi ξ with high probability. We formalize this goal below.
Definition 1. For α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , a measurable mapping C n , 1 − α : X n → 2 [ n − 1 ] C_{n,1-\alpha} : \mathcal{X}^n \to2^{[n-1]} C n , 1 − α : X n → 2 [ n − 1 ] is a distribution-free confidence set for a changepoint if
P X ∼ P ( ξ ∈ C n , 1 − α ( X ) ) ≥ 1 − α , \mathbb{P}_{\mathbf{X}\sim P}(\xi\in C_{n,1-\alpha}(\mathbf{X})) \ge1-\alpha, P X ∼ P ( ξ ∈ C n , 1 − α ( X )) ≥ 1 − α , for every distribution P P P with a changepoint at ξ ∈ [ n − 1 ] \xi\in[n-1] ξ ∈ [ n − 1 ] and satisfying Assumption Assumption 1.
Existing work
Offline changepoint analysis has a long history; see Truong et al. [20 ] ; Duggins [4 ] for surveys. A significant part of this literature focuses only on detecting the change. Beginning with CUSUM (Page [13 ] ), a large literature has developed around modern detection procedures, including kernel changepoint procedures (KCP) (Arlot et al. [1 ] ), ChangeForest (Londschien et al. [12 ] ), and conformal martingale methods in the online setting (Vovk et al. [22 ] ; Volkhonskiy et al. [21 ] ).
The goal of this paper is to localize the changepoint efficiently while quantifying uncertainty in its location. Likelihood-based approaches assume specific parametric families, such as Gaussian mean-shift or linear regression models, and derive point estimators and confidence intervals through likelihood theory (Kim and Siegmund [10 ] ; Quandt [16 ] ; Gurevich and Vexler [7 ] ).
Other approaches derive localization guarantees through asymptotic theory, including SMUCE (Frick et al. [5 ] ) and regression-based methods (Xu et al. (2024)). Bootstrap approaches (Cho and Kirch [2 ] ) quantify uncertainty in changepoint estimates but generally lack finite-sample validity and can be computationally intensive.
However, these classical approaches do not meet the requirements of modern applications. Today, data are complex and often scarce, and therefore may not satisfy the model assumptions or justify the large-sample approximations required by these approaches. This motivates the distribution-free formulation outlined in Definition 1. Building on conformal p p p -values, recent works (Dandapanthula and Ramdas [3 ] ; Hore and Ramdas [9 ] ) have developed such changepoint localization frameworks with provable finite-sample, distribution-free coverage guarantees. These approaches start from a score function to measure the plausibility of a change at each time point and construct a confidence set by testing, for each candidate location t ∈ [ n − 1 ] t \in[n - 1] t ∈ [ n − 1 ] , whether t t t is the true changepoint, retaining the locations that are not rejected.
These conformal frameworks do not immediately provide uncertainty quantification around an existing changepoint estimate. In predictive inference, by contrast, conformal methods are commonly viewed as calibration wrappers: they take a black-box prediction algorithm and quantify uncertainty around its predictions. Since the existing conformal localization approaches rely on n − 1 n - 1 n − 1 separate tests, one for each candidate location, it is not immediately clear how to wrap them around existing point estimates.
Preview of our approach: CLONE
A natural way to calibrate an existing changepoint estimate is to construct a confidence interval around it with distribution-free coverage for the true changepoint, thereby quantifying uncertainty in the estimate.
Suppose we are given a preliminary changepoint estimate ξ ^ \hat{\xi} ξ ^ . We consider nested intervals around it with decreasing radii, eventually reaching the singleton { ξ ^ } \{\hat{\xi}\} { ξ ^ } . Starting from the full range of candidate locations, we test exchangeability in successively smaller windows and continue shrinking whenever the test rejects. The intuition is simple: if the true changepoint ξ \xi ξ lies outside a proposed interval, the associated window is homogeneous, so its exchangeability test should typically not reject. We return the preceding interval at the first non-rejection, or the singleton set if every test rejects. We call our proposed method Changepoint LOcalization via Nested Exchangeability tests (CLONE). An illustration of the different hypothesis tests considered by existing conformal frameworks and our proposal is given in Figure 1 .
Figure 1. A schematic comparison of the hypotheses tested: green and blue points indicate the true pre- and post-change segments, with changepoint ξ \xi ξ and reference estimate ξ ^ \hat{\xi} ξ ^ . On the left, we have the hypotheses tested by Hore and Ramdas [9 ] ; Dandapanthula and Ramdas [3 ] . For each candidate t t t , the null asserts that the two disjoint segments determined by t t t are independent and each exchangeable; the shaded regions mark these segments. On the right is our proposal: for each radius R R R , CLONE tests whether the observations in the associated window around ξ ^ \hat{\xi} ξ ^ are exchangeable. The pink regions illustrate nested windows, parametrized by radius R R R .
The use of nested intervals around a point estimate has previously appeared in the conformal literature. In predictive inference, Gupta et al. [6 ] consider nested intervals around a point estimate and calibrate them efficiently to produce valid prediction intervals for the unseen test response. There, the nested conformal prediction intervals help measure the uncertainty around the initial estimate. Likewise, CLONE provides uncertainty quantification for any given black-box changepoint estimator. A preview of the CLONE framework is given in Figure 2 , where the confidence sets are contiguous intervals around the changepoint estimates and cover the true changepoint ξ \xi ξ in most simulations.
Figure 2. Gaussian mean shift localization with n = 200 n = 200 n = 200 , ξ = 100 \xi= 100 ξ = 100 , and pre- and post-change distributions N ( 0.5 , 1 ) \mathcal{N}(0.5, 1) N ( 0.5 , 1 ) and N ( − 0.5 , 1 ) \mathcal{N}(-0.5, 1) N ( − 0.5 , 1 ) , respectively. Left: a simulated sequence with the true changepoint (dashed), the reference estimate (dash-dotted), and the 90% CLONE confidence interval (shaded). Right: CLONE intervals across ten simulations, with green points marking the corresponding reference estimates. CLONE quantifies uncertainty around each reference estimate through a contiguous confidence interval.
Our contributions
The main contributions of this work are summarized below:
We formally describe the CLONE construction and establish its finite-sample validity. This coverage guarantee holds for any score used to test exchangeability within each window, providing the analyst with flexibility in designing their score. With a radius grid that shrinks geometrically, CLONE requires only O ( log n ) O(\log n) O ( log n ) permutation tests.
An efficient score results in tight confidence intervals. We characterize optimal scores for the individual exchangeability tests in CLONE and give practical recommendations for approximating these scores.
(iii) We establish asymptotic sharpness of CLONE confidence intervals for general scores in the i.i.d. changepoint model through an interpretable signal-to-noise ratio, without requiring consistent estimation of the underlying densities. When the pre- and post-change marginals are known, the CLONE construction attains the rate given by the information-theoretic lower bound on cardinality.
Organization of the paper. The rest of the paper is organized as follows. In § 2 , we introduce CLONE and establish its finite-sample validity. In § 3 , we develop optimal and practical scores for the exchangeability tests and derive asymptotic localization rates. In § 4 , we present simulations and experiments on image and text data. In § 5 , we review CONCH and consider its interval hull as a baseline for comparison. We establish the same localization rate for the hull and show that, in the oracle setting, both methods attain the rate given by the information-theoretic cardinality lower bound. We conclude with a discussion in § 6 . All proofs are deferred to the appendices.
Changepoint localization via nested exchangeability tests
In this section, we formally describe the CLONE framework. Inspired by the rich literature on split conformal prediction [14 ] , we adopt a split conformal approach to changepoint localization. We compute the reference estimate on one split and use the remaining observations for conformal calibration.
A random split need not place observations from both segments in each split. To preserve the temporal ordering and ensure that both splits contain a change, we use interlaced sample splitting. We assume throughout this paper that the changepoint is away from the boundaries, i.e., ξ ∉ { 1 , n − 1 } \xi\notin\{1,n-1\} ξ ∈ / { 1 , n − 1 } , so that both subsequences contain a change. We write T = { 2 , … , n − 2 } \mathcal{T}=\{2,\ldots,n-2\} T = { 2 , … , n − 2 } to denote the set of possible changepoint locations. Specifically, write m = ⌊ n / 2 ⌋ m=\lfloor n/2\rfloor m = ⌊ n /2 ⌋ and form the interlaced splits
D n , 1 = ( X 2 i − 1 , n ) i = 1 ⌈ n / 2 ⌉ , D n , 2 = Y n = ( Y 1 , n , … , Y m , n ) , Y i , n = X 2 i , n . (1) D_{n,1}=(X_{2i-1,n})_{i=1}^{\lceil n/2\rceil},\qquad D_{n,2}=\mathbf{Y}_n=(Y_{1,n},\ldots,Y_{m,n}),\qquad Y_{i,n}=X_{2i,n}. \tag*{(1)} D n , 1 = ( X 2 i − 1 , n ) i = 1 ⌈ n /2 ⌉ , D n , 2 = Y n = ( Y 1 , n , … , Y m , n ) , Y i , n = X 2 i , n . (1)
Their changepoint indices are ξ ′ ′ = ⌈ ξ / 2 ⌉ \xi^{\prime\prime}=\lceil\xi/2\rceil ξ ′′ = ⌈ ξ /2 ⌉ and ξ ′ = ⌊ ξ / 2 ⌋ \xi^\prime=\lfloor\xi/2\rfloor ξ ′ = ⌊ ξ /2 ⌋ , respectively, with ∣ ξ ′ ′ − ξ ′ ∣ ≤ 1 |\xi^{\prime\prime}-\xi^\prime|\leq1 ∣ ξ ′′ − ξ ′ ∣ ≤ 1 . We refer to D n , 1 D_{n,1} D n , 1 and D n , 2 D_{n,2} D n , 2 as the training and calibration splits, respectively.
First, we use D n , 1 D_{n,1} D n , 1 to learn a reference estimate ξ ^ n / 2 ∈ [ m − 1 ] \widehat{\xi}_{n/2}\in[m-1] ξ n /2 ∈ [ m − 1 ] . We write ξ ^ n / 2 \widehat{\xi}_{n/2} ξ n /2 to explicitly encode the dependence of the estimate on approximately half of the data.
Next, we calibrate ξ ^ n / 2 \widehat{\xi}_{n/2} ξ n /2 on the calibration split by considering nested intervals around this estimate. For an integer radius R ≥ 0 R\geq0 R ≥ 0 , define
I R = { t ∈ [ m − 1 ] : ∣ t − ξ ^ n / 2 ∣ ≤ R } . (2) I_R=\{t\in[m-1]:|t-\widehat{\xi}_{n/2}|\leq R\}. \tag*{(2)} I R = { t ∈ [ m − 1 ] : ∣ t − ξ n /2 ∣ ≤ R } . (2)
If ξ ′ ∉ I R \xi^\prime\notin I_R ξ ′ ∈ / I R , then the observations ( Y L R , n , … , Y U R , n ) (Y_{L_R,n},\ldots,Y_{U_R,n}) ( Y L R , n , … , Y U R , n ) are exchangeable conditional on D n , 1 D_{n,1} D n , 1 , where L R = max { 1 , ξ ^ n / 2 − R } L_R=\max\{1,\widehat{\xi}_{n/2}-R\} L R = max { 1 , ξ n /2 − R } and U R = min { m , ξ ^ n / 2 + R + 1 } U_R=\min\{m,\widehat{\xi}_{n/2}+R+1\} U R = min { m , ξ n /2 + R + 1 } . This window contains $k_R=U_R-L_R+1\leq 2 R + 2 2R+2 2 R + 2 observations and motivates hypotheses of the form
H 0 , I R : ( Y L R , n , … , Y U R , n ) is exchangeable conditional on D n , 1 . \mathcal{H}_{0,I_R}: (Y_{L_R,n},\ldots,Y_{U_R,n})\text{ is exchangeable conditional on }D_{n,1}. H 0 , I R : ( Y L R , n , … , Y U R , n ) is exchangeable conditional on D n , 1 .
Consider a strictly decreasing integer sequence R 0 > R 1 > ⋯ > R J = 0 R_0>R_1>\cdots>R_J=0 R 0 > R 1 > ⋯ > R J = 0 , which may be chosen based on the training split D n , 1 D_{n,1} D n , 1 , where R 0 = max { ξ ^ n / 2 , m − 1 − ξ ^ n / 2 } R_0=\max\{\widehat{\xi}_{n/2},m-1-\widehat{\xi}_{n/2}\} R 0 = max { ξ n /2 , m − 1 − ξ n /2 } . By construction, I R 0 = [ m − 1 ] I_{R_0}=[m-1] I R 0 = [ m − 1 ] always contains ξ ′ \xi' ξ ′ . Moreover, the hypotheses H 0 , I R \mathcal{H}_{0,I_R} H 0 , I R are nested in R R R : if R 1 < R 2 R_1<R_2 R 1 < R 2 and H 0 , I R 1 \mathcal{H}_{0,I_{R_1}} H 0 , I R 1 is false, then H 0 , I R 2 \mathcal{H}_{0,I_{R_2}} H 0 , I R 2 must also be false. We therefore test the windows in decreasing order of radius, stopping at the first non-rejection and retaining the preceding interval.
To test H 0 , I R \mathcal{H}_{0,I_R} H 0 , I R , we first define a window-specific score S R : X k R → R S_R:\mathcal{X}^{k_R}\to\mathbb{R} S R : X k R → R , which may depend on the training split, with larger values providing greater evidence against exchangeability. Define the conformal p p p -value
p w i n d o w , R = 1 ∣ S k R ∣ ∑ π ∈ S k R 1 { S R ( π ( Y L R , n , … , Y U R , n ) ) ≥ S R ( Y L R , n , … , Y U R , n ) } . (3) p_{\mathrm{window},R}=\frac{1}{\lvert S_{k_R}\rvert}\sum_{\pi\in S_{k_R}}\mathbb{1}\left\{S_R\left(\pi(Y_{L_R,n},\ldots,Y_{U_R,n})\right)\ge S_R(Y_{L_R,n},\ldots,Y_{U_R,n})\right\}. \tag*{(3)} p window , R = ∣ S k R ∣ 1 π ∈ S k R ∑ 1 { S R ( π ( Y L R , n , … , Y U R , n ) ) ≥ S R ( Y L R , n , … , Y U R , n ) } . (3)
where we write S k R S_{k_R} S k R to denote the permutation group on k R k_R k R items. Define the stopping rule
j ^ α = min ( { j ∈ [ J ] : p w i n d o w , R j > α } ∪ { J + 1 } ) . \widehat{j}_{\alpha}=\min\left(\{j\in[J]:p_{\mathrm{window},R_j}>\alpha\}\cup\{J+1\}\right). j α = min ( { j ∈ [ J ] : p window , R j > α } ∪ { J + 1 } ) .
We return the calibration confidence interval I R j ^ α − 1 I_{R_{\widehat{j}_{\alpha}-1}} I R j α − 1 . If p w i n d o w , R j ≤ α p_{\mathrm{window},R_j}\le\alpha p window , R j ≤ α for every j ∈ [ J ] j\in[J] j ∈ [ J ] , then j ^ α = J + 1 \widehat{j}_{\alpha}=J+1 j α = J + 1 , resulting in the singleton calibration interval I 0 = { ξ ^ n / 2 } I_0=\{\widehat{\xi}_{n/2}\} I 0 = { ξ n /2 } .
This gives a confidence interval on the calibration subsequence. To map back to the original timeline, let B t = { 2 t , 2 t + 1 } B_t=\{2t,2t+1\} B t = { 2 t , 2 t + 1 } for t ∈ [ m − 1 ] t\in[m-1] t ∈ [ m − 1 ] and observe that ξ ∈ B ξ ′ \xi\in B_{\xi'} ξ ∈ B ξ ′ by construction. We report the resulting confidence interval
I n , 1 − α C L O N E = ⋃ t ∈ I R j ^ α − 1 B t . (4) I^{\mathrm{CLONE}}_{n,1-\alpha}=\bigcup_{t\in I_{R_{\widehat{j}_{\alpha}-1}}}B_t. \tag*{(4)} I n , 1 − α CLONE = t ∈ I R j α − 1 ⋃ B t . (4)
The procedure is summarized in Algorithm 1.
Theorem 2.1 (Finite-sample coverage). Fix α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and ξ ∈ T \xi\in\mathcal{T} ξ ∈ T . The CLONE confidence interval defined in Algorithm 1 satisfies
P X ∼ P ( ξ ∈ I n , 1 − α C L O N E ) ≥ 1 − α , (5) \mathbb{P}_{X\sim P}\left(\xi\in I^{\mathrm{CLONE}}_{n,1-\alpha}\right)\ge1-\alpha, \tag*{(5)} P X ∼ P ( ξ ∈ I n , 1 − α CLONE ) ≥ 1 − α , (5) for every distribution P P P with a changepoint at ξ \xi ξ and satisfying Assumption 1.
For large windows, enumerating the permutation group S k R S_{k_R} S k R to compute (3) can be impractical. However, one need not enumerate all permutations in S k R S_{k_R} S k R to compute a valid conformal p p p -value. Instead, one may use Monte Carlo calibration: for each tested window, draw fresh π 1 , … , π B ∼ i i d Unif ( S k R ) \pi_1,\ldots,\pi_B\mathrel{\overset{\mathrm{iid}}{\sim}}\operatorname{Unif}(S_{k_R}) π 1 , … , π B ∼ iid Unif ( S k R ) , independently of the observed data X \mathbf{X} X , and compute
p ^ w i n d o w , R = 1 B + 1 ( 1 + ∑ k = 1 B 1 { S R ( π k ( Y L R , n , … , Y U R , n ) ) ≥ S R ( Y L R , n , … , Y U R , n ) } ) . (6) \widehat{p}_{\mathrm{window},R}=\frac{1}{B+1}\left(1+\sum_{k=1}^{B}\mathbb{1}\left\{S_R\left(\pi_k(Y_{L_R,n},\ldots,Y_{U_R,n})\right)\ge S_R(Y_{L_R,n},\ldots,Y_{U_R,n})\right\}\right). \tag*{(6)} p window , R = B + 1 1 ( 1 + k = 1 ∑ B 1 { S R ( π k ( Y L R , n , … , Y U R , n ) ) ≥ S R ( Y L R , n , … , Y U R , n ) } ) . (6)
Algorithm 1: CLONE: changepoint localization via nested exchangeability tests
Input: Calibration sequence $\mathbf{Y}_n$; training-based reference $\hat{\xi}_{n/2}$, radius sequence $R_0 > \cdots > R_J = 0$, and window scores $S_R$; level $\alpha$.
Output: A confidence interval on the original timeline.
1 $\hat{j}_{\alpha} \leftarrow J+1$;
2 for $j=1,\ldots,J$ do
3 Compute $p_{\mathrm{window},R_j}$ using {xref}`(2.3)`;
4 if $p_{\mathrm{window},R_j}>\alpha$ then
5 $\hat{j}_{\alpha}\leftarrow j$;
6 break;
7 end
8 end
9 $I_{n,1-\alpha}^{\mathrm{CLONE}}\leftarrow\bigcup_{t\in I_{B_{\hat{j}_{\alpha-1}}}}B_t$;
10 return $I_{n,1-\alpha}^{\mathrm{CLONE}}$;
The finite-sample coverage guarantee continues to hold with these Monte Carlo p p p -values.
Corollary 2.2. Under the assumptions of Theorem 2.1 , fix B ≥ 1 B\ge1 B ≥ 1 and replace p w i n d o w , R j p_{\mathrm{window},R_j} p window , R j in Algorithm 1 by p ^ w i n d o w , R j \hat{p}_{\mathrm{window},R_j} p ^ window , R j from (6) . The returned confidence interval satisfies (5) , where probability is taken over both the data X \mathbf{X} X and the sampled permutations.
The validity guarantees of CLONE intervals hold for any window-specific score functions, offering great flexibility in score design. The choice of score still affects the width of the CLONE interval. Before studying this in detail, we make a few remarks.
Designing scores for CLONE
An efficient window-specific score can lead to more powerful tests of exchangeability and thus narrower confidence intervals. In this section, we derive an expression for the optimal score and give practical approximations.
Optimal window-specific scores
To obtain an expression for an optimal score, we specialize to the i.i.d. changepoint model. Suppose that the pre-change observations X 1 , … , X ξ X_1,\ldots,X_{\xi} X 1 , … , X ξ are drawn i.i.d. from a density f 0 f_0 f 0 and the post-change observations X ξ + 1 , … , X n X_{\xi+1},\ldots,X_n X ξ + 1 , … , X n are drawn i.i.d. from a density f 1 f_1 f 1 , with f 0 ≠ f 1 f_0 \ne f_1 f 0 = f 1 . We assume that the corresponding distributions are mutually absolutely continuous.
We write H 0 , ξ \mathcal{H}_{0,\xi} H 0 , ξ to denote the hypothesis that Assumption 1 holds with a changepoint at ξ \xi ξ . The corresponding calibration changepoint is at ξ ′ \xi' ξ ′ . We write P ξ \mathbb{P}_{\xi} P ξ and E ξ \mathbb{E}_{\xi} E ξ for probability and expectation under a joint distribution satisfying Assumption 1 with a changepoint at ξ \xi ξ .
To obtain a narrow confidence interval, a powerful window-specific score should reject H 0 , I R \mathcal{H}_{0,I_R} H 0 , I R whenever the calibration changepoint ξ ′ \xi' ξ ′ belongs to I R I_R I R . Write j ⋆ = max { j ∈ { 0 , … , J } : ξ ′ ∈ I R j } j_\star= \max\{j \in\{0,\ldots,J\} : \xi' \in I_{R_j}\} j ⋆ = max { j ∈ { 0 , … , J } : ξ ′ ∈ I R j } for the largest index whose interval contains the calibration changepoint. One natural strategy for finding an optimal score is to consider the following objective:
E ξ [ ∑ j = 1 j ⋆ 1 { p w i n d o w , R j ( S R j ) ≤ α } ∣ D n , 1 ] = ∑ j = 1 j ⋆ P ξ ( p w i n d o w , R j ( S R j ) ≤ α ∣ D n , 1 ) . \mathbb{E}_{\xi}\left[\left.\sum_{j=1}^{j_\star}\mathbb{1}\{p_{\mathrm{window},R_j}(S_{R_j})\leq\alpha\}\right|D_{n,1}\right]=\sum_{j=1}^{j_\star}\mathbb{P}_{\xi}\left(p_{\mathrm{window},R_j}(S_{R_j})\leq\alpha\mid D_{n,1}\right). E ξ [ j = 1 ∑ j ⋆ 1 { p window , R j ( S R j ) ≤ α } D n , 1 ] = j = 1 ∑ j ⋆ P ξ ( p window , R j ( S R j ) ≤ α ∣ D n , 1 ) .
where p w i n d o w , R ( S R ) p_{\mathrm{window},R}(S_R) p window , R ( S R ) denotes the conformal p p p -value in (3) computed with the window-specific score S R S_R S R . This objective can be interpreted as the expected number of correct rejections over the j ⋆ j_\star j ⋆ nested hypotheses and serves as a surrogate for the final interval width.
Theorem 3.1. Consider the setting and notation defined above. Fix an integer R ≥ 0 R \geq0 R ≥ 0 and suppose ξ ′ ∈ I R \xi' \in I_R ξ ′ ∈ I R . Conditional on D n , 1 D_{n,1} D n , 1 and the unordered observations { Y L R , n , … , Y U R , n } \{Y_{L_R,n},\ldots,Y_{U_R,n}\} { Y L R , n , … , Y U R , n } , a most powerful level-α \alpha α test of H 0 , I R \mathcal{H}_{0,I_R} H 0 , I R against the alternative H 0 , ξ \mathcal{H}_{0,\xi} H 0 , ξ rejects for large values of
S R ⋆ ( Y L R , n , … , Y U R , n ) = ∑ i = L R ξ ′ ℓ ( Y i , n ) , where ℓ = log ( f 0 / f 1 ) , (8) S_R^\star(Y_{L_R,n},\ldots,Y_{U_R,n})=\sum_{i=L_R}^{\xi'}\ell(Y_{i,n}),\qquad\text{where }\ell=\log(f_0/f_1), \tag*{(8)} S R ⋆ ( Y L R , n , … , Y U R , n ) = i = L R ∑ ξ ′ ℓ ( Y i , n ) , where ℓ = log ( f 0 / f 1 ) , (8) where an empty sum equals zero. Consequently, using the conformal p p p -value (7) to attain the Type I error level α \alpha α exactly, we have, for any collection of window-specific scores ( S R j ) j (S_{R_j})_j ( S R j ) j ,
E ξ [ ∑ j = 1 j ⋆ 1 { p ˉ w i n d o w , R j ( S R j ) ≤ α } ∣ D n , 1 ] ≤ E ξ [ ∑ j = 1 j ⋆ 1 { p ˉ w i n d o w , R j ( S R j ⋆ ) ≤ α } ∣ D n , 1 ] . \mathbb{E}_{\xi}\left[\left.\sum_{j=1}^{j_\star}\mathbb{1}\{\bar{p}_{\mathrm{window},R_j}(S_{R_j})\leq\alpha\}\right|D_{n,1}\right]\leq\mathbb{E}_{\xi}\left[\left.\sum_{j=1}^{j_\star}\mathbb{1}\{\bar{p}_{\mathrm{window},R_j}(S^\star_{R_j})\leq\alpha\}\right|D_{n,1}\right]. E ξ [ j = 1 ∑ j ⋆ 1 { p ˉ window , R j ( S R j ) ≤ α } D n , 1 ] ≤ E ξ [ j = 1 ∑ j ⋆ 1 { p ˉ window , R j ( S R j ⋆ ) ≤ α } D n , 1 ] . Therefore, S R ⋆ S_R^\star S R ⋆ is the optimal score for the individual exchangeability test underlying the CLONE framework, but it requires knowledge of both the log-likelihood ratio ℓ \ell ℓ and the cali-
bration changepoint ξ ′ \xi' ξ ′ , which are unknown in practice. Nevertheless, it motivates concrete and practical window-specific score constructions. We discuss these choices next.
Practical window-specific scores
In practice, we first replace ξ ′ \xi' ξ ′ by the reference estimate ξ ^ n / 2 \hat{\xi}_{n/2} ξ ^ n /2 computed on the training split D n , 1 D_{n,1} D n , 1 :
ξ ^ n / 2 ∈ argmax s ∈ [ m − 1 ] ∑ i = 1 s ℓ ( X 2 i − 1 , n ) . \hat{\xi}_{n/2} \in\operatorname*{argmax}_{s \in[m-1]} \sum_{i=1}^{s} \ell(X_{2i-1,n}). ξ ^ n /2 ∈ s ∈ [ m − 1 ] argmax i = 1 ∑ s ℓ ( X 2 i − 1 , n ) .
Recalling that ℓ = log ( f 0 / f 1 ) \ell= \log(f_0/f_1) ℓ = log ( f 0 / f 1 ) , one can observe that ξ ^ n / 2 \hat{\xi}_{n/2} ξ ^ n /2 is essentially a maximum likelihood estimate (MLE) of the changepoint on the training split. We write ξ ^ n / 2 \hat{\xi}_{n/2} ξ ^ n /2 to explicitly encode the dependence of the estimate on approximately half of the data. This gives the score ∑ i = L R ξ ^ n / 2 ℓ ( Y i , n ) \sum_{i=L_R}^{\hat{\xi}_{n/2}} \ell(Y_{i,n}) ∑ i = L R ξ ^ n /2 ℓ ( Y i , n ) , which can be used when the oracle log-likelihood ratio ℓ \ell ℓ is known. We refer to this score as the oracle LLR window score in this and later sections.
By construction, we always have L R ≤ ξ ^ n / 2 < U R L_R \le\hat{\xi}_{n/2} < U_R L R ≤ ξ ^ n /2 < U R . Since the total window sum is unchanged by permutation, the oracle score ∑ i = L R ξ ^ n / 2 ℓ ( Y i , n ) \sum_{i=L_R}^{\hat{\xi}_{n/2}} \ell(Y_{i,n}) ∑ i = L R ξ ^ n /2 ℓ ( Y i , n ) and the score
∑ i = L R ξ ^ n / 2 ℓ ( Y i , n ) ξ ^ n / 2 − L R + 1 − ∑ i = ξ ^ n / 2 + 1 U R ℓ ( Y i , n ) U R − ξ ^ n / 2 \frac{\sum_{i=L_R}^{\hat{\xi}_{n/2}} \ell(Y_{i,n})}{\hat{\xi}_{n/2}-L_R+1}
-
\frac{\sum_{i=\hat{\xi}_{n/2}+1}^{U_R} \ell(Y_{i,n})}{U_R-\hat{\xi}_{n/2}} ξ ^ n /2 − L R + 1 ∑ i = L R ξ ^ n /2 ℓ ( Y i , n ) − U R − ξ ^ n /2 ∑ i = ξ ^ n /2 + 1 U R ℓ ( Y i , n )
produce the same permutation p p p -values. The latter has a natural interpretation: it is the difference in mean log-likelihood ratio between the two segments in the current window, treating ξ ^ n / 2 \hat{\xi}_{n/2} ξ ^ n /2 as the changepoint. Both denominators are positive for every radius R ≥ 0 R \ge0 R ≥ 0 , and larger values indicate greater evidence of a change at the reference estimate. Henceforth, we use this mean-difference form throughout the remaining sections.
In practice, we will also not know ℓ \ell ℓ . Therefore, we may replace it by an estimate ℓ ^ n \hat{\ell}_n ℓ ^ n , which motivates the learned LLR window score
S R ( Y L R , n , … , Y U R , n ) = ∑ i = L R ξ ^ n / 2 ℓ ^ n ( Y i , n ) ξ ^ n / 2 − L R + 1 − ∑ i = ξ ^ n / 2 + 1 U R ℓ ^ n ( Y i , n ) U R − ξ ^ n / 2 . (9) S_R(Y_{L_R,n},\ldots,Y_{U_R,n}) =
\frac{\sum_{i=L_R}^{\hat{\xi}_{n/2}} \hat{\ell}_n(Y_{i,n})}{\hat{\xi}_{n/2}-L_R+1}
-
\frac{\sum_{i=\hat{\xi}_{n/2}+1}^{U_R} \hat{\ell}_n(Y_{i,n})}{U_R-\hat{\xi}_{n/2}}. \tag*{(9)} S R ( Y L R , n , … , Y U R , n ) = ξ ^ n /2 − L R + 1 ∑ i = L R ξ ^ n /2 ℓ ^ n ( Y i , n ) − U R − ξ ^ n /2 ∑ i = ξ ^ n /2 + 1 U R ℓ ^ n ( Y i , n ) . (9)
The reference estimate is correspondingly obtained by maximizing the learned-score partial sum ∑ i = 1 s ℓ ^ n ( X 2 i − 1 , n ) \sum_{i=1}^{s} \hat{\ell}_n(X_{2i-1,n}) ∑ i = 1 s ℓ ^ n ( X 2 i − 1 , n ) over s ∈ [ m − 1 ] s \in[m-1] s ∈ [ m − 1 ] . To obtain ℓ ^ n \hat{\ell}_n ℓ ^ n , one may first estimate the pre- and post-change densities f ^ 0 , n \hat{f}_{0,n} f ^ 0 , n and f ^ 1 , n \hat{f}_{1,n} f ^ 1 , n and take their log-likelihood ratio, using the training data alone or separate independent labeled data whenever available. Alternatively, one can learn ℓ ^ n \hat{\ell}_n ℓ ^ n directly by training a classifier that distinguishes between the estimated pre- and post-change segments and then using its logits as an estimate. Both the learned function ℓ ^ n \hat{\ell}_n ℓ ^ n and the reference estimate are held fixed during the conformal calibration on D n , 2 D_{n,2} D n , 2 .
Asymptotic sharpness of CLONE intervals
We now study the sharpness of CLONE confidence sets in an asymptotic setting. Specifically, consider a generalization of the i.i.d. changepoint model, with independent observations satisfying
X 1 , n , … , X ξ n , n ∼ i i d P 0 , n , X ξ n + 1 , n , … , X n , n ∼ i i d P 1 , n , (10) X_{1,n},\ldots,X_{\xi_n,n} \overset{\mathrm{iid}}{\sim} P_{0,n}, \qquad X_{\xi_n+1,n},\ldots,X_{n,n} \overset{\mathrm{iid}}{\sim} P_{1,n}, \tag*{(10)} X 1 , n , … , X ξ n , n ∼ iid P 0 , n , X ξ n + 1 , n , … , X n , n ∼ iid P 1 , n , (10)
where the pre- and post-change distributions may vary with the sample size. This allows local alternatives, under which P 0 , n P_{0,n} P 0 , n and P 1 , n P_{1,n} P 1 , n become increasingly similar as n → ∞ n \to\infty n → ∞ . We write f 0 , n f_{0,n} f 0 , n and f 1 , n f_{1,n} f 1 , n for their densities with respect to a common dominating measure, and ℓ n = log ( f 0 , n / f 1 , n ) \ell_n = \log(f_{0,n}/f_{1,n}) ℓ n = log ( f 0 , n / f 1 , n ) for the oracle log-likelihood ratio (LLR). As noted above, we do not require knowledge of ℓ n \ell_n ℓ n to compute the CLONE confidence interval and instead use an estimate ℓ ^ n \hat{\ell}_n ℓ ^ n in its place.
As before, we adopt interlaced sample splitting, dividing the sequence X n = ( X 1 , n , … , X n , n ) \mathbf{X}_n = (X_{1,n},\ldots,X_{n,n}) X n = ( X 1 , n , … , X n , n ) into the training split D n , 1 D_{n,1} D n , 1 and the calibration split D n , 2 D_{n,2} D n , 2 . Their changepoints are located at ξ n ′ ′ = ⌈ ξ n / 2 ⌉ \xi_n^{\prime\prime} = \lceil\xi_n/2 \rceil ξ n ′′ = ⌈ ξ n /2 ⌉ and ξ n ′ = ⌊ ξ n / 2 ⌋ \xi_n^{\prime} = \lfloor\xi_n/2 \rfloor ξ n ′ = ⌊ ξ n /2 ⌋ , respectively. For the asymptotic analysis in this section, we learn ℓ ^ n : X → R \hat{\ell}_n : \mathcal{X} \to\mathbb{R} ℓ ^ n : X → R from a separate dataset D n ′ D_n^{\prime} D n ′ that is independent of ( D n , 1 , D n , 2 ) (D_{n,1}, D_{n,2}) ( D n , 1 , D n , 2 ) . Any randomness used in learning ℓ ^ n \hat{\ell}_n ℓ ^ n is included in D n ′ D_n^{\prime} D n ′ . The asymptotic results below use the full-permutation p p p -value in (3) .
Using the training split D n , 1 D_{n,1} D n , 1 , we first define the reference estimate
ξ ^ n / 2 ∈ argmax s ∈ [ m − 1 ] ∑ i = 1 s ℓ ^ n ( X 2 i − 1 , n ) , (11) \hat{\xi}_{n/2} \in\underset{s \in[m-1]}{\operatorname{argmax}} \sum_{i=1}^{s} \hat{\ell}_n(X_{2i-1,n}), \tag*{(11)} ξ ^ n /2 ∈ s ∈ [ m − 1 ] argmax i = 1 ∑ s ℓ ^ n ( X 2 i − 1 , n ) , (11)
with a fixed measurable rule for resolving ties. Conditional on ( D n ′ , D n , 1 ) (D_n^{\prime}, D_{n,1}) ( D n ′ , D n , 1 ) , both ℓ ^ n \hat{\ell}_n ℓ ^ n and ξ ^ n / 2 \hat{\xi}_{n/2} ξ ^ n /2 are fixed. We then compute the conformal p p p -values on D n , 2 D_{n,2} D n , 2 using the window-specific score S R S_R S R defined in (9) and construct the CLONE confidence interval.
To state the result, we introduce some notation. For j ∈ { 0 , 1 } j \in\{0,1\} j ∈ { 0 , 1 } , define the unconditional score moments μ j , n = E D n ′ , X ∼ P j , n [ ℓ ^ n ( X ) ] \mu_{j,n} = \mathbb{E}_{D_n^{\prime}, X \sim P_{j,n}}[\hat{\ell}_n(X)] μ j , n = E D n ′ , X ∼ P j , n [ ℓ ^ n ( X )] and σ j , n 2 = Var D n ′ , X ∼ P j , n ( ℓ ^ n ( X ) ) \sigma_{j,n}^{2} = \operatorname{Var}_{D_n^{\prime}, X \sim P_{j,n}}(\hat{\ell}_n(X)) σ j , n 2 = Var D n ′ , X ∼ P j , n ( ℓ ^ n ( X )) , where X X X is drawn independently of D n ′ D_n^{\prime} D n ′ . These moments account for both the randomness of the learned function and variation within the pre- or post-change segments. To establish the sharpness guarantees, we impose the following conditions.
Assumption 2. We assume that
(i) The changepoint location sequence ( ξ n ) n (\xi_n)_n ( ξ n ) n satisfies ξ n / n → τ ∈ ( 0 , 1 ) \xi_n/n \to\tau\in(0,1) ξ n / n → τ ∈ ( 0 , 1 ) .
(ii) There exists κ ∈ ( 0 , 1 / 2 ] \kappa\in(0,1/2] κ ∈ ( 0 , 1/2 ] such that, for all sufficiently large n n n , μ 0 , n > 0 > μ 1 , n \mu_{0,n} > 0 > \mu_{1,n} μ 0 , n > 0 > μ 1 , n and
μ 0 , n ∧ ( − μ 1 , n ) ≥ κ ( μ 0 , n − μ 1 , n ) . (12) \mu_{0,n} \wedge(-\mu_{1,n}) \ge\kappa(\mu_{0,n} - \mu_{1,n}). \tag*{(12)} μ 0 , n ∧ ( − μ 1 , n ) ≥ κ ( μ 0 , n − μ 1 , n ) . (12) Further, σ 0 , n 2 , σ 1 , n 2 < ∞ \sigma_{0,n}^{2}, \sigma_{1,n}^{2} < \infty σ 0 , n 2 , σ 1 , n 2 < ∞ for every n n n .
(iii) ℓ ^ n \hat{\ell}_n ℓ ^ n satisfies the following stability condition: as n → ∞ n \to\infty n → ∞ ,
ε n : = Var D n ′ ( E X ∼ P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) + Var D n ′ ( E X ∼ P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) ( μ 0 , n − μ 1 , n ) 2 ⟶ 0. (13) \varepsilon_n := \frac{\operatorname{Var}_{D'_n}\left(\mathbb{E}_{X \sim P_{0,n}}\left[\hat{\ell}_n(X) \mid D'_n\right]\right) + \operatorname{Var}_{D'_n}\left(\mathbb{E}_{X \sim P_{1,n}}\left[\hat{\ell}_n(X) \mid D'_n\right]\right)}{(\mu_{0,n} - \mu_{1,n})^2} \longrightarrow0. \tag*{(13)} ε n := ( μ 0 , n − μ 1 , n ) 2 Var D n ′ ( E X ∼ P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) + Var D n ′ ( E X ∼ P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) ⟶ 0. (13)
Condition (i) is a mild assumption on the changepoint location. It ensures that the changepoint stays away from the boundaries of the timeline, so that both pre- and post-change segments cover a non-vanishing fraction of the sequence.
Condition (ii) is an assumption on the quality of the score ℓ ^ n \hat{\ell}_n ℓ ^ n . While it may not accurately estimate the oracle LLR, it should distinguish the two segments in expectation: pre-change observations receive a positive mean score, while post-change observations receive a negative mean score. The gap μ 0 , n − μ 1 , n \mu_{0,n} - \mu_{1,n} μ 0 , n − μ 1 , n measures the separation of the pre- and post-change distributions through ℓ ^ n \hat{\ell}_n ℓ ^ n , and the condition (12) requires each mean to be separated from zero by at least a fixed fraction of this gap.
Finally, condition (iii) controls the randomness introduced by ℓ ^ n \hat{\ell}_n ℓ ^ n . It requires the conditional pre- and post-change score means to have small variances relative to the square of the unconditional mean separation gap from condition (ii). If ℓ ^ n \hat{\ell}_n ℓ ^ n is deterministic, as with the oracle LLR, this condition is automatically satisfied.
Remark 3.1. For a fixed reference index, adding a deterministic constant to ℓ ^ n \hat{\ell}_n ℓ ^ n leaves the CLONE p p p -values unchanged. Subtracting the population midpoint ( μ 0 , n + μ 1 , n ) / 2 (\mu_{0,n} + \mu_{1,n})/2 ( μ 0 , n + μ 1 , n ) /2 satisfies (12) with κ = 1 / 2 \kappa= 1/2 κ = 1/2 . However, this centering may change the reference estimate in (11) and the “maximum likelihood” interpretation attached to it.
Next, we define the signal-to-noise ratio (SNR) as
SNR n = μ 0 , n − μ 1 , n ( σ 0 , n 2 + σ 1 , n 2 ) 1 / 2 , (14) \operatorname{SNR}_n = \frac{\mu_{0,n} - \mu_{1,n}}{\left(\sigma_{0,n}^2 + \sigma_{1,n}^2\right)^{1/2}}, \tag*{(14)} SNR n = ( σ 0 , n 2 + σ 1 , n 2 ) 1/2 μ 0 , n − μ 1 , n , (14)
with SNR n = + ∞ \operatorname{SNR}_n = +\infty SNR n = + ∞ when the denominator is zero. The corresponding localization scale appearing in the results below is r n = 1 ∨ SNR n − 2 r_n = 1 \vee\operatorname{SNR}_n^{-2} r n = 1 ∨ SNR n − 2 . A weaker mean separation or greater score variability increases r n r_n r n , as one would naturally expect. Under local alternatives, this scale may diverge. The following proposition shows that the reference estimate localizes the changepoint at this scale.
Proposition 3.2. Under the model (10) and Assumption 2 , for all sufficiently large n n n and every integer u ≥ 2 u \ge2 u ≥ 2 ,
P ( ∣ ξ ^ n / 2 − ξ n ′ ∣ > u ) ≤ 4 ε n κ 2 + 4 κ 2 ( u − 1 ) σ 0 , n 2 + σ 1 , n 2 ( μ 0 , n − μ 1 , n ) 2 . (15) \mathbb{P}\left(\left|\hat{\xi}_{n/2} - \xi'_n\right| > u\right) \le\frac{4\varepsilon_n}{\kappa^2} + \frac{4}{\kappa^2(u-1)}\frac{\sigma_{0,n}^2 + \sigma_{1,n}^2}{(\mu_{0,n} - \mu_{1,n})^2}. \tag*{(15)} P ( ξ ^ n /2 − ξ n ′ > u ) ≤ κ 2 4 ε n + κ 2 ( u − 1 ) 4 ( μ 0 , n − μ 1 , n ) 2 σ 0 , n 2 + σ 1 , n 2 . (15) Consequently, ∣ ξ ^ n / 2 − ξ n ′ ∣ = O P ( r n ) \left|\hat{\xi}_{n/2} - \xi'_n\right| = O_{\mathbb{P}}(r_n) ξ ^ n /2 − ξ n ′ = O P ( r n ) and ∣ 2 ξ ^ n / 2 − ξ n ∣ = O P ( r n ) \left|2\hat{\xi}_{n/2} - \xi_n\right| = O_{\mathbb{P}}(r_n) 2 ξ ^ n /2 − ξ n = O P ( r n ) .
The next theorem establishes the same localization rate for the CLONE interval. As stated earlier in Remark 2.2, we use the geometric radius sequence R j + 1 = ⌊ R j / 2 ⌋ R_{j+1} = \lfloor R_j/2 \rfloor R j + 1 = ⌊ R j /2 ⌋ , starting from R 0 = max { ξ ^ n / 2 , m − 1 − ξ ^ n / 2 } R_0 = \max\{\hat{\xi}_{n/2}, m - 1 - \hat{\xi}_{n/2}\} R 0 = max { ξ ^ n /2 , m − 1 − ξ ^ n /2 } and continuing until zero is reached.
Theorem 3.3. Under the model (10) and the construction defined above, suppose Assumption 2 holds, with r n / n → 0 r_n/n \to0 r n / n → 0 . Then, for every fixed α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
∣ I n , 1 − α C L O N E ∣ = O P ( r n ) , ∣ I n , 1 − α C L O N E ∣ n − 1 → P 0. (16) \lvert I^{\mathrm{CLONE}}_{n,1-\alpha}\rvert= O_{\mathbb{P}}(r_n), \qquad\frac{\lvert I^{\mathrm{CLONE}}_{n,1-\alpha}\rvert}{n-1} \xrightarrow{\mathbb{P}} 0. \tag*{(16)} ∣ I n , 1 − α CLONE ∣ = O P ( r n ) , n − 1 ∣ I n , 1 − α CLONE ∣ P 0. (16) Thus, under the stated assumptions, S N R n ≫ n − 1 / 2 \mathrm{SNR}_n \gg n^{-1/2} SNR n ≫ n − 1/2 ensures that the CLONE intervals have asymptotically vanishing normalized length.
Experiments
We now evaluate CLONE in simulated and real data experiments. Throughout, we use interlaced sample splitting, a target confidence level of 90%, and a radius grid that halves at each shrinking step. Each Monte Carlo p p p -value uses 1000 sampled permutations.
Gaussian mean shift localization
We start by evaluating CLONE in the Gaussian mean shift setting. We observe n = 500 n = 500 n = 500 independent samples with a changepoint at ξ = 250 \xi= 250 ξ = 250 . The pre- and post-change distributions are N ( δ , 1 ) \mathcal{N}(\delta,1) N ( δ , 1 ) and N ( − δ , 1 ) \mathcal{N}(-\delta,1) N ( − δ , 1 ) , respectively, with δ ∈ { 0.1 , 0.2 , 0.3 , 0.4 , 0.6 , 0.8 , 1 } \delta\in\{0.1,0.2,0.3,0.4,0.6,0.8,1\} δ ∈ { 0.1 , 0.2 , 0.3 , 0.4 , 0.6 , 0.8 , 1 } . Smaller δ \delta δ corresponds to a weaker change, which is harder to localize. As δ \delta δ increases, we thus expect narrower confidence intervals.
We estimate the reference changepoint on the odd split by maximum likelihood and use the estimated segments to learn the densities. We then use the learned LLR window score for conformal calibration on the even split. We simulate 200 independent sequences at each δ \delta δ .
Our findings are summarized in Figure 3 . In the left panel, we show boxplots of empirical coverage at each δ \delta δ . Average empirical coverage is at least 90% in these simulations, in line with the theoretical guarantee. In the middle panel, we plot the average interval width with Monte Carlo standard errors. As δ \delta δ increases, CLONE returns narrower intervals. In the rightmost panel, we fix δ = 0.5 \delta= 0.5 δ = 0.5 and plot intervals from ten simulated sequences, with green points marking the corresponding reference estimates.
Figure 3. Gaussian mean shift: CLONE maintains the nominal coverage and returns narrower intervals as the change strength increases. The intervals quantify uncertainty around the reference estimates, shown in green.
DomainNet: localizing domain shift
Next, we consider domain shift localization using the DomainNet dataset [15 ] . We simulate sequences of n = 800 n = 800 n = 800 images, with images from the real domain before ξ = 350 \xi= 350 ξ = 350 and the sketch domain afterward. All images are converted to grayscale to remove color cues and make localization more challenging.
We train a CNN with four blocks on an independent labeled sample and use the classifier logits to construct the learned LLR score. We estimate the reference changepoint from the odd-indexed observations and calibrate CLONE on the even split. We simulate ten sequences and compute the CLONE intervals at the 90% confidence level.
Figure 4 summarizes our findings. The left panel shows example images around the changepoint for one simulated sequence. The right panel plots the CLONE intervals from the ten sequences, zoomed to the range [ 300 , 400 ] [300, 400] [ 300 , 400 ] , with green points marking the corresponding reference estimates. The intervals remain narrow relative to the full timeline.
Figure 4. Domain shift localization: CLONE gives contiguous confidence intervals around the reference estimates, shown in green.
SST-2: localizing sentiment change
We next consider localizing sentiment changes using review snippets from the SST-2 dataset (Socher et al., [19 ] ). We observe a sequence containing n = 1000 n = 1000 n = 1000 reviews with a changepoint at ξ = 400 \xi= 400 ξ = 400 . Before the change, a review is positive with probability ( 1 + δ ) / 2 (1 + \delta)/2 ( 1 + δ ) /2 ; afterward, it is positive with probability ( 1 − δ ) / 2 (1 - \delta)/2 ( 1 − δ ) /2 . We vary δ ∈ { 0.1 , 0.2 , 0.3 , 0.4 , 0.6 , 0.8 , 1 } \delta\in\{0.1, 0.2, 0.3, 0.4, 0.6, 0.8, 1\} δ ∈ { 0.1 , 0.2 , 0.3 , 0.4 , 0.6 , 0.8 , 1 } and sample reviews independently with replacement from fixed positive and negative pools. Thus, δ \delta δ measures the difference in positive-review proportions between the segments. Examples of positive and negative review snippets follow.
t = 399 t = 399 t = 399 : “juicy writer”
t = 400 t = 400 t = 400 : “intricately structured and well-realized drama”
t = 401 t = 401 t = 401 : “painfully”
t = 402 t = 402 t = 402 : “than most of jaglom’s self-conscious and gratingly irritating films”
We use a pretrained DistilBERT model fine-tuned for sentiment classification (Sanh et al., [18 ] ), with its logits providing the learned LLR-type score. We simulate 100 sequences at each value of δ \delta δ , and compute the width of the CLONE intervals.
In the left panel of Figure 5 , we show CLONE intervals for three simulated sequences at each δ \delta δ , with green points marking the corresponding reference estimates. As expected, if the initial reference estimate is far from ξ \xi ξ , the corresponding CLONE interval tends to be wide. In the right panel, we plot the mean interval cardinality with 95% Monte Carlo confidence intervals. The intervals are large when the sentiment shift is weak, i.e., δ \delta δ is small.
Figure 5. Sentiment shift localization: CLONE intervals become narrower as sentiment separation increases, while quantifying uncertainty around the reference estimates shown in green.
An alternative: conformal changepoint localization
The CONCH framework of Hore and Ramdas [9 ] constructs distribution-free confidence sets by testing each candidate location separately and is a natural alternative for changepoint localization. A natural question is whether constructing intervals around the changepoint estimates reduces efficiency. We show that, with similarly constructed scores, CONCH attains the same localization rate as CLONE. When the oracle score ℓ \ell ℓ is known, both methods attain the rate given by the information-theoretic lower bound on cardinality.
The CONCH construction
The CONCH framework requires the user to specify two components: a changepoint plausibility score and a split permutation group. A changepoint plausibility (CPP) score is any measurable map S : X n × [ n − 1 ] → R S : \mathcal{X}^{n} \times[n-1] \to\mathbb{R} S : X n × [ n − 1 ] → R , where larger S ( X , t ) S(X,t) S ( X , t ) indicates greater plausibility of a change at t t t . Next, let S n \mathcal{S}_{n} S n be the permutation group on [ n ] [n] [ n ] and define Π t = { π ∈ S n : π ( [ t ] ) = [ t ] } \Pi_{t} = \{\pi\in\mathcal{S}_{n} : \pi([t]) = [t]\} Π t = { π ∈ S n : π ([ t ]) = [ t ]} . These permutations act on the observations on either side of t t t without mixing the segments. Writing π ( X ) = ( X π ( 1 ) , … , X π ( n ) ) \pi(X) = (X_{\pi(1)},\ldots,X_{\pi(n)}) π ( X ) = ( X π ( 1 ) , … , X π ( n ) ) , CONCH defines a conformal p p p -value for each t ∈ [ n − 1 ] t \in[n-1] t ∈ [ n − 1 ] by
p t = 1 ∣ Π t ∣ ∑ π ∈ Π t 1 { S ( π ( X ) , t ) ≤ S ( X , t ) } . (17) p_{t} = \frac{1}{\lvert\Pi_{t}\rvert} \sum_{\pi\in\Pi_{t}} \mathbb{1}\{S(\pi(X),t) \le S(X,t)\}. \tag*{(17)} p t = ∣ Π t ∣ 1 π ∈ Π t ∑ 1 { S ( π ( X ) , t ) ≤ S ( X , t )} . (17)
Under H 0 , t \mathcal{H}_{0,t} H 0 , t , p t p_{t} p t is a super-uniform random variable. Finally, one returns the time points where the CONCH p p p -values exceed α \alpha α , that is, C n , 1 − α C O N C H = { t ∈ [ n − 1 ] : p t > α } \mathcal{C}^{\mathrm{CONCH}}_{n,1-\alpha} = \{t \in[n-1] : p_{t} > \alpha\} C n , 1 − α CONCH = { t ∈ [ n − 1 ] : p t > α } . Under Assumption 1, we therefore have
P ξ ( ξ ∈ C n , 1 − α C O N C H ) ≥ 1 − α . (18) \mathbb{P}_{\xi}\left(\xi\in\mathcal{C}^{\mathrm{CONCH}}_{n,1-\alpha}\right) \ge1-\alpha. \tag*{(18)} P ξ ( ξ ∈ C n , 1 − α CONCH ) ≥ 1 − α . (18)
Further, we write C ˉ n , 1 − α C O N C H = [ min C n , 1 − α C O N C H , max C n , 1 − α C O N C H ] ∩ [ n − 1 ] \bar{C}^{\mathrm{CONCH}}_{n,1-\alpha} = [\min C^{\mathrm{CONCH}}_{n,1-\alpha}, \max C^{\mathrm{CONCH}}_{n,1-\alpha}] \cap[n-1] C ˉ n , 1 − α CONCH = [ min C n , 1 − α CONCH , max C n , 1 − α CONCH ] ∩ [ n − 1 ] for the interval hull of the CONCH confidence set, with C ˉ n , 1 − α C O N C H = ∅ \bar{C}^{\mathrm{CONCH}}_{n,1-\alpha} = \varnothing C ˉ n , 1 − α CONCH = ∅ when the set is empty. This hull also satisfies the same distribution-free coverage guarantee.
In practice, sample splitting is recommended, as for the CLONE confidence intervals. In particular, D n , 1 D_{n,1} D n , 1 is used to learn the score, and D n , 2 D_{n,2} D n , 2 is used for calibration. The original paper calls this implementation CONCH-SPLIT. For simplicity, we refer to it as CONCH here. For a formal description, see [9 Section 3.3] .
The authors further derive an expression for the optimal CPP score under the i.i.d. changepoint model and give practical recommendations for approximating it. These scores are similar to the LLR-type scores used for CLONE. As in CLONE, they use the training split D n , 1 D_{n,1} D n , 1 to obtain an LLR estimate ℓ ^ n : X → R \hat{\ell}_n : \mathcal{X} \to\mathbb{R} ℓ ^ n : X → R and compute the reference estimate
ξ ^ n / 2 ∈ argmax s ∈ [ m − 1 ] ∑ i = 1 s ℓ ^ n ( X 2 i − 1 , n ) , \hat{\xi}_{n/2} \in\underset{s \in[m-1]}{\operatorname{argmax}} \sum_{i=1}^{s} \hat{\ell}_n(X_{2i-1,n}), ξ ^ n /2 ∈ s ∈ [ m − 1 ] argmax i = 1 ∑ s ℓ ^ n ( X 2 i − 1 , n ) ,
and then define the learned LLR CPP score as
S n ( Y n , t ) = ∑ i = 1 t ℓ ^ n ( Y i , n ) − ∑ i = 1 ξ ^ n / 2 ℓ ^ n ( Y i , n ) . (19) S_n(Y_n,t) = \sum_{i=1}^{t} \hat{\ell}_n(Y_{i,n}) - \sum_{i=1}^{\hat{\xi}_{n/2}} \hat{\ell}_n(Y_{i,n}). \tag*{(19)} S n ( Y n , t ) = i = 1 ∑ t ℓ ^ n ( Y i , n ) − i = 1 ∑ ξ ^ n /2 ℓ ^ n ( Y i , n ) . (19)
This score is similar in spirit to the learned LLR window score, comparing the log-likelihood ratios of different segments. As before, ℓ ^ n \hat{\ell}_n ℓ ^ n may be obtained by estimating the two densities separately or by training a classifier and using its logits.
Localization rates for the CONCH interval hull
We use the asymptotic setting and Assumption 2 from § 3.3 , including the independent dataset D n ′ D'_n D n ′ and the reference estimate in (11) . The following theorem then characterizes the sharpness of both CONCH and its interval hull under the generalized i.i.d. changepoint model.
Theorem 5.1. Suppose the model (10) and Assumption 2 hold, with r n / n → 0 r_n/n \to0 r n / n → 0 . Then, for every fixed α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
lim M → ∞ lim sup n → ∞ P ( max t ∈ [ m − 1 ] ∣ t − ξ n ′ ∣ ≥ M r n p t , n > α ) = 0 , (20) \lim_{M \to\infty} \limsup_{n \to\infty} \mathbb{P}\left(\max_{\substack{t \in[m-1]\\ \lvert t-\xi'_n\rvert\ge M r_n}} p_{t,n} > \alpha\right)=0, \tag*{(20)} M → ∞ lim n → ∞ lim sup P t ∈ [ m − 1 ] ∣ t − ξ n ′ ∣ ≥ M r n max p t , n > α = 0 , (20) where the maximum over an empty index set is interpreted as zero. Consequently,
∣ C ‾ n , 1 − α C O N C H ∣ = O P ( r n ) , ∣ C ‾ n , 1 − α C O N C H ∣ n − 1 → P 0. (21) \left|\overline{\mathcal{C}}^{\mathrm{CONCH}}_{n,1-\alpha}\right| = O_{\mathbb{P}}(r_n),
\qquad
\frac{\left|\overline{\mathcal{C}}^{\mathrm{CONCH}}_{n,1-\alpha}\right|}{n-1} \xrightarrow{\mathbb{P}} 0. \tag*{(21)} C n , 1 − α CONCH = O P ( r n ) , n − 1 C n , 1 − α CONCH P 0. (21)
Theorem 5.1 strengthens the asymptotic sharpness guarantee in Hore and Ramdas [9 ] . Their result shows that the normalized cardinality of the CONCH confidence set vanishes, assuming that ℓ ^ n \hat{\ell}_n ℓ ^ n consistently estimates the oracle LLR ℓ n \ell_n ℓ n . We instead give a precise localization rate for general LLR-type CPP scores.
Therefore, CLONE and the CONCH interval hull attain the same localization rate. While CONCH performs O ( n ) O(n) O ( n ) separate permutation tests, CLONE uses only O ( log n ) O(\log n) O ( log n ) tests with geometric shrinking.
Empirical comparison between CLONE and CONCH: We return to the Gaussian mean shift setting from § 4.1 and compare the interval width and calibration time of CLONE and the CONCH hull. As explained earlier, both methods use the same interlaced split and similar learned LLR scores. We therefore exclude the shared training stage and compare only the time spent on conformal calibration on D n , 2 D_{n,2} D n , 2 . We take n = 500 n = 500 n = 500 and ξ = 250 \xi= 250 ξ = 250 and vary the change strength δ \delta δ as before to record the interval width. For calibration time, we fix δ = 0.5 \delta= 0.5 δ = 0.5 , set ξ = n / 2 \xi= n/2 ξ = n /2 , and vary n n n . Figure 6 illustrates the tradeoff: the CONCH hull gives narrower intervals in this experiment, whereas CLONE requires substantially less calibration time. Matching localization rates do not imply equal finite-sample widths, and CLONE offers a computationally efficient alternative.
Figure 6. Gaussian mean shift: in finite samples, CLONE intervals can be wider than the CONCH hull but require substantially less calibration time.
Oracle rates and information-theoretic optimality
We next specialize the sharpness results for CLONE and the CONCH hull to the oracle setting, where the oracle LLR ℓ ^ n = ℓ n \hat{\ell}_n = \ell_n ℓ ^ n = ℓ n is known. This enables us to write down the localization rate r n r_n r n in terms of the distributional gap between P 0 , n P_{0,n} P 0 , n and P 1 , n P_{1,n} P 1 , n .
We now define the symmetrized KL divergence, also known as Jeffreys divergence, by
J n = KL ( P 0 , n ∥ P 1 , n ) + KL ( P 1 , n ∥ P 0 , n ) . (22) J_n = \operatorname{KL}(P_{0,n}\mathbin{\|}P_{1,n}) + \operatorname{KL}(P_{1,n}\mathbin{\|}P_{0,n}). \tag*{(22)} J n = KL ( P 0 , n ∥ P 1 , n ) + KL ( P 1 , n ∥ P 0 , n ) . (22)
For the oracle LLR, μ 0 , n = KL ( P 0 , n ∥ P 1 , n ) \mu_{0,n} = \operatorname{KL}(P_{0,n}\mathbin\Vert P_{1,n}) μ 0 , n = KL ( P 0 , n ∥ P 1 , n ) and μ 1 , n = − KL ( P 1 , n ∥ P 0 , n ) \mu_{1,n} = -\operatorname{KL}(P_{1,n}\mathbin\Vert P_{0,n}) μ 1 , n = − KL ( P 1 , n ∥ P 0 , n ) . Thus, the mean separation in condition (ii) of Assumption 2 equals J n J_n J n , and the stability condition (iii) of Assumption 2 holds immediately with ε n = 0 \varepsilon_n = 0 ε n = 0 .
Corollary 5.2. Suppose ξ n / n → τ ∈ ( 0 , 1 ) \xi_n/n \to\tau\in(0,1) ξ n / n → τ ∈ ( 0 , 1 ) , both KL ( P 0 , n ∥ P 1 , n ) \operatorname{KL}(P_{0,n}\mathbin\Vert P_{1,n}) KL ( P 0 , n ∥ P 1 , n ) and KL ( P 1 , n ∥ P 0 , n ) \operatorname{KL}(P_{1,n}\mathbin\Vert P_{0,n}) KL ( P 1 , n ∥ P 0 , n ) are positive and finite, and, for fixed κ ∈ ( 0 , 1 / 2 ] \kappa\in(0,1/2] κ ∈ ( 0 , 1/2 ] and C v < ∞ C_v < \infty C v < ∞ ,
KL ( P 0 , n ∥ P 1 , n ) ∧ KL ( P 1 , n ∥ P 0 , n ) ≥ κ J n , max j = 0 , 1 Var P j , n ( ℓ n ( X ) ) ≤ C v J n . (23) \operatorname{KL}(P_{0,n}\mathbin\Vert P_{1,n}) \wedge\operatorname{KL}(P_{1,n}\mathbin\Vert P_{0,n}) \ge\kappa J_n,\qquad\max_{j=0,1}\operatorname{Var}_{P_{j,n}}(\ell_n(X)) \le C_vJ_n. \tag*{(23)} KL ( P 0 , n ∥ P 1 , n ) ∧ KL ( P 1 , n ∥ P 0 , n ) ≥ κ J n , j = 0 , 1 max Var P j , n ( ℓ n ( X )) ≤ C v J n . (23) If J n → 0 J_n \to0 J n → 0 and n J n → ∞ nJ_n \to\infty n J n → ∞ , then, with ℓ ^ n = ℓ n \widehat{\ell}_n = \ell_n ℓ n = ℓ n , for every fixed α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
∣ ξ ^ n / 2 − ξ ∣ = O P ( J n − 1 ) , ∣ C n , 1 − α C O N C H - S P L I T ∣ = O P ( J n − 1 ) , ∣ I n , 1 − α C L O N E ∣ = O P ( J n − 1 ) . (24) \left|\widehat{\xi}_{n/2} - \xi\right| = O_{\mathbb{P}}(J_n^{-1}),\qquad\left|\mathcal{C}^{\mathrm{CONCH\text{-}SPLIT}}_{n,1-\alpha}\right| = O_{\mathbb{P}}(J_n^{-1}),\qquad\left|I^{\mathrm{CLONE}}_{n,1-\alpha}\right| = O_{\mathbb{P}}(J_n^{-1}). \tag*{(24)} ξ n /2 − ξ = O P ( J n − 1 ) , C n , 1 − α CONCH - SPLIT = O P ( J n − 1 ) , I n , 1 − α CLONE = O P ( J n − 1 ) . (24) Thus, in the oracle setting, both confidence-set constructions share the information-based localization scale J n − 1 J_n^{-1} J n − 1 . In particular, this rate cannot be improved by a valid distribution-free confidence set.
For t ∈ [ n − 1 ] t \in[n-1] t ∈ [ n − 1 ] , let P t , n = P 0 , n ⊗ ξ n ⊗ P 1 , n ⊗ ( n − t ) \mathbb{P}_{t,n} = P_{0,n}^{\otimes\xi_n} \otimes P_{1,n}^{\otimes(n-t)} P t , n = P 0 , n ⊗ ξ n ⊗ P 1 , n ⊗ ( n − t ) . Fix α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and consider any distribution-free confidence set C ~ n ⊆ [ n − 1 ] \widetilde{\mathcal{C}}_n \subseteq[n-1] C n ⊆ [ n − 1 ] satisfying
P t , n ( t ∈ C ~ n ) ≥ 1 − α for every t ∈ T . (25) \mathbb{P}_{t,n}(t \in\widetilde{\mathcal{C}}_n) \ge1-\alpha\qquad\text{for every } t \in\mathcal{T}. \tag*{(25)} P t , n ( t ∈ C n ) ≥ 1 − α for every t ∈ T . (25)
We show that C ~ n \widetilde{\mathcal{C}}_n C n cannot have cardinality o ( J n − 1 ) o(J_n^{-1}) o ( J n − 1 ) .
Proposition 5.3 (A cardinality lower bound). Suppose ξ n / n → τ ∈ ( 0 , 1 ) \xi_n/n \to\tau\in(0,1) ξ n / n → τ ∈ ( 0 , 1 ) , the two KL divergences KL ( P 0 , n ∥ P 1 , n ) \operatorname{KL}(P_{0,n}\mathbin\Vert P_{1,n}) KL ( P 0 , n ∥ P 1 , n ) and KL ( P 1 , n ∥ P 0 , n ) \operatorname{KL}(P_{1,n}\mathbin\Vert P_{0,n}) KL ( P 1 , n ∥ P 0 , n ) are positive and finite, J n → 0 J_n \to0 J n → 0 , and n J n → ∞ nJ_n \to\infty n J n → ∞ . For every fixed
α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , there exist constants c α , p α > 0 c_\alpha,p_\alpha> 0 c α , p α > 0 such that every confidence set satisfying (25) obeys
lim inf n → ∞ P ξ n , n ( ∣ C ~ n ∣ ≥ c α J n ) ≥ p α . (26) \liminf_{n\to\infty} \mathbb{P}_{\xi_n,n}\left(\left|\widetilde{C}_n\right| \ge\frac{c_\alpha}{J_n}\right) \ge p_\alpha. \tag*{(26)} n → ∞ lim inf P ξ n , n ( C n ≥ J n c α ) ≥ p α . (26)
In particular, ∣ C ~ n ∣ = Ω P ( J n − 1 ) \left|\widetilde{C}_n\right| = \Omega_P\left(J_n^{-1}\right) C n = Ω P ( J n − 1 ) .
Together, Corollary 5.2 and Proposition 5.3 show that CLONE and the CONCH hull attain the optimal J n − 1 J_n^{-1} J n − 1 localization rate at any fixed confidence level.
Discussion
CLONE provides a distribution-free confidence interval around a pre-learned changepoint estimate by testing exchangeability in nested intervals centered at that estimate. The distribution-free finite-sample validity of CLONE allows flexibility in the choice of the preliminary estimate and window scores. With a geometrically shrinking radius grid, it requires only O ( log n ) O(\log n) O ( log n ) permutation tests, providing a significant computational gain relative to the existing frameworks. The localization results show that this computational advantage preserves the asymptotic localization order. The fixed-level oracle bounds further show that CLONE attains the rate given by the information-theoretic lower bound on cardinality. Extending this nested interval calibration approach to multiple changes and more general temporal dependence is a natural direction for future work.
Acknowledgment
An AI model was used during the preparation of this manuscript to assist with language editing, presentation, and coding. The authors are responsible for reviewing the technical content and conclusions.
Post-detection changepoint localization
In the previous sections, we have focused on localizing a changepoint, assuming that a non-trivial change exists. We now study the possibility of no change. In this case, a natural goal is for the framework to return an empty set with high probability.
CLONE framework offers a simple solution: first, we perform detection on the training split D n , 1 D_{n,1} D n , 1 . Let A ( D n , 1 ) A(D_{n,1}) A ( D n , 1 ) denote the resulting detection rule. We report the usual CLONE interval when A ( D n , 1 ) = 1 A(D_{n,1}) = 1 A ( D n , 1 ) = 1 and the empty set otherwise. Since the validity of CLONE established in Theorem 2.1 is proven conditional on D n , 1 D_{n,1} D n , 1 , even after this detection step, the coverage continues to hold. Consequently, whenever P ξ ( A ( D n , 1 ) = 1 ) > 0 \mathbb{P}_{\xi}(A(D_{n,1}) = 1) > 0 P ξ ( A ( D n , 1 ) = 1 ) > 0 ,
P ξ ( ξ ∈ I n , 1 − α C L O N E ∣ A ( D n , 1 ) = 1 ) ≥ 1 − α . \mathbb{P}_{\xi}\left(\xi\in I^{\mathrm{CLONE}}_{n,1-\alpha} \mid A(D_{n,1}) = 1\right) \ge1-\alpha. P ξ ( ξ ∈ I n , 1 − α CLONE ∣ A ( D n , 1 ) = 1 ) ≥ 1 − α .
If we instead want to use the whole sequence of observation X \mathbf{X} X for both detection and localization, modifying the full conformal implementation of CONCH suitably can answer that. We write H 0 , n \mathcal{H}_{0,n} H 0 , n to denote the no-change hypothesis, ξ = n \xi= n ξ = n . Hore and Ramdas [9 ] note that the no-change hypothesis H 0 , n \mathcal{H}_{0,n} H 0 , n can be accommodated within the CONCH framework by allowing ξ = n \xi= n ξ = n and separately testing exchangeability of the whole sequence. In particular, writing S ( ⋅ , n ) S(\cdot,n) S ( ⋅ , n ) for the plausibility score for no change, one can define the conformal p p p -value
p n = 1 ∣ S n ∣ ∑ π ∈ S n 1 { S ( π ( X ) , n ) ≤ S ( X , n ) } . (27) p_n = \frac{1}{|S_n|}\sum_{\pi\in S_n}\mathbb{1}\{S(\pi(\mathbf{X}),n)\le S(\mathbf{X},n)\}. \tag*{(27)} p n = ∣ S n ∣ 1 π ∈ S n ∑ 1 { S ( π ( X ) , n ) ≤ S ( X , n )} . (27)
The p p p -value p n p_n p n is valid under H 0 , n \mathcal{H}_{0,n} H 0 , n , as formally recorded below.
Proposition A.1 (Validity of the detection p p p -value). For any measurable score S ( ⋅ , n ) S(\cdot,n) S ( ⋅ , n ) , the p p p -value p n p_n p n defined in (A.1) satisfies P H 0 , n ( p n ≤ u ) ≤ u \mathbb{P}_{\mathcal{H}_{0,n}}(p_n\le u)\le u P H 0 , n ( p n ≤ u ) ≤ u for any u ∈ ( 0 , 1 ) u\in(0,1) u ∈ ( 0 , 1 ) . Consequently, for any detection level β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) , the rule A ( X ) = 1 { p n ≤ β } A(\mathbf{X})=\mathbb{1}\{p_n\le\beta\} A ( X ) = 1 { p n ≤ β } satisfies
P H 0 , n ( A ( X ) = 1 ) ≤ β . \mathbb{P}_{\mathcal{H}_{0,n}}(A(\mathbf{X})=1)\le\beta. P H 0 , n ( A ( X ) = 1 ) ≤ β .
One may therefore first test H 0 , n \mathcal{H}_{0,n} H 0 , n at a user-specified detection level β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) and return an empty set whenever p n > β p_n>\beta p n > β . Otherwise, if p n ≤ β p_n\le\beta p n ≤ β , one proceeds to localization. The CONCH p p p -values ( p t ) t ∈ [ n − 1 ] (p_t)_{t\in[n-1]} ( p t ) t ∈ [ n − 1 ] , however, need not remain valid conditional on this detection event.
One may further ask whether a separate detection step is needed: would the original CONCH set already be typically empty under H 0 , n \mathcal{H}_{0,n} H 0 , n ? The answer is no: the hypotheses H 0 , t \mathcal{H}_{0,t} H 0 , t specify independent, exchangeable segments but do not require their marginal distributions to differ. Under H 0 , n \mathcal{H}_{0,n} H 0 , n , the law of X \mathbf{X} X is invariant under every permutation in Π t \Pi_t Π t for each t ∈ [ n − 1 ] t\in[n-1] t ∈ [ n − 1 ] . Thus each p t p_t p t in (17) remains super-uniform, even though there is no changepoint to localize. In particular, for any CPP score,
E H 0 , n [ ∣ C n , 1 − α C O N C H ∣ ] = ∑ t = 1 n − 1 P H 0 , n ( p t > α ) ≥ ( 1 − α ) ( n − 1 ) . \mathbb{E}_{\mathcal{H}_{0,n}}\left[|C^{\mathrm{CONCH}}_{n,1-\alpha}|\right]
= \sum_{t=1}^{n-1}\mathbb{P}_{\mathcal{H}_{0,n}}(p_t>\alpha)
\ge(1-\alpha)(n-1). E H 0 , n [ ∣ C n , 1 − α CONCH ∣ ] = t = 1 ∑ n − 1 P H 0 , n ( p t > α ) ≥ ( 1 − α ) ( n − 1 ) .
The CONCH confidence set therefore has expected size of order n n n under no change. This is consistent with the ( n − 1 ) (n-1) ( n − 1 ) hypotheses that CONCH tests, but differs from the interpretation of an empty output as no detected change. A two-step procedure that reports coverage conditional on detection must therefore use conditionally valid calibration. We next describe how to modify CONCH to achieve this.
Detect-then-localize CONCH
Let A : X n → { 0 , 1 } A : \mathcal{X}^{n} \to\{0,1\} A : X n → { 0 , 1 } be any measurable changepoint detection rule, where A ( X ) = 1 A(\mathbf{X}) = 1 A ( X ) = 1 means that a change has been detected. For instance, the full-permutation p p p -value in (A.1) gives the rule A ( x ) = 1 { p n ( x ) ≤ β } A(\mathbf{x}) = \mathbb{1}\{p_n(\mathbf{x}) \le\beta\} A ( x ) = 1 { p n ( x ) ≤ β } for a detection level β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) . In general, any measurable detection rule may be used; a level-β \beta β rule additionally controls false reports under no change.
Suppose a change is detected in an observed sequence x \mathbf{x} x , so that A ( x ) = 1 A(\mathbf{x}) = 1 A ( x ) = 1 . Define
p t d e t ( x ) = ∑ π ∈ Π t 1 { A ( π ( x ) ) = 1 } 1 { S ( π ( x ) , t ) ≤ S ( x , t ) } ∑ π ∈ Π t 1 { A ( π ( x ) ) = 1 } . (28) p_t^{\mathrm{det}}(\mathbf{x}) =
\frac{\sum_{\pi\in\Pi_t}\mathbb{1}\{A(\pi(\mathbf{x}))=1\}\mathbb{1}\{S(\pi(\mathbf{x}),t)\le S(\mathbf{x},t)\}}
{\sum_{\pi\in\Pi_t}\mathbb{1}\{A(\pi(\mathbf{x}))=1\}}. \tag*{(28)} p t det ( x ) = ∑ π ∈ Π t 1 { A ( π ( x )) = 1 } ∑ π ∈ Π t 1 { A ( π ( x )) = 1 } 1 { S ( π ( x ) , t ) ≤ S ( x , t )} . (28)
The resulting procedure, DTL-CONCH, returns
C n , 1 − α D T L − C O N C H = { ∅ , A ( X ) = 0 , { t ∈ [ n − 1 ] : p t d e t ( X ) > α } , A ( X ) = 1. C_{n,1-\alpha}^{\mathrm{DTL-CONCH}} =
\begin{cases}
\varnothing, & A(\mathbf{X})=0,\\
\{t\in[n-1]:p_t^{\mathrm{det}}(\mathbf{X})>\alpha\}, & A(\mathbf{X})=1.
\end{cases} C n , 1 − α DTL − CONCH = { ∅ , { t ∈ [ n − 1 ] : p t det ( X ) > α } , A ( X ) = 0 , A ( X ) = 1.
Algorithm 2 records the full-permutation version of this procedure. On A ( x ) = 1 A(\mathbf{x}) = 1 A ( x ) = 1 , the denominator is positive because the identity permutation is retained. Although the retained permutations need not form a group, the p p p -values remain valid conditional on detection under their corresponding null hypotheses.
Theorem A.2. Fix α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . Suppose Assumption 1 holds at a changepoint ξ ∈ [ n − 1 ] \xi\in[n-1] ξ ∈ [ n − 1 ] . Then p ξ d e t ( X ) p_{\xi}^{\mathrm{det}}(\mathbf{X}) p ξ det ( X ) is super-uniform conditional on A ( X ) = 1 A(\mathbf{X}) = 1 A ( X ) = 1 , whenever the conditioning event has positive probability. In particular,
P ξ ( A ( X ) = 1 , ξ ∉ C n , 1 − α D T L − C O N C H ) ≤ α P ξ ( A ( X ) = 1 ) . (29) \mathbb{P}_{\xi}\left(A(\mathbf{X})=1,\ \xi\notin C_{n,1-\alpha}^{\mathrm{DTL-CONCH}}\right)
\le\alpha\mathbb{P}_{\xi}(A(\mathbf{X})=1). \tag*{(29)} P ξ ( A ( X ) = 1 , ξ ∈ / C n , 1 − α DTL − CONCH ) ≤ α P ξ ( A ( X ) = 1 ) . (29) Consequently, whenever P ξ ( A ( X ) = 1 ) > 0 \mathbb{P}_{\xi}(A(\mathbf{X})=1)>0 P ξ ( A ( X ) = 1 ) > 0 , we have P ξ ( ξ ∈ C n , 1 − α D T L − C O N C H ∣ A ( X ) = 1 ) ≥ 1 − α \mathbb{P}_{\xi}(\xi\in C_{n,1-\alpha}^{\mathrm{DTL-CONCH}}\mid A(\mathbf{X})=1)\ge1-\alpha P ξ ( ξ ∈ C n , 1 − α DTL − CONCH ∣ A ( X ) = 1 ) ≥ 1 − α .
Numerical simulations
We now evaluate DTL-CONCH in a Gaussian mean shift setting. Specifically, we observe independent X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n with X i ∼ N ( δ , 1 ) X_i\sim\mathcal{N}(\delta,1) X i ∼ N ( δ , 1 ) for i ≤ ξ i\le\xi i ≤ ξ and X i ∼ N ( − δ , 1 ) X_i\sim\mathcal{N}(-\delta,1) X i ∼ N ( − δ , 1 ) for i > ξ i>\xi i > ξ . Here, δ = 0 \delta=0 δ = 0 corresponds to no change, and for δ > 0 \delta>0 δ > 0 , the changepoint is ξ = n / 2 \xi=n/2 ξ = n /2 . Throughout, we use detection level β = 0.05 \beta=0.05 β = 0.05 and localization level α = 0.10 \alpha=0.10 α = 0.10 .
Algorithm 2: DTL-CONCH: localization conditional on detection
Input: Data X \mathbf{X} X ; detection rule A A A ; CPP score S S S ; confidence level α \alpha α .
Output: A changepoint confidence set.
if A ( X ) = 0 A(\mathbf{X}) = 0 A ( X ) = 0 then
return ∅ \varnothing ∅ ;
end
for t ∈ [ n − 1 ] t \in[n-1] t ∈ [ n − 1 ] do
Retain π ∈ Π t \pi\in\Pi_t π ∈ Π t for which A ( π ( X ) ) = 1 A(\pi(\mathbf{X})) = 1 A ( π ( X )) = 1 ;
Evaluate S ( π ( X ) , t ) S(\pi(\mathbf{X}),t) S ( π ( X ) , t ) on every retained permutation;
Compute p t d e t p_t^{\mathrm{det}} p t det using (A.2);
end
return { t ∈ [ n − 1 ] : p t d e t > α } \{t \in[n-1] : p_t^{\mathrm{det}} > \alpha\} { t ∈ [ n − 1 ] : p t det > α } ;
We use interlaced sample splitting: the odd subsequence is used to obtain a reference changepoint ξ ^ n / 2 \hat{\xi}_{n/2} ξ ^ n /2 by maximizing the absolute standardized CUSUM statistic, and to estimate Gaussian segment means and a common variance. The resulting learned LLR defines the CPP score on the even subsequence. For detection, we use the negative learned LLR partial sum at the reference estimate as the no-change plausibility score, and take p n ≤ β p_n \le\beta p n ≤ β as the detection event.
Figure 7 summarizes our findings. In the left panel, we show boxplots of the empirical false detection proportion across sample sizes n ∈ { 100 , 200 , 400 , 800 } n \in\{100, 200, 400, 800\} n ∈ { 100 , 200 , 400 , 800 } . The boxplots are centered near β = 0.05 \beta= 0.05 β = 0.05 , consistent with the theoretical bound on the false detection probability. In the middle panel, we plot the DTL-CONCH p p p -values computed from the even subsequence on the original timeline, for n = 400 n = 400 n = 400 and δ = 0.5 \delta= 0.5 δ = 0.5 . As expected, only locations near the true changepoint have p p p -values exceeding α \alpha α and are retained.
Figure 7. DTL-CONCH controls false detections under no change. When a change is detected, stronger signals yield more concentrated confidence sets.
Finally, the rightmost panel reports empirical confidence-set membership for n = 400 n = 400 n = 400 and δ ∈ { 0 , 0.1 , 0.2 , 0.3 , 0.4 , 0.6 , 0.8 , 1 } \delta\in\{0, 0.1, 0.2, 0.3, 0.4, 0.6, 0.8, 1\} δ ∈ { 0 , 0.1 , 0.2 , 0.3 , 0.4 , 0.6 , 0.8 , 1 } , using 100 independent sequences at each signal strength. As δ \delta δ increases, detection becomes more frequent and the confidence set concentrates around the true location.
Proofs
Proving validity of CLONE
Proof of Theorem 2.1
Throughout the proof, we condition on D n , 1 D_{n,1} D n , 1 , so that the reference estimate ξ ^ n / 2 \hat{\xi}_{n/2} ξ ^ n /2 and radius grid R 0 > ⋯ > R J R_0 > \cdots> R_J R 0 > ⋯ > R J are fixed. Let Y n , R = ( Y L R , n , … , Y U R , n ) \mathbf{Y}_{n,R} = (Y_{L_R,n},\ldots,Y_{U_R,n}) Y n , R = ( Y L R , n , … , Y U R , n ) . If ξ ′ ∉ I R \xi' \notin I_R ξ ′ ∈ / I R , then we must have ξ ′ < L R \xi' < L_R ξ ′ < L R or U R ≤ ξ ′ U_R \le\xi' U R ≤ ξ ′ . In either case, by Assumption 1, the vector Y n , R \mathbf{Y}_{n,R} Y n , R is exchangeable. Therefore, conditional on D n , 1 D_{n,1} D n , 1 , π ( Y n , R ) = d Y n , R \pi(\mathbf{Y}_{n,R}) \overset{d}{=} \mathbf{Y}_{n,R} π ( Y n , R ) = d Y n , R for every π ∈ S k R \pi\in\mathcal{S}_{k_R} π ∈ S k R .
For every x ∈ X k R \mathbf{x} \in\mathcal{X}^{k_R} x ∈ X k R and for π ∈ S k R \pi\in\mathcal{S}_{k_R} π ∈ S k R , we can write
p w i n d o w , R ( π ( x ) ) = 1 ∣ S k R ∣ ∑ σ ∈ S k R 1 { S R ( σ ( x ) ) ≥ S R ( π ( x ) ) } p_{\mathrm{window},R}(\pi(\mathbf{x})) = \frac{1}{|\mathcal{S}_{k_R}|} \sum_{\sigma\in\mathcal{S}_{k_R}} \mathbf{1}\{S_R(\sigma(\mathbf{x})) \ge S_R(\pi(\mathbf{x}))\} p window , R ( π ( x )) = ∣ S k R ∣ 1 σ ∈ S k R ∑ 1 { S R ( σ ( x )) ≥ S R ( π ( x ))}
Hence, by ([8 Lemma 3] ), we have
1 ∣ S k R ∣ ∑ π ∈ S k R 1 { p w i n d o w , R ( π ( x ) ) ≤ u } ≤ u , u ∈ ( 0 , 1 ) . \frac{1}{|\mathcal{S}_{k_R}|} \sum_{\pi\in\mathcal{S}_{k_R}} \mathbf{1}\{p_{\mathrm{window},R}(\pi(\mathbf{x})) \le u\} \le u,\qquad u \in(0,1). ∣ S k R ∣ 1 π ∈ S k R ∑ 1 { p window , R ( π ( x )) ≤ u } ≤ u , u ∈ ( 0 , 1 ) .
Consequently, it follows that
P ξ ( p w i n d o w , R ≤ u ∣ D n , 1 ) = 1 ∣ S k R ∣ ∑ π ∈ S k R P ξ ( p w i n d o w , R ( π ( Y n , R ) ) ≤ u ∣ D n , 1 ) = E ξ [ 1 ∣ S k R ∣ ∑ π ∈ S k R 1 { p w i n d o w , R ( π ( Y n , R ) ) ≤ u } ∣ D n , 1 ] ≤ u . \begin{aligned}
\mathbb{P}_{\xi}(p_{\mathrm{window},R} \le u \mid D_{n,1}) = \frac{1}{|\mathcal{S}_{k_R}|} \sum_{\pi\in\mathcal{S}_{k_R}} \mathbb{P}_{\xi}(p_{\mathrm{window},R}(\pi(\mathbf{Y}_{n,R})) \le u \mid D_{n,1}) \\
&= \mathbb{E}_{\xi}\left[\left.\frac{1}{|\mathcal{S}_{k_R}|} \sum_{\pi\in\mathcal{S}_{k_R}} \mathbf{1}\{p_{\mathrm{window},R}(\pi(\mathbf{Y}_{n,R})) \le u\}\right|D_{n,1}\right] \le u.
\end{aligned} P ξ ( p window , R ≤ u ∣ D n , 1 ) = ∣ S k R ∣ 1 π ∈ S k R ∑ P ξ ( p window , R ( π ( Y n , R )) ≤ u ∣ D n , 1 ) = E ξ ∣ S k R ∣ 1 π ∈ S k R ∑ 1 { p window , R ( π ( Y n , R )) ≤ u } D n , 1 ≤ u .
By definition, j ^ α = min ( { j ∈ [ J ] : p w i n d o w , R j > α } ∪ { J + 1 } ) \hat{j}_{\alpha} = \min(\{j \in[J] : p_{\mathrm{window},R_j} > \alpha\} \cup\{J+1\}) j ^ α = min ({ j ∈ [ J ] : p window , R j > α } ∪ { J + 1 }) and on D n , 2 D_{n,2} D n , 2 , we return I R j ^ α − 1 I_{R_{\hat{j}_{\alpha}-1}} I R j ^ α − 1 . If ξ ′ ∈ I R J \xi' \in I_{R_J} ξ ′ ∈ I R J , nestedness of the intervals immediately gives ξ ′ ∈ I R j ^ α − 1 \xi' \in I_{R_{\hat{j}_{\alpha}-1}} ξ ′ ∈ I R j ^ α − 1 . Otherwise, define
j ∗ = min { j ∈ [ J ] : ξ ′ ∉ I R j } . j_* = \min\{j \in[J] : \xi' \notin I_{R_j}\}. j ∗ = min { j ∈ [ J ] : ξ ′ ∈ / I R j } .
Since I R 0 I_{R_0} I R 0 contains every calibration time point, j ∗ ≥ 1 j_* \ge1 j ∗ ≥ 1 , and
{ ξ ′ ∉ I R j ^ α − 1 } = { j ^ α > j ∗ } = ⋂ j = 1 j ∗ { p w i n d o w , R j ≤ α } ⊆ { p w i n d o w , R j ∗ ≤ α } . \{\xi' \notin I_{R_{\hat{j}_{\alpha}-1}}\} = \{\hat{j}_{\alpha} > j_*\} = \bigcap_{j=1}^{j_*}\{p_{\mathrm{window},R_j} \le\alpha\} \subseteq\{p_{\mathrm{window},R_{j_*}} \le\alpha\}. { ξ ′ ∈ / I R j ^ α − 1 } = { j ^ α > j ∗ } = j = 1 ⋂ j ∗ { p window , R j ≤ α } ⊆ { p window , R j ∗ ≤ α } .
The index j ∗ j_* j ∗ is fixed conditional on D n , 1 D_{n,1} D n , 1 and ξ ′ ∉ I R j ∗ \xi' \notin I_{R_{j_*}} ξ ′ ∈ / I R j ∗ . Hence,
P ξ ( ξ ′ ∉ I R j ^ α − 1 ∣ D n , 1 ) ≤ P ξ ( p w i n d o w , R j ∗ ≤ α ∣ D n , 1 ) ≤ α . \mathbb{P}_{\xi}(\xi' \notin I_{R_{\hat{j}_{\alpha}-1}} \mid D_{n,1}) \le\mathbb{P}_{\xi}(p_{\mathrm{window},R_{j_*}} \le\alpha\mid D_{n,1}) \le\alpha. P ξ ( ξ ′ ∈ / I R j ^ α − 1 ∣ D n , 1 ) ≤ P ξ ( p window , R j ∗ ≤ α ∣ D n , 1 ) ≤ α .
Taking expectations and using ξ ∈ B ξ ′ \xi\in B_{\xi'} ξ ∈ B ξ ′ proves (5) . □ \square □
Proof of Corollary 2.2
The proof follows the same approach as in the proof of Theorem 2.1 . Fix any R ∈ N ∪ { 0 } R \in\mathbb{N} \cup\{0\} R ∈ N ∪ { 0 } . Under the null H 0 , I R \mathcal{H}_{0,I_R} H 0 , I R , conditional on D n , 1 D_{n,1} D n , 1 and the unordered window { Y L R , n , … , Y U R , n } \{Y_{L_R,n},\ldots,Y_{U_R,n}\} { Y L R , n , … , Y U R , n } , the observed score S R ( Y L R , n , … , Y U R , n ) S_R(Y_{L_R,n},\ldots,Y_{U_R,n}) S R ( Y L R , n , … , Y U R , n ) and its B B B randomly permuted counterparts are exchangeable. Thus, following the arguments in the proof of Theorem 2.1 , for any u ∈ ( 0 , 1 ) u \in(0,1) u ∈ ( 0 , 1 ) ,
P ( p ^ w i n d o w , R ≤ u ∣ D n , 1 ) ≤ ⌊ ( B + 1 ) u ⌋ B + 1 ≤ u . \mathbb{P}(\hat{p}_{\mathrm{window},R} \leq u \mid D_{n,1}) \leq\frac{\lfloor(B+1)u \rfloor}{B+1} \leq u. P ( p ^ window , R ≤ u ∣ D n , 1 ) ≤ B + 1 ⌊( B + 1 ) u ⌋ ≤ u .
Here the probability is taken over both the randomness of the sampled permutations and the data sequence X \mathbf{X} X .
Writing j ∗ j^* j ∗ for the first index for which ξ ′ ∉ I R j ∗ \xi' \notin I_{R_{j^*}} ξ ′ ∈ / I R j ∗ , we obtain
P ( ξ ′ ∉ I R j ^ α − 1 ∣ D n , 1 ) ≤ P ( p ^ w i n d o w , R j ∗ ≤ α ∣ D n , 1 ) ≤ α . \mathbb{P}(\xi' \notin I_{R_{\hat{j}_{\alpha}-1}} \mid D_{n,1}) \leq\mathbb{P}(\hat{p}_{\mathrm{window},R_{j^*}} \leq\alpha\mid D_{n,1}) \leq\alpha. P ( ξ ′ ∈ / I R j ^ α − 1 ∣ D n , 1 ) ≤ P ( p ^ window , R j ∗ ≤ α ∣ D n , 1 ) ≤ α .
Taking expectations and mapping back to the full timeline through the sets B t B_t B t completes the proof.
For the randomized versions, conditional on the unordered window, the randomized rank is uniform under exchangeability. The same holds for the Monte Carlo version by exchangeability of the B + 1 B+1 B + 1 scores, with ties randomized independently. Replacing the super-uniform rank bound above by this uniform rank bound gives the same first-excluded-interval argument.
Proof of Theorem 3.1: Optimal score of CLONE
Throughout the proof, we condition on D n , 1 D_{n,1} D n , 1 and the unordered observations in the window { Y L R , n , … , Y U R , n } \{Y_{L_R,n},\ldots,Y_{U_R,n}\} { Y L R , n , … , Y U R , n } . Thus, the reference estimate ξ ^ n / 2 \hat{\xi}_{n/2} ξ ^ n /2 and radius sequence are fixed. Fix R R R with ξ ′ ∈ I R \xi' \in I_R ξ ′ ∈ I R .
Let Q 0 Q_0 Q 0 and Q ξ Q_\xi Q ξ denote the laws of ( Y L R , n , … , Y U R , n ) (Y_{L_R,n},\ldots,Y_{U_R,n}) ( Y L R , n , … , Y U R , n ) , conditional on D n , 1 D_{n,1} D n , 1 and { Y L R , n , … , Y U R , n } \{Y_{L_R,n},\ldots,Y_{U_R,n}\} { Y L R , n , … , Y U R , n } , under the exchangeability H 0 , I R \mathcal{H}_{0,I_R} H 0 , I R and the alternative H 0 , ξ \mathcal{H}_{0,\xi} H 0 , ξ respectively. Since under H 0 , I R \mathcal{H}_{0,I_R} H 0 , I R , every ordering is equally likely, Q 0 Q_0 Q 0 is essentially discrete uniform. Moreover, for an ordering y = ( y L R , … , y U R ) y=(y_{L_R},\ldots,y_{U_R}) y = ( y L R , … , y U R ) ,
d Q ξ d Q 0 ( y ) ∝ ∏ i = L R ξ ′ f 0 ( y i ) ∏ i = ξ ′ + 1 U R f 1 ( y i ) = { ∏ i = L R U R f 1 ( y i ) } exp { ∑ i = L R ξ ′ ℓ ( y i ) } ∝ exp { S R ∗ ( y ) } , \frac{\mathrm{d}Q_\xi}{\mathrm{d}Q_0}(y) \propto\prod_{i=L_R}^{\xi'} f_0(y_i)\prod_{i=\xi'+1}^{U_R} f_1(y_i)
= \left\{\prod_{i=L_R}^{U_R} f_1(y_i)\right\}\exp\left\{\sum_{i=L_R}^{\xi'} \ell(y_i)\right\} \propto\exp\{S_R^*(y)\}, d Q 0 d Q ξ ( y ) ∝ i = L R ∏ ξ ′ f 0 ( y i ) i = ξ ′ + 1 ∏ U R f 1 ( y i ) = { i = L R ∏ U R f 1 ( y i ) } exp ⎩ ⎨ ⎧ i = L R ∑ ξ ′ ℓ ( y i ) ⎭ ⎬ ⎫ ∝ exp { S R ∗ ( y )} ,
where an empty product is interpreted as one. The last proportionality holds since the term { ∏ i = L R U R f 1 ( y i ) } \left\{\prod_{i=L_R}^{U_R} f_1(y_i)\right\} { ∏ i = L R U R f 1 ( y i ) } is invariant to the ordering.
By the Neyman–Pearson lemma, therefore a most powerful conditional level-α \alpha α test rejects when S R ∗ > c S_R^*>c S R ∗ > c and randomizes when S R ∗ = c S_R^*=c S R ∗ = c , with rejection probability γ ∈ [ 0 , 1 ] \gamma\in[0,1] γ ∈ [ 0 , 1 ] chosen so that $Q_0(S_R^* > c ) + γ Q 0 ( S R ∗ = c ) = α c) + \gamma Q_0(S_R^* = c) = \alpha c ) + γ Q 0 ( S R ∗ = c ) = α . Equivalently, sampling V R ∼ Unif ( 0 , 1 ) V_R \sim\operatorname{Unif}(0,1) V R ∼ Unif ( 0 , 1 ) independent of the data, for any score S R S_R S R , its randomized permutation p p p -value can be given by
p w i n d o w , R ( S R ; y ) = Q 0 ( S R > S R ( y ) ) + V R Q 0 ( S R = S R ( y ) ) = 1 ∣ S k R ∣ ∑ π ∈ S k R 1 { S R ( π ( y L R , … , y U R ) ) > S R ( y L R , … , y U R ) } + V R ∣ S k R ∣ ∑ π ∈ S k R 1 { S R ( π ( y L R , … , y U R ) ) = S R ( y L R , … , y U R ) } . \begin{aligned}
p_{\mathrm{window},R}(S_R;y) = Q_0(S_R > S_R(y)) + V_R Q_0(S_R = S_R(y)) \\
&= \frac{1}{|S_{k_R}|} \sum_{\pi\in S_{k_R}} \mathbb{1}\left\{S_R\bigl(\pi(y_{L_R},\ldots,y_{U_R})\bigr) > S_R(y_{L_R},\ldots,y_{U_R})\right\} \\
&+ \frac{V_R}{|S_{k_R}|} \sum_{\pi\in S_{k_R}} \mathbb{1}\left\{S_R\bigl(\pi(y_{L_R},\ldots,y_{U_R})\bigr) = S_R(y_{L_R},\ldots,y_{U_R})\right\}.
\end{aligned} p window , R ( S R ; y ) = Q 0 ( S R > S R ( y )) + V R Q 0 ( S R = S R ( y )) = ∣ S k R ∣ 1 π ∈ S k R ∑ 1 { S R ( π ( y L R , … , y U R ) ) > S R ( y L R , … , y U R ) } + ∣ S k R ∣ V R π ∈ S k R ∑ 1 { S R ( π ( y L R , … , y U R ) ) = S R ( y L R , … , y U R ) } .
Consequently, from the above discussion, we obtain
Q ξ ( p w i n d o w , R ( S R ) ≤ α ) ≤ Q ξ ( p w i n d o w , R ( S R ∗ ) ≤ α ) . Q_{\xi}\bigl(p_{\mathrm{window},R}(S_R) \leq\alpha\bigr) \leq Q_{\xi}\bigl(p_{\mathrm{window},R}(S_R^*) \leq\alpha\bigr). Q ξ ( p window , R ( S R ) ≤ α ) ≤ Q ξ ( p window , R ( S R ∗ ) ≤ α ) .
This proves the first part.
For the second part, since j ∗ j_* j ∗ is fixed conditional on D n , 1 D_{n,1} D n , 1 and ξ ′ ∈ I R j \xi' \in I_{R_j} ξ ′ ∈ I R j for every j ≤ j ∗ j \leq j_* j ≤ j ∗ , averaging the preceding power inequality over { Y L R j , n , … , Y U R j , n } \{Y_{L_{R_j},n},\ldots,Y_{U_{R_j},n}\} { Y L R j , n , … , Y U R j , n } gives
P ξ ( p w i n d o w , R j ( S R j ) ≤ α ∣ D n , 1 ) ≤ P ξ ( p w i n d o w , R j ( S R j ∗ ) ≤ α ∣ D n , 1 ) . \mathbb{P}_{\xi}\left(p_{\mathrm{window},R_j}(S_{R_j}) \leq\alpha\mid D_{n,1}\right) \leq\mathbb{P}_{\xi}\left(p_{\mathrm{window},R_j}(S_{R_j}^*) \leq\alpha\mid D_{n,1}\right). P ξ ( p window , R j ( S R j ) ≤ α ∣ D n , 1 ) ≤ P ξ ( p window , R j ( S R j ∗ ) ≤ α ∣ D n , 1 ) .
Consequently, by linearity of conditional expectation,
E ξ [ ∑ j = 1 j ∗ 1 { p w i n d o w , R j ( S R j ) ≤ α } ∣ D n , 1 ] = ∑ j = 1 j ∗ P ξ ( p w i n d o w , R j ( S R j ) ≤ α ∣ D n , 1 ) ≤ ∑ j = 1 j ∗ P ξ ( p w i n d o w , R j ( S R j ∗ ) ≤ α ∣ D n , 1 ) = E ξ [ ∑ j = 1 j ∗ 1 { p w i n d o w , R j ( S R j ∗ ) ≤ α } ∣ D n , 1 ] , \begin{aligned}
\mathbb{E}_{\xi}\left[\left.\sum_{j=1}^{j_*}\mathbb{1}\left\{p_{\mathrm{window},R_j}(S_{R_j}) \leq\alpha\right\}\right|D_{n,1}\right]
= \sum_{j=1}^{j_*}\mathbb{P}_{\xi}\left(p_{\mathrm{window},R_j}(S_{R_j}) \leq\alpha\mid D_{n,1}\right) \\
&\leq\sum_{j=1}^{j_*}\mathbb{P}_{\xi}\left(p_{\mathrm{window},R_j}(S_{R_j}^*) \leq\alpha\mid D_{n,1}\right) \\
&= \mathbb{E}_{\xi}\left[\left.\sum_{j=1}^{j_*}\mathbb{1}\left\{p_{\mathrm{window},R_j}(S_{R_j}^*) \leq\alpha\right\}\right|D_{n,1}\right],
\end{aligned} E ξ [ j = 1 ∑ j ∗ 1 { p window , R j ( S R j ) ≤ α } D n , 1 ] = j = 1 ∑ j ∗ P ξ ( p window , R j ( S R j ) ≤ α ∣ D n , 1 ) ≤ j = 1 ∑ j ∗ P ξ ( p window , R j ( S R j ∗ ) ≤ α ∣ D n , 1 ) = E ξ [ j = 1 ∑ j ∗ 1 { p window , R j ( S R j ∗ ) ≤ α } D n , 1 ] ,
which proves the second part.
Localization of the reference estimate
Proof of Proposition 3.2
We start by defining the event
G n = { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ≥ μ 0 , n / 2 , E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ≤ μ 1 , n / 2 } . G_n = \left\{\mathbb{E}_{P_{0,n}}\left[\hat{\ell}_n(X)\mid D'_n\right] \geq\mu_{0,n}/2,\quad\mathbb{E}_{P_{1,n}}\left[\hat{\ell}_n(X)\mid D'_n\right] \leq\mu_{1,n}/2\right\}. G n = { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ≥ μ 0 , n /2 , E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ≤ μ 1 , n /2 } .
By Chebyshev’s inequality, we obtain
P ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ≤ μ 0 , n / 2 ) ≤ 4 Var D n ′ ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) μ 0 , n 2 , \mathbb{P}\left(\mathbb{E}_{P_{0,n}}\left[\hat{\ell}_n(X)\mid D'_n\right]\leq\mu_{0,n}/2\right)\leq\frac{4\operatorname{Var}_{D'_n}\left(\mathbb{E}_{P_{0,n}}\left[\hat{\ell}_n(X)\mid D'_n\right]\right)}{\mu_{0,n}^{2}}, P ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ≤ μ 0 , n /2 ) ≤ μ 0 , n 2 4 Var D n ′ ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) ,
and similarly,
P ( E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] > μ 1 , n / 2 ) ≤ 4 Var D n ′ ( E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) μ 1 , n 2 . \mathbb{P}\left(\mathbb{E}_{P_{1,n}}\left[\hat{\ell}_n(X)\mid D'_n\right]>\mu_{1,n}/2\right)\leq\frac{4\operatorname{Var}_{D'_n}\left(\mathbb{E}_{P_{1,n}}\left[\hat{\ell}_n(X)\mid D'_n\right]\right)}{\mu_{1,n}^{2}}. P ( E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] > μ 1 , n /2 ) ≤ μ 1 , n 2 4 Var D n ′ ( E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) .
Consequently, by Assumption 2(ii) and the definition of ε n \varepsilon_n ε n ,
P ( G n c ) ≤ 4 { Var D n ′ ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) μ 0 , n 2 + Var D n ′ ( E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) μ 1 , n 2 } ≤ 4 ε n κ 2 . (30) \mathbb{P}(G_n^c)\leq4\left\{\frac{\operatorname{Var}_{D'_n}\left(\mathbb{E}_{P_{0,n}}\left[\hat{\ell}_n(X)\mid D'_n\right]\right)}{\mu_{0,n}^{2}}+\frac{\operatorname{Var}_{D'_n}\left(\mathbb{E}_{P_{1,n}}\left[\hat{\ell}_n(X)\mid D'_n\right]\right)}{\mu_{1,n}^{2}}\right\}\leq\frac{4\varepsilon_n}{\kappa^2}. \tag*{(30)} P ( G n c ) ≤ 4 ⎩ ⎨ ⎧ μ 0 , n 2 Var D n ′ ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) + μ 1 , n 2 Var D n ′ ( E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) ⎭ ⎬ ⎫ ≤ κ 2 4 ε n . (30)
For sufficiently large n n n , Assumption 2(i) gives ξ n ′ ′ ∈ [ m − 1 ] \xi''_n\in[m-1] ξ n ′′ ∈ [ m − 1 ] . Thus, for every integer L ≥ 1 L\geq1 L ≥ 1 ,
{ ξ ^ n / 2 ≥ ξ n ′ ′ + L } ⊆ { max L ≤ l ≤ m − 1 − ξ n ′ ′ ∑ i = ξ n ′ ′ + 1 ξ n ′ ′ + l ℓ ^ n ( X 2 i − 1 , n ) ≥ 0 } . \{\hat{\xi}_{n/2}\geq\xi''_n+L\}\subseteq\left\{\max_{L\leq l\leq m-1-\xi''_n}\sum_{i=\xi''_n+1}^{\xi''_n+l}\hat{\ell}_n(X_{2i-1,n})\geq0\right\}. { ξ ^ n /2 ≥ ξ n ′′ + L } ⊆ ⎩ ⎨ ⎧ L ≤ l ≤ m − 1 − ξ n ′′ max i = ξ n ′′ + 1 ∑ ξ n ′′ + l ℓ ^ n ( X 2 i − 1 , n ) ≥ 0 ⎭ ⎬ ⎫ .
Conditional on D n ′ D'_n D n ′ , the observations in this sum are independent draws from P 1 , n P_{1,n} P 1 , n , and on G n G_n G n , each summand has conditional mean at most μ 1 , n / 2 \mu_{1,n}/2 μ 1 , n /2 . Therefore, on G n G_n G n , the first bound in Lemma B.1 gives
P ( ξ ^ n / 2 ≥ ξ n ′ ′ + L ∣ D n ′ ) ≤ P ( max L ≤ l ≤ m − 1 − ξ n ′ ′ 1 l ∑ i = ξ n ′ ′ + 1 ξ n ′ ′ + l { ℓ ^ n ( X 2 i − 1 , n ) − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } ≥ − μ 1 , n / 2 ∣ D n ′ ) ≤ 4 Var P 1 , n ( ℓ ^ n ( X ) ∣ D n ′ ) L μ 1 , n 2 . \begin{aligned}
\mathbb{P}\left(\hat{\xi}_{n/2}\geq\xi''_n+L\mid D'_n\right) \\
&\leq\mathbb{P}\left(\max_{L\leq l\leq m-1-\xi''_n}\frac{1}{l}\sum_{i=\xi''_n+1}^{\xi''_n+l}\left\{\hat{\ell}_n(X_{2i-1,n})-\mathbb{E}_{P_{1,n}}\left[\hat{\ell}_n(X)\mid D'_n\right]\right\}\geq-\mu_{1,n}/2\mid D'_n\right) \\
&\leq\frac{4\operatorname{Var}_{P_{1,n}}\left(\hat{\ell}_n(X)\mid D'_n\right)}{L\mu_{1,n}^{2}}.
\end{aligned} P ( ξ ^ n /2 ≥ ξ n ′′ + L ∣ D n ′ ) ≤ P L ≤ l ≤ m − 1 − ξ n ′′ max l 1 i = ξ n ′′ + 1 ∑ ξ n ′′ + l { ℓ ^ n ( X 2 i − 1 , n ) − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } ≥ − μ 1 , n /2 ∣ D n ′ ≤ L μ 1 , n 2 4 Var P 1 , n ( ℓ ^ n ( X ) ∣ D n ′ ) .
On G n G_n G n , an analogous argument gives
P ( ξ ^ n / 2 ≤ ξ n ′ ′ − L ∣ D n ′ ) ≤ 4 Var P 0 , n ( ℓ ^ n ( X ) ∣ D n ′ ) L μ 0 , n 2 . \mathbb{P}\left(\hat{\xi}_{n/2}\leq\xi''_n-L\mid D'_n\right)\leq\frac{4\operatorname{Var}_{P_{0,n}}\left(\hat{\ell}_n(X)\mid D'_n\right)}{L\mu_{0,n}^{2}}. P ( ξ ^ n /2 ≤ ξ n ′′ − L ∣ D n ′ ) ≤ L μ 0 , n 2 4 Var P 0 , n ( ℓ ^ n ( X ) ∣ D n ′ ) .
By the law of total variance,
E [ Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) ] ≤ σ j , n 2 , j ∈ { 0 , 1 } . \mathbb{E}\left[\operatorname{Var}_{P_{j,n}}\left(\hat{\ell}_n(X)\mid D'_n\right)\right]\leq\sigma_{j,n}^{2},\qquad j\in\{0,1\}. E [ Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) ] ≤ σ j , n 2 , j ∈ { 0 , 1 } .
Consequently, taking L = u − 1 L=u-1 L = u − 1 gives
P ( ∣ ξ ^ n / 2 − ξ n ′ ∣ > u ) ≤ P ( G n c ) + 4 u − 1 ( σ 0 , n 2 μ 0 , n 2 + σ 1 , n 2 μ 1 , n 2 ) . \mathbb{P}\left(\left|\hat{\xi}_{n/2}-\xi'_n\right|>u\right)\leq\mathbb{P}(G_n^c)+\frac{4}{u-1}\left(\frac{\sigma_{0,n}^{2}}{\mu_{0,n}^{2}}+\frac{\sigma_{1,n}^{2}}{\mu_{1,n}^{2}}\right). P ( ξ ^ n /2 − ξ n ′ > u ) ≤ P ( G n c ) + u − 1 4 ( μ 0 , n 2 σ 0 , n 2 + μ 1 , n 2 σ 1 , n 2 ) .
because ∣ ξ n ′ ′ − ξ n ′ ∣ ≤ 1 |\xi_n''-\xi_n'| \le1 ∣ ξ n ′′ − ξ n ′ ∣ ≤ 1 . This intermediate bound requires only μ 0 , n > 0 > μ 1 , n \mu_{0,n} > 0 > \mu_{1,n} μ 0 , n > 0 > μ 1 , n . By the balance condition in Assumption 2(ii),
σ 0 , n 2 μ 0 , n 2 + σ 1 , n 2 μ 1 , n 2 ≤ σ 0 , n 2 + σ 1 , n 2 κ 2 ( μ 0 , n − μ 1 , n ) 2 . \frac{\sigma_{0,n}^{2}}{\mu_{0,n}^{2}}+\frac{\sigma_{1,n}^{2}}{\mu_{1,n}^{2}} \le\frac{\sigma_{0,n}^{2}+\sigma_{1,n}^{2}}{\kappa^{2}(\mu_{0,n}-\mu_{1,n})^{2}}. μ 0 , n 2 σ 0 , n 2 + μ 1 , n 2 σ 1 , n 2 ≤ κ 2 ( μ 0 , n − μ 1 , n ) 2 σ 0 , n 2 + σ 1 , n 2 .
Combining this with (B.1) proves (15) . For u = ⌊ M r n ⌋ u=\lfloor Mr_n\rfloor u = ⌊ M r n ⌋ and M ≥ 4 M\ge4 M ≥ 4 , the resulting bound is at most 4 ϵ n / κ 2 + 8 / ( κ 2 M ) 4\epsilon_n/\kappa^2+8/(\kappa^2M) 4 ϵ n / κ 2 + 8/ ( κ 2 M ) . Thus
lim M → ∞ lim sup n → ∞ P ( ∣ ξ ^ n / 2 − ξ n ′ ∣ > M r n ) = 0. \lim_{M\to\infty}\limsup_{n\to\infty}\mathbb{P}\left(|\widehat{\xi}_{n/2}-\xi_n'|>Mr_n\right)=0. M → ∞ lim n → ∞ lim sup P ( ∣ ξ n /2 − ξ n ′ ∣ > M r n ) = 0.
Finally, ∣ 2 ξ ^ n / 2 − ξ n ∣ ≤ 2 ∣ ξ ^ n / 2 − ξ n ′ ∣ + 1 |2\widehat{\xi}_{n/2}-\xi_n|\le2|\widehat{\xi}_{n/2}-\xi_n'|+1 ∣2 ξ n /2 − ξ n ∣ ≤ 2∣ ξ n /2 − ξ n ′ ∣ + 1 , and r n ≥ 1 r_n\ge1 r n ≥ 1 . This proves the second part. □
Auxiliary lemma
Lemma B.1 (A maximal inequality). Let W 1 , … , W N W_1,\ldots,W_N W 1 , … , W N be independent, with E [ W i ] = 0 \mathbb{E}[W_i]=0 E [ W i ] = 0 and Var ( W i ) ≤ V \operatorname{Var}(W_i)\le V Var ( W i ) ≤ V for every i ∈ [ N ] i\in[N] i ∈ [ N ] . For integers N ≥ L ≥ 1 N\ge L\ge1 N ≥ L ≥ 1 and x > 0 x>0 x > 0 ,
P ( max L ≤ l ≤ N ∣ ∑ i = 1 l W i ∣ l ≥ x ) ≤ { V L x 2 , if the variables are i.i.d., 4 V L x 2 , in general. (31) \mathbb{P}\left(\max_{L\le l\le N}\frac{\left|\sum_{i=1}^{l}W_i\right|}{l}\ge x\right)\le
\begin{cases}
\frac{V}{Lx^2}, & \text{if the variables are i.i.d.,}\\
\frac{4V}{Lx^2}, & \text{in general.}
\end{cases} \tag*{(31)} P L ≤ l ≤ N max l ∑ i = 1 l W i ≥ x ≤ { L x 2 V , L x 2 4 V , if the variables are i.i.d., in general. (31)
Proof. For the i.i.d. bound, see Ramdas and Manole, [17 ] . The proof of the general result is as follows.
We start by observing that by union bound,
P ( max L ≤ l ≤ N ∣ ∑ i = 1 l W i ∣ l ≥ x ) ≤ ∑ j ≥ 0 2 j L ≤ N P ( max 2 j L ≤ l ≤ min { 2 j + 1 L , N } ∣ ∑ i = 1 l W i ∣ l ≥ x ) . \mathbb{P}\left(\max_{L\le l\le N}\frac{\left|\sum_{i=1}^{l}W_i\right|}{l}\ge x\right)\le\sum_{\substack{j\ge0\\2^jL\le N}}\mathbb{P}\left(\max_{2^jL\le l\le\min\{2^{j+1}L,N\}}\frac{\left|\sum_{i=1}^{l}W_i\right|}{l}\ge x\right). P L ≤ l ≤ N max l ∑ i = 1 l W i ≥ x ≤ j ≥ 0 2 j L ≤ N ∑ P 2 j L ≤ l ≤ m i n { 2 j + 1 L , N } max l ∑ i = 1 l W i ≥ x .
Now, fix any j ≥ 0 j\ge0 j ≥ 0 , and note that for 2 j L ≤ l < 2 j + 1 L 2^jL\le l<2^{j+1}L 2 j L ≤ l < 2 j + 1 L ,
{ ∣ ∑ i = 1 l W i ∣ l ≥ x } ⟹ { ∣ ∑ i = 1 l W i ∣ ≥ 2 j L x } . \left\{\frac{\left|\sum_{i=1}^{l}W_i\right|}{l}\ge x\right\}\Longrightarrow\left\{\left|\sum_{i=1}^{l}W_i\right|\ge2^jLx\right\}. ⎩ ⎨ ⎧ l ∑ i = 1 l W i ≥ x ⎭ ⎬ ⎫ ⟹ { i = 1 ∑ l W i ≥ 2 j Lx } .
Consequently, Kolmogorov’s inequality gives
P ( max 1 ≤ l ≤ min { 2 j + 1 L , N } ∣ ∑ i = 1 l W i ∣ ≥ 2 j L x ) ≤ 2 j + 1 L V ( 2 j L x ) 2 = 2 1 − j V L x 2 . \mathbb{P}\left(\max_{1\le l\le\min\{2^{j+1}L,N\}}\left|\sum_{i=1}^{l}W_i\right|\ge2^jLx\right)\le\frac{2^{j+1}LV}{(2^jLx)^2}=\frac{2^{1-j}V}{Lx^2}. P ( 1 ≤ l ≤ m i n { 2 j + 1 L , N } max i = 1 ∑ l W i ≥ 2 j Lx ) ≤ ( 2 j Lx ) 2 2 j + 1 L V = L x 2 2 1 − j V .
Consequently, we obtain:
P ( max L ≤ l ≤ N ∣ ∑ i = 1 l W i ∣ l ≥ x ) ≤ ∑ j = 0 ∞ 2 1 − j V L x 2 = 4 V L x 2 . \mathbb{P}\left(\max_{L\le l\le N}\frac{\left|\sum_{i=1}^{l}W_i\right|}{l}\ge x\right)\le\sum_{j=0}^{\infty}\frac{2^{1-j}V}{Lx^2}=\frac{4V}{Lx^2}. P L ≤ l ≤ N max l ∑ i = 1 l W i ≥ x ≤ j = 0 ∑ ∞ L x 2 2 1 − j V = L x 2 4 V .
This completes the proof.
Proving sharpness of CLONE
Proof of Theorem 3.3
We start by fixing c > 0 c > 0 c > 0 such that 2 c < min { τ , 1 − τ } 2c < \min\{\tau, 1-\tau\} 2 c < min { τ , 1 − τ } . For all sufficiently large n n n , therefore, by Assumption 2(i), we have ξ n ′ ∈ [ 2 c m , ( 1 − 2 c ) m ] \xi'_n \in[2cm,(1-2c)m] ξ n ′ ∈ [ 2 c m , ( 1 − 2 c ) m ] . Fix M M M sufficiently large, and write A = ⌈ M r n ⌉ A = \lceil Mr_n\rceil A = ⌈ M r n ⌉ and u = ⌊ A / 4 ⌋ u = \lfloor A/4\rfloor u = ⌊ A /4 ⌋ . Since by the hypothesis we have r n = o ( n ) = o ( m ) r_n = o(n) = o(m) r n = o ( n ) = o ( m ) , eventually it holds that A ≤ c m A \le cm A ≤ c m .
Define
H n = { ∣ E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ∣ ≥ μ 0 , n − μ 1 , n 2 } . H_n = \left\{\left|\mathbb{E}_{P_{0,n}}[\widehat{\ell}_n(X) \mid D'_n]-\mathbb{E}_{P_{1,n}}[\widehat{\ell}_n(X) \mid D'_n]\right| \ge\frac{\mu_{0,n}-\mu_{1,n}}{2}\right\}. H n = { E P 0 , n [ ℓ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ n ( X ) ∣ D n ′ ] ≥ 2 μ 0 , n − μ 1 , n } .
The conditional mean separation has mean μ 0 , n − μ 1 , n \mu_{0,n}-\mu_{1,n} μ 0 , n − μ 1 , n and variance at most 2 ε n ( μ 0 , n − μ 1 , n ) 2 2\varepsilon_n(\mu_{0,n}-\mu_{1,n})^2 2 ε n ( μ 0 , n − μ 1 , n ) 2 . Chebyshev’s inequality therefore gives P ( H n c ) ≤ 8 ε n \mathbb{P}(H_n^c) \le8\varepsilon_n P ( H n c ) ≤ 8 ε n . For the next steps, we condition on ( D n ′ , D n , 1 ) (D'_n,D_{n,1}) ( D n ′ , D n , 1 ) and restrict to H n ∩ { ∣ ξ ^ n / 2 − ξ n ′ ∣ ≤ u } H_n \cap\{|\widehat{\xi}_{n/2}-\xi'_n| \le u\} H n ∩ { ∣ ξ n /2 − ξ n ′ ∣ ≤ u } . Since u ≤ A ≤ c m u \le A \le cm u ≤ A ≤ c m , on this event ξ ^ n / 2 ∈ [ c m , ( 1 − c ) m ] \widehat{\xi}_{n/2} \in[cm,(1-c)m] ξ n /2 ∈ [ c m , ( 1 − c ) m ] , and the radius sequence is fixed.
Step 1: True window scores are large. Fix a radius R ≥ A R \ge A R ≥ A . The lengths of the segments to the left and right of ξ ^ n / 2 \widehat{\xi}_{n/2} ξ n /2 are respectively a R = min { R + 1 , ξ ^ n / 2 } a_R = \min\{R+1,\widehat{\xi}_{n/2}\} a R = min { R + 1 , ξ n /2 } and b R = min { R + 1 , m − ξ ^ n / 2 } b_R = \min\{R+1,m-\widehat{\xi}_{n/2}\} b R = min { R + 1 , m − ξ n /2 } . By the above discussion, both are at least A A A .
If ξ ^ n / 2 ≤ ξ n ′ \widehat{\xi}_{n/2} \le\xi'_n ξ n /2 ≤ ξ n ′ , then all the observations to the left of ξ ^ n / 2 \widehat{\xi}_{n/2} ξ n /2 are from the pre-change distribution, while exactly ξ n ′ − ξ ^ n / 2 \xi'_n-\widehat{\xi}_{n/2} ξ n ′ − ξ n /2 observations on the right are pre-change. Hence, the window score S R S_R S R has the expectation,
E [ S R ∣ D n ′ , D n , 1 ] = ( 1 − ξ n ′ − ξ ^ n / 2 b R ) { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } . \mathbb{E}[S_R \mid D'_n,D_{n,1}] = \left(1-\frac{\xi'_n-\widehat{\xi}_{n/2}}{b_R}\right)\left\{\mathbb{E}_{P_{0,n}}[\widehat{\ell}_n(X)\mid D'_n]-\mathbb{E}_{P_{1,n}}[\widehat{\ell}_n(X)\mid D'_n]\right\}. E [ S R ∣ D n ′ , D n , 1 ] = ( 1 − b R ξ n ′ − ξ n /2 ) { E P 0 , n [ ℓ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ n ( X ) ∣ D n ′ ] } .
If instead ξ ^ n / 2 ≥ ξ n ′ \widehat{\xi}_{n/2} \ge\xi'_n ξ n /2 ≥ ξ n ′ , the same expression holds with the pre-factor replaced by 1 − ( ξ ^ n / 2 − ξ n ′ ) / a R 1-(\widehat{\xi}_{n/2}-\xi'_n)/a_R 1 − ( ξ n /2 − ξ n ′ ) / a R . Since u / A ≤ 1 / 4 u/A \le1/4 u / A ≤ 1/4 , by the above calculation, on H n H_n H n we have
E [ S R ∣ D n ′ , D n , 1 ] ≥ 3 8 ( μ 0 , n − μ 1 , n ) . (32) \mathbb{E}[S_R \mid D'_n,D_{n,1}] \ge\frac{3}{8}(\mu_{0,n}-\mu_{1,n}). \tag*{(32)} E [ S R ∣ D n ′ , D n , 1 ] ≥ 8 3 ( μ 0 , n − μ 1 , n ) . (32)
Next, let us write V n = max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) V_n = \max_{j=0,1}\operatorname{Var}_{P_{j,n}}(\widehat{\ell}_n(X)\mid D'_n) V n = max j = 0 , 1 Var P j , n ( ℓ n ( X ) ∣ D n ′ ) . Since the calibration observations are drawn independently, we further have Var ( S R ∣ D n ′ , D n , 1 ) ≤ V n ( a R − 1 + b R − 1 ) \operatorname{Var}(S_R\mid D'_n,D_{n,1}) \le V_n(a_R^{-1}+b_R^{-1}) Var ( S R ∣ D n ′ , D n , 1 ) ≤ V n ( a R − 1 + b R − 1 ) . Therefore, by Chebyshev’s inequality, we obtain
P ( S R < μ 0 , n − μ 1 , n 4 | D n ′ , D n , 1 ) ≤ 64 V n ( μ 0 , n − μ 1 , n ) 2 ( 1 a R + 1 b R ) . (33) \mathbb{P}\left(S_R < \frac{\mu_{0,n}-\mu_{1,n}}{4}\,\middle|\,D'_n,D_{n,1}\right) \le\frac{64V_n}{(\mu_{0,n}-\mu_{1,n})^2}\left(\frac{1}{a_R}+\frac{1}{b_R}\right). \tag*{(33)} P ( S R < 4 μ 0 , n − μ 1 , n D n ′ , D n , 1 ) ≤ ( μ 0 , n − μ 1 , n ) 2 64 V n ( a R 1 + b R 1 ) . (33)
Step 2: Control the permutation tail. Let k R = a R + b R k_R = a_R+b_R k R = a R + b R be the length of the window segment and ℓ ‾ R = k R − 1 ∑ i = L R U R ℓ ^ n ( Y i , n ) \overline{\ell}_R = k_R^{-1}\sum_{i=L_R}^{U_R}\widehat{\ell}_n(Y_{i,n}) ℓ R = k R − 1 ∑ i = L R U R ℓ n ( Y i , n ) be the empirical average of ℓ ^ \widehat{\ell} ℓ computed on the corresponding observations. Further, note that conditional on the observed window, the permutation mean of S R S_R S R is zero. This is because both permuted averages have conditional expectation ℓ ˉ R \bar{\ell}_R ℓ ˉ R . Moreover, we can compute
Var π ( S R ( π ( Y L R , n , … , Y U R , n ) ) ∣ D n ′ , D n , 1 , Y n ) = k R k R − 1 ( 1 a R + 1 b R ) 1 k R ∑ i = L R U R ( ℓ ^ n ( Y i , n ) − ℓ ˉ R ) 2 ≤ 2 ( 1 a R + 1 b R ) 1 k R ∑ i = L R U R ( ℓ ^ n ( Y i , n ) − μ 0 , n + μ 1 , n 2 ) 2 , (34) \operatorname{Var}_{\pi}\left(S_R(\pi(Y_{L_R,n},\ldots,Y_{U_R,n})) \mid D'_n,D_{n,1},\mathbf{Y}_n\right)
= \frac{k_R}{k_R-1}\left(\frac{1}{a_R}+\frac{1}{b_R}\right)\frac{1}{k_R}\sum_{i=L_R}^{U_R}\left(\hat{\ell}_n(Y_{i,n})-\bar{\ell}_R\right)^2
\leq2\left(\frac{1}{a_R}+\frac{1}{b_R}\right)\frac{1}{k_R}\sum_{i=L_R}^{U_R}\left(\hat{\ell}_n(Y_{i,n})-\frac{\mu_{0,n}+\mu_{1,n}}{2}\right)^2, \tag*{(34)} Var π ( S R ( π ( Y L R , n , … , Y U R , n )) ∣ D n ′ , D n , 1 , Y n ) = k R − 1 k R ( a R 1 + b R 1 ) k R 1 i = L R ∑ U R ( ℓ ^ n ( Y i , n ) − ℓ ˉ R ) 2 ≤ 2 ( a R 1 + b R 1 ) k R 1 i = L R ∑ U R ( ℓ ^ n ( Y i , n ) − 2 μ 0 , n + μ 1 , n ) 2 , (34)
where the last inequality uses the fact that the empirical mean ℓ ˉ R \bar{\ell}_R ℓ ˉ R minimizes squared deviations and k R ≥ 2 k_R \geq2 k R ≥ 2 . On the event { S R ≥ ( μ 0 , n − μ 1 , n ) / 4 } \{S_R \geq(\mu_{0,n}-\mu_{1,n})/4\} { S R ≥ ( μ 0 , n − μ 1 , n ) /4 } , Chebyshev’s inequality under the permutation law gives the following upper bound on the CLONE p p p -values:
p w i n d o w , R ≤ 16 ( μ 0 , n − μ 1 , n ) 2 Var π ( S R ( π ( Y L R , n , … , Y U R , n ) ) ∣ D n ′ , D n , 1 , Y n ) . p_{\mathrm{window},R} \leq\frac{16}{(\mu_{0,n}-\mu_{1,n})^2}\operatorname{Var}_{\pi}\left(S_R(\pi(Y_{L_R,n},\ldots,Y_{U_R,n})) \mid D'_n,D_{n,1},\mathbf{Y}_n\right). p window , R ≤ ( μ 0 , n − μ 1 , n ) 2 16 Var π ( S R ( π ( Y L R , n , … , Y U R , n )) ∣ D n ′ , D n , 1 , Y n ) .
For notational clarity, let us write
K n = E P 0 , n [ ( ℓ ^ n ( X ) − μ 0 , n + μ 1 , n 2 ) 2 | D n ′ ] + E P 1 , n [ ( ℓ ^ n ( X ) − μ 0 , n + μ 1 , n 2 ) 2 | D n ′ ] . K_n=\mathbb{E}_{P_{0,n}}\left[\left(\hat{\ell}_n(X)-\frac{\mu_{0,n}+\mu_{1,n}}{2}\right)^2\middle|D'_n\right]+\mathbb{E}_{P_{1,n}}\left[\left(\hat{\ell}_n(X)-\frac{\mu_{0,n}+\mu_{1,n}}{2}\right)^2\middle|D'_n\right]. K n = E P 0 , n [ ( ℓ ^ n ( X ) − 2 μ 0 , n + μ 1 , n ) 2 D n ′ ] + E P 1 , n [ ( ℓ ^ n ( X ) − 2 μ 0 , n + μ 1 , n ) 2 D n ′ ] .
The empirical second moment in (B.5), 1 k R ∑ i = L R U R ( ℓ ^ n ( Y i , n ) − μ 0 , n + μ 1 , n 2 ) 2 \frac{1}{k_R}\sum_{i=L_R}^{U_R}\left(\hat{\ell}_n(Y_{i,n})-\frac{\mu_{0,n}+\mu_{1,n}}{2}\right)^2 k R 1 ∑ i = L R U R ( ℓ ^ n ( Y i , n ) − 2 μ 0 , n + μ 1 , n ) 2 has expectation at most K n K_n K n , conditional on D n ′ , D n , 1 D'_n,D_{n,1} D n ′ , D n , 1 . Combining Markov’s inequality with (B.4) therefore gives
P ( p w i n d o w , R > α ∣ D n ′ , D n , 1 ) ≤ P ( S R < μ 0 , n − μ 1 , n 4 | D n ′ , D n , 1 ) \mathbb{P}(p_{\mathrm{window},R}>\alpha\mid D'_n,D_{n,1})
\leq\mathbb{P}\left(S_R<\frac{\mu_{0,n}-\mu_{1,n}}{4}\middle|D'_n,D_{n,1}\right) P ( p window , R > α ∣ D n ′ , D n , 1 ) ≤ P ( S R < 4 μ 0 , n − μ 1 , n D n ′ , D n , 1 )
+ P ( 1 k R ∑ i = L R U R ( ℓ ^ n ( Y i , n ) − μ 0 , n + μ 1 , n 2 ) 2 > α ( μ 0 , n − μ 1 , n ) 2 32 ( a R − 1 + b R − 1 ) | D n ′ , D n , 1 ) ≤ 64 V n + 32 K n / α ( μ 0 , n − μ 1 , n ) 2 ( 1 a R + 1 b R ) . (35) \begin{aligned}
\quad+\mathbb{P}\left(\frac{1}{k_R}\sum_{i=L_R}^{U_R}\left(\hat{\ell}_n(Y_{i,n})-\frac{\mu_{0,n}+\mu_{1,n}}{2}\right)^2>\frac{\alpha(\mu_{0,n}-\mu_{1,n})^2}{32(a_R^{-1}+b_R^{-1})}\middle|D'_n,D_{n,1}\right) \\
&\leq\frac{64V_n+32K_n/\alpha}{(\mu_{0,n}-\mu_{1,n})^2}\left(\frac{1}{a_R}+\frac{1}{b_R}\right). \tag*{(35)}
\end{aligned} + P ( k R 1 i = L R ∑ U R ( ℓ ^ n ( Y i , n ) − 2 μ 0 , n + μ 1 , n ) 2 > 32 ( a R − 1 + b R − 1 ) α ( μ 0 , n − μ 1 , n ) 2 D n ′ , D n , 1 ) ≤ ( μ 0 , n − μ 1 , n ) 2 64 V n + 32 K n / α ( a R 1 + b R 1 ) . (35)
This bound holds on the event H n ∩ { ∣ ξ n / 2 ′ − ξ n ′ ∣ ≤ u } H_n\cap\{|\xi'_{n/2}-\xi'_n|\leq u\} H n ∩ { ∣ ξ n /2 ′ − ξ n ′ ∣ ≤ u } for every radius R ≥ A R\geq A R ≥ A .
Step 3: Sum over the geometric radii. We first observe that, by the law of total variance and the definitions of the unconditional moments,
E [ V n ] ≤ σ 0 , n 2 + σ 1 , n 2 , E [ K n ] = σ 0 , n 2 + σ 1 , n 2 + ( μ 0 , n − μ 1 , n ) 2 2 . \mathbb{E}[V_n]\leq\sigma_{0,n}^2+\sigma_{1,n}^2,\qquad\mathbb{E}[K_n]=\sigma_{0,n}^2+\sigma_{1,n}^2+\frac{(\mu_{0,n}-\mu_{1,n})^2}{2}. E [ V n ] ≤ σ 0 , n 2 + σ 1 , n 2 , E [ K n ] = σ 0 , n 2 + σ 1 , n 2 + 2 ( μ 0 , n − μ 1 , n ) 2 .
Conditional on ( D n ′ , D n , 1 ) (D'_n,D_{n,1}) ( D n ′ , D n , 1 ) , the radius sequence is fixed. On H n ∩ { ∣ ξ ^ n / 2 − ξ n ′ ∣ ≤ u } H_n \cap\{|\hat{\xi}_{n/2}-\xi'_n|\le u\} H n ∩ { ∣ ξ ^ n /2 − ξ n ′ ∣ ≤ u } , a union bound, followed by (B.6) and Lemma B.2, therefore gives
P ( ∃ j ∈ [ J ] : R j ≥ A , p w i n d o w , R j > α ∣ D n ′ , D n , 1 ) ≤ 64 V n + 32 K n / α ( μ 0 , n − μ 1 , n ) 2 ∑ j ∈ [ J ] R j ≥ A ( 1 a R j + 1 b R j ) ≤ 4 ( 64 V n + 32 K n / α ) c A ( μ 0 , n − μ 1 , n ) 2 . \mathbb{P}\left(\exists j\in[J]: R_j\ge A,\ p_{\mathrm{window},R_j}>\alpha\mid D'_n,D_{n,1}\right)
\le\frac{64V_n+32K_n/\alpha}{(\mu_{0,n}-\mu_{1,n})^2}\sum_{\substack{j\in[J]\\R_j\ge A}}\left(\frac{1}{aR_j}+\frac{1}{bR_j}\right)\le\frac{4(64V_n+32K_n/\alpha)}{cA(\mu_{0,n}-\mu_{1,n})^2}. P ( ∃ j ∈ [ J ] : R j ≥ A , p window , R j > α ∣ D n ′ , D n , 1 ) ≤ ( μ 0 , n − μ 1 , n ) 2 64 V n + 32 K n / α j ∈ [ J ] R j ≥ A ∑ ( a R j 1 + b R j 1 ) ≤ c A ( μ 0 , n − μ 1 , n ) 2 4 ( 64 V n + 32 K n / α ) .
The aforementioned bound holds uniformly over ξ ^ n / 2 ∈ [ c m , ( 1 − c ) m ] \hat{\xi}_{n/2}\in[cm,(1-c)m] ξ ^ n /2 ∈ [ c m , ( 1 − c ) m ] . Taking expectations therefore yields
P ( ∃ j ∈ [ J ] : R j ≥ A , p w i n d o w , R j > α , H n , ∣ ξ ^ n / 2 − ξ n ′ ∣ ≤ u ) ≤ 4 { 64 E [ V n ] + 32 E [ K n ] / α } c A ( μ 0 , n − μ 1 , n ) 2 ≤ 4 α c A { ( 64 α + 32 ) σ 0 , n 2 + σ 1 , n 2 ( μ 0 , n − μ 1 , n ) 2 + 16 } ≤ 448 r n α c A ≤ 448 α c M . \begin{aligned}
\mathbb{P}\left(\exists j\in[J]: R_j\ge A,\ p_{\mathrm{window},R_j}>\alpha,\ H_n,\ |\hat{\xi}_{n/2}-\xi'_n|\le u\right)
\le\frac{4\{64\mathbb{E}[V_n]+32\mathbb{E}[K_n]/\alpha\}}{cA(\mu_{0,n}-\mu_{1,n})^2} \\
&\le\frac{4}{\alpha cA}\left\{(64\alpha+32)\frac{\sigma_{0,n}^2+\sigma_{1,n}^2}{(\mu_{0,n}-\mu_{1,n})^2}+16\right\}\le\frac{448r_n}{\alpha cA}\le\frac{448}{\alpha cM}.
\end{aligned} P ( ∃ j ∈ [ J ] : R j ≥ A , p window , R j > α , H n , ∣ ξ ^ n /2 − ξ n ′ ∣ ≤ u ) ≤ c A ( μ 0 , n − μ 1 , n ) 2 4 { 64 E [ V n ] + 32 E [ K n ] / α } ≤ α c A 4 { ( 64 α + 32 ) ( μ 0 , n − μ 1 , n ) 2 σ 0 , n 2 + σ 1 , n 2 + 16 } ≤ α c A 448 r n ≤ α c M 448 .
Here, the penultimate inequality uses α < 1 \alpha<1 α < 1 , r n ≥ 1 r_n\ge1 r n ≥ 1 , and ( σ 0 , n 2 + σ 1 , n 2 ) / ( μ 0 , n − μ 1 , n ) 2 ≤ r n (\sigma_{0,n}^2+\sigma_{1,n}^2)/(\mu_{0,n}-\mu_{1,n})^2\le r_n ( σ 0 , n 2 + σ 1 , n 2 ) / ( μ 0 , n − μ 1 , n ) 2 ≤ r n .
Step 4: Bound the returned interval. Suppose every tested radius R j ≥ A R_j\ge A R j ≥ A rejects. If the first nonrejection occurs at index j j j , then R j < A R_j<A R j < A , and the procedure returns I R j − 1 I_{R_{j-1}} I R j − 1 . Since R j = ⌊ R j − 1 / 2 ⌋ R_j=\lfloor R_{j-1}/2\rfloor R j = ⌊ R j − 1 /2 ⌋ , we have R j − 1 ≤ 2 R j + 1 ≤ 2 A + 1 R_{j-1}\le2R_j+1\le2A+1 R j − 1 ≤ 2 R j + 1 ≤ 2 A + 1 . If all tests reject, the returned radius is zero. Thus, in either case, the retained calibration interval has at most 4 A + 3 4A+3 4 A + 3 locations. Since each calibration location maps to at most two original locations,
∣ I n , 1 − α C L O N E ∣ ≤ 8 A + 6. |I^{\mathrm{CLONE}}_{n,1-\alpha}|\le8A+6. ∣ I n , 1 − α CLONE ∣ ≤ 8 A + 6.
Consequently, Step 3 and P ( H n c ) ≤ 8 ε n \mathbb{P}(H_n^c)\le8\varepsilon_n P ( H n c ) ≤ 8 ε n give
P ( ∣ I n , 1 − α C L O N E ∣ > 8 A + 6 ) ≤ 8 ε n + P ( ∣ ξ ^ n / 2 − ξ n ′ ∣ > u ) + 448 α c M . \mathbb{P}\left(|I^{\mathrm{CLONE}}_{n,1-\alpha}|>8A+6\right)\le8\varepsilon_n+\mathbb{P}\left(|\hat{\xi}_{n/2}-\xi'_n|>u\right)+\frac{448}{\alpha cM}. P ( ∣ I n , 1 − α CLONE ∣ > 8 A + 6 ) ≤ 8 ε n + P ( ∣ ξ ^ n /2 − ξ n ′ ∣ > u ) + α c M 448 .
For M ≥ 16 M\ge16 M ≥ 16 , we have A ≥ 16 A\ge16 A ≥ 16 and u − 1 = ⌊ A / 4 ⌋ − 1 ≥ A / 8 u-1=\lfloor A/4\rfloor-1\ge A/8 u − 1 = ⌊ A /4 ⌋ − 1 ≥ A /8 . Proposition 3.2 therefore implies
P ( ∣ ξ ^ n / 2 − ξ n ′ ∣ > u ) ≤ 4 ε n κ 2 + 4 κ 2 ( u − 1 ) σ 0 , n 2 + σ 1 , n 2 ( μ 0 , n − μ 1 , n ) 2 ≤ 4 ε n κ 2 + 32 r n κ 2 A ≤ 4 ε n κ 2 + 32 κ 2 M . \begin{aligned}
\mathbb{P}\left(|\hat{\xi}_{n/2}-\xi'_n|>u\right)\le\frac{4\varepsilon_n}{\kappa^2}+\frac{4}{\kappa^2(u-1)}\frac{\sigma_{0,n}^2+\sigma_{1,n}^2}{(\mu_{0,n}-\mu_{1,n})^2} \\
&\le\frac{4\varepsilon_n}{\kappa^2}+\frac{32r_n}{\kappa^2A}\le\frac{4\varepsilon_n}{\kappa^2}+\frac{32}{\kappa^2M}.
\end{aligned} P ( ∣ ξ ^ n /2 − ξ n ′ ∣ > u ) ≤ κ 2 4 ε n + κ 2 ( u − 1 ) 4 ( μ 0 , n − μ 1 , n ) 2 σ 0 , n 2 + σ 1 , n 2 ≤ κ 2 4 ε n + κ 2 A 32 r n ≤ κ 2 4 ε n + κ 2 M 32 .
Combining these bounds, for every fixed M ≥ 16 M\ge16 M ≥ 16 and all sufficiently large n n n ,
P ( ∣ I n , 1 − α C L O N E ∣ > 8 ⌈ M r n ⌉ + 6 ) ≤ ( 8 + 4 κ 2 ) ε n + 32 κ 2 M + 448 α c M . \mathbb{P}\left(|I^{\mathrm{CLONE}}_{n,1-\alpha}|>8\lceil Mr_n\rceil+6\right)\le\left(8+\frac{4}{\kappa^2}\right)\varepsilon_n+\frac{32}{\kappa^2M}+\frac{448}{\alpha cM}. P ( ∣ I n , 1 − α CLONE ∣ > 8 ⌈ M r n ⌉ + 6 ) ≤ ( 8 + κ 2 4 ) ε n + κ 2 M 32 + α c M 448 .
By Assumption 2(iii), ε n → 0 \varepsilon_n \to0 ε n → 0 . First letting n → ∞ n \to\infty n → ∞ and then M → ∞ M \to\infty M → ∞ proves ∣ I n , 1 − α C L O N E ∣ = O P ( r n ) |I^{\mathrm{CLONE}}_{n,1-\alpha}| = O_{\mathbb{P}}(r_n) ∣ I n , 1 − α CLONE ∣ = O P ( r n ) . The relative size converges to zero because r n / n → 0 r_n/n \to0 r n / n → 0 . □ \square □
Auxiliary lemma
Lemma B.2. Fix c ∈ ( 0 , 1 / 2 ) c \in(0,1/2) c ∈ ( 0 , 1/2 ) and an integer reference h ∈ [ m − 1 ] ∩ [ c m , ( 1 − c ) m ] h \in[m-1] \cap[cm,(1-c)m] h ∈ [ m − 1 ] ∩ [ c m , ( 1 − c ) m ] . Consider the geometric grid defined by R 0 = max { h , m − 1 − h } R_0 = \max\{h,m-1-h\} R 0 = max { h , m − 1 − h } and R j + 1 = ⌊ R j / 2 ⌋ R_{j+1} = \lfloor R_j/2\rfloor R j + 1 = ⌊ R j /2 ⌋ until R J = 0 R_J=0 R J = 0 . Write a R = min { R + 1 , h } a_R = \min\{R+1,h\} a R = min { R + 1 , h } and b R = min { R + 1 , m − h } b_R = \min\{R+1,m-h\} b R = min { R + 1 , m − h } . Then, for every integer 1 ≤ A ≤ c m 1 \le A \le cm 1 ≤ A ≤ c m ,
∑ j ∈ [ J ] R j ≥ A ( 1 a R j + 1 b R j ) ≤ 4 c A . (36) \sum_{\substack{j\in[J]\\R_j\ge A}}\left(\frac{1}{a_{R_j}}+\frac{1}{b_{R_j}}\right)\le\frac{4}{cA}. \tag*{(36)} j ∈ [ J ] R j ≥ A ∑ ( a R j 1 + b R j 1 ) ≤ c A 4 . (36) Proof. Since R 0 ≤ m − 1 R_0 \le m-1 R 0 ≤ m − 1 , every radius satisfies R + 1 ≤ m R+1 \le m R + 1 ≤ m . Together with h ∧ ( m − h ) ≥ c m h \wedge(m-h) \ge cm h ∧ ( m − h ) ≥ c m , this gives
a R ∧ b R ≥ min { R + 1 , c m } ≥ c ( R + 1 ) . a_R \wedge b_R \ge\min\{R+1,cm\}\ge c(R+1). a R ∧ b R ≥ min { R + 1 , c m } ≥ c ( R + 1 ) . If no tested radius is at least A A A , the claim is immediate. Otherwise, let j A = max { j ∈ [ J ] : R j ≥ A } j_A=\max\{j\in[J]:R_j\ge A\} j A = max { j ∈ [ J ] : R j ≥ A } . The recursion gives R j ≥ 2 R j + 1 R_j\ge2R_{j+1} R j ≥ 2 R j + 1 , so R j A − k ≥ 2 k R j A ≥ 2 k A R_{j_A-k}\ge2^kR_{j_A}\ge2^kA R j A − k ≥ 2 k R j A ≥ 2 k A for k = 0 , … , j A − 1 k=0,\ldots,j_A-1 k = 0 , … , j A − 1 . Therefore,
∑ j ∈ [ J ] R j ≥ A ( 1 a R j + 1 b R j ) ≤ 2 c ∑ j = 1 j A 1 R j + 1 ≤ 2 c A ∑ k = 0 j A − 1 2 − k ≤ 4 c A . \sum_{\substack{j\in[J]\\R_j\ge A}}\left(\frac{1}{a_{R_j}}+\frac{1}{b_{R_j}}\right)
\le\frac{2}{c}\sum_{j=1}^{j_A}\frac{1}{R_j+1}
\le\frac{2}{cA}\sum_{k=0}^{j_A-1}2^{-k}
\le\frac{4}{cA}. j ∈ [ J ] R j ≥ A ∑ ( a R j 1 + b R j 1 ) ≤ c 2 j = 1 ∑ j A R j + 1 1 ≤ c A 2 k = 0 ∑ j A − 1 2 − k ≤ c A 4 . This proves the claim. □ \square □
Proving sharpness of CONCH
We start by defining some notation for clarity of the exposition. For t ∈ [ m − 1 ] t \in[m-1] t ∈ [ m − 1 ] , define
μ ^ t , n , L = 1 t ∑ i = 1 t ℓ ^ n ( Y i , n ) , μ ^ t , n , R = − 1 m − t ∑ i = t + 1 m ℓ ^ n ( Y i , n ) . \widehat{\mu}_{t,n,L}=\frac{1}{t}\sum_{i=1}^{t}\widehat{\ell}_n(Y_{i,n}),\qquad
\widehat{\mu}_{t,n,R}=-\frac{1}{m-t}\sum_{i=t+1}^{m}\widehat{\ell}_n(Y_{i,n}). μ t , n , L = t 1 i = 1 ∑ t ℓ n ( Y i , n ) , μ t , n , R = − m − t 1 i = t + 1 ∑ m ℓ n ( Y i , n ) .
For t ≠ ξ ^ n / 2 t \ne\widehat{\xi}_n/2 t = ξ n /2 , write
Δ t , ξ ^ n / 2 = S n ( Y n , t ) ∣ t − ξ ^ n / 2 ∣ − μ ^ t , n , L 1 { t > ξ ^ n / 2 } − μ ^ t , n , R 1 { t < ξ ^ n / 2 } . (37) \Delta_{t,\widehat{\xi}_n/2}
=\frac{S_n(Y_n,t)}{|t-\widehat{\xi}_n/2|}
-\widehat{\mu}_{t,n,L}\mathbb{1}\{t>\widehat{\xi}_n/2\}
-\widehat{\mu}_{t,n,R}\mathbb{1}\{t<\widehat{\xi}_n/2\}. \tag*{(37)} Δ t , ξ n /2 = ∣ t − ξ n /2∣ S n ( Y n , t ) − μ t , n , L 1 { t > ξ n /2 } − μ t , n , R 1 { t < ξ n /2 } . (37)
We also define
v ^ n = 1 m ∑ i = 1 m ( ℓ ^ n ( Y i , n ) − μ 0 , n + μ 1 , n 2 ) 2 . (38) \widehat{v}_n=\frac{1}{m}\sum_{i=1}^{m}\left(\widehat{\ell}_n(Y_{i,n})-\frac{\mu_{0,n}+\mu_{1,n}}{2}\right)^2. \tag*{(38)} v n = m 1 i = 1 ∑ m ( ℓ n ( Y i , n ) − 2 μ 0 , n + μ 1 , n ) 2 . (38)
Proof of Theorem 5.1
Fix c ∈ ( 0 , min { τ , 1 − τ } ) c \in(0,\min\{\tau,1-\tau\}) c ∈ ( 0 , min { τ , 1 − τ }) . For all sufficiently large n n n , Assumption 2(i) gives
ξ n ′ ≥ c m , m − ξ n ′ ≥ c m . \xi'_n \ge cm,\qquad m-\xi'_n \ge cm. ξ n ′ ≥ c m , m − ξ n ′ ≥ c m .
Throughout the proof, write R = ⌈ M r n ⌉ R=\lceil Mr_n\rceil R = ⌈ M r n ⌉ and u = ⌊ c R / ( 2 + c ) ⌋ u=\lfloor cR/(2+c)\rfloor u = ⌊ c R / ( 2 + c )⌋ . Then R > u R>u R > u and
u R − u ≤ c 2 . (39) \frac{u}{R-u}\le\frac{c}{2}. \tag*{(39)} R − u u ≤ 2 c . (39)
Step 1: Restrict to a high-probability event. We start by defining the event
H n = { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ≥ μ 0 , n − μ 1 , n 2 } . H_n=\left\{\mathbb{E}_{P_{0,n}}[\hat{\ell}_n(X)\mid D'_n]-\mathbb{E}_{P_{1,n}}[\hat{\ell}_n(X)\mid D'_n]\ge\frac{\mu_{0,n}-\mu_{1,n}}{2}\right\}. H n = { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ≥ 2 μ 0 , n − μ 1 , n } .
By the definition of ε n \varepsilon_n ε n , the conditional mean separation has mean μ 0 , n − μ 1 , n \mu_{0,n}-\mu_{1,n} μ 0 , n − μ 1 , n and variance bounded as follows:
Var D n ′ ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) ≤ 2 { Var D n ′ ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) + Var D n ′ ( E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) } = 2 ε n ( μ 0 , n − μ 1 , n ) 2 . \begin{aligned}
\operatorname{Var}_{D'_n}\left(\mathbb{E}_{P_{0,n}}[\hat{\ell}_n(X)\mid D'_n]-\mathbb{E}_{P_{1,n}}[\hat{\ell}_n(X)\mid D'_n]\right)
&\le2\left\{\operatorname{Var}_{D'_n}\left(\mathbb{E}_{P_{0,n}}[\hat{\ell}_n(X)\mid D'_n]\right)+\operatorname{Var}_{D'_n}\left(\mathbb{E}_{P_{1,n}}[\hat{\ell}_n(X)\mid D'_n]\right)\right\}\\
&=2\varepsilon_n(\mu_{0,n}-\mu_{1,n})^2.
\end{aligned} Var D n ′ ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) ≤ 2 { Var D n ′ ( E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) + Var D n ′ ( E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] ) } = 2 ε n ( μ 0 , n − μ 1 , n ) 2 .
Thus, Chebyshev’s inequality followed by a union bound gives
P ( H n c ∪ { ∣ ξ ^ n / 2 − ξ n ′ ∣ > u } ) ≤ 8 ε n + P ( ∣ ξ ^ n / 2 − ξ n ′ ∣ > u ) . (40) \mathbb{P}\left(H_n^c\cup\left\{\left|\hat{\xi}_{n/2}-\xi'_n\right|>u\right\}\right)\le8\varepsilon_n+\mathbb{P}\left(\left|\hat{\xi}_{n/2}-\xi'_n\right|>u\right). \tag*{(40)} P ( H n c ∪ { ξ ^ n /2 − ξ n ′ > u } ) ≤ 8 ε n + P ( ξ ^ n /2 − ξ n ′ > u ) . (40)
For the next steps, we condition on ( D n ′ , D n , 1 ) (D'_n,D_{n,1}) ( D n ′ , D n , 1 ) and restrict to H n ∩ { ∣ ξ ^ n / 2 − ξ n ′ ∣ ≤ u } H_n\cap\{|\hat{\xi}_{n/2}-\xi'_n|\le u\} H n ∩ { ∣ ξ ^ n /2 − ξ n ′ ∣ ≤ u } .
Step 2: Negative drift on both sides of the changepoint. For t ≥ ξ n ′ + R t\ge\xi'_n+R t ≥ ξ n ′ + R , since R > u R>u R > u , we have t > ξ ^ n / 2 t>\hat{\xi}_{n/2} t > ξ ^ n /2 . The block { ξ ^ n / 2 + 1 , … , t } \{\hat{\xi}_{n/2}+1,\ldots,t\} { ξ ^ n /2 + 1 , … , t } contains ( ξ n ′ − ξ ^ n / 2 ) + (\xi'_n-\hat{\xi}_{n/2})_+ ( ξ n ′ − ξ ^ n /2 ) + pre-change observations. Hence,
E [ 1 t − ξ ^ n / 2 ∑ i = ξ ^ n / 2 + 1 t ℓ ^ n ( Y i , n ) ∣ D n ′ , D n , 1 ] = E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] + ( ξ n ′ − ξ ^ n / 2 ) + t − ξ ^ n / 2 { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } . \begin{aligned}
\mathbb{E}\left[\left.\frac{1}{t-\hat{\xi}_{n/2}}\sum_{i=\hat{\xi}_{n/2}+1}^{t}\hat{\ell}_n(Y_{i,n})\right|D'_n,D_{n,1}\right]
&=\mathbb{E}_{P_{1,n}}[\hat{\ell}_n(X)\mid D'_n]\\
&\quad+\frac{(\xi'_n-\hat{\xi}_{n/2})_+}{t-\hat{\xi}_{n/2}}
\left\{\mathbb{E}_{P_{0,n}}[\hat{\ell}_n(X)\mid D'_n]-\mathbb{E}_{P_{1,n}}[\hat{\ell}_n(X)\mid D'_n]\right\}.
\end{aligned} E t − ξ ^ n /2 1 i = ξ ^ n /2 + 1 ∑ t ℓ ^ n ( Y i , n ) D n ′ , D n , 1 = E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] + t − ξ ^ n /2 ( ξ n ′ − ξ ^ n /2 ) + { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } .
Similarly,
E [ μ ^ t , n , L ∣ D n ′ , D n , 1 ] = E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] + ξ n ′ t { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } . \mathbb{E}[\hat{\mu}_{t,n,L}\mid D'_n,D_{n,1}]
=\mathbb{E}_{P_{1,n}}[\hat{\ell}_n(X)\mid D'_n]
+\frac{\xi'_n}{t}\left\{\mathbb{E}_{P_{0,n}}[\hat{\ell}_n(X)\mid D'_n]-\mathbb{E}_{P_{1,n}}[\hat{\ell}_n(X)\mid D'_n]\right\}. E [ μ ^ t , n , L ∣ D n ′ , D n , 1 ] = E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] + t ξ n ′ { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } .
Since t > ξ ^ n / 2 t > \hat{\xi}_{n/2} t > ξ ^ n /2 , we have
Δ t , ξ ^ n / 2 = S n ( Y n , t ) ∣ t − ξ ^ n / 2 ∣ − μ ^ t , n , L = 1 t − ξ ^ n / 2 ∑ i = ξ ^ n / 2 + 1 t ℓ ^ n ( Y i , n ) − μ ^ t , n , L . \Delta_{t,\hat{\xi}_{n/2}} = \frac{S_n(Y_n,t)}{|t-\hat{\xi}_{n/2}|} - \hat{\mu}_{t,n,L} = \frac{1}{t-\hat{\xi}_{n/2}}\sum_{i=\hat{\xi}_{n/2}+1}^{t}\hat{\ell}_n(Y_{i,n})-\hat{\mu}_{t,n,L}. Δ t , ξ ^ n /2 = ∣ t − ξ ^ n /2 ∣ S n ( Y n , t ) − μ ^ t , n , L = t − ξ ^ n /2 1 i = ξ ^ n /2 + 1 ∑ t ℓ ^ n ( Y i , n ) − μ ^ t , n , L .
We have ξ n ′ / t ≥ ξ n ′ / m ≥ c \xi'_n/t \ge\xi'_n/m \ge c ξ n ′ / t ≥ ξ n ′ / m ≥ c and, on the training event under consideration,
( ξ n ′ − ξ ^ n / 2 ) + t − ξ ^ n / 2 ≤ u R − u ≤ c 2 , \frac{(\xi'_n-\hat{\xi}_{n/2})_+}{t-\hat{\xi}_{n/2}} \le\frac{u}{R-u} \le\frac{c}{2}, t − ξ ^ n /2 ( ξ n ′ − ξ ^ n /2 ) + ≤ R − u u ≤ 2 c ,
where the last inequality uses (B.10). Together, these give
E [ Δ t , ξ ^ n / 2 ∣ D n ′ , D n , 1 ] = − { ξ n ′ t − ( ξ n ′ − ξ ^ n / 2 ) + t − ξ ^ n / 2 } { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } ≤ − c 4 ( μ 0 , n − μ 1 , n ) . (41) \begin{aligned}
\mathbb{E}[\Delta_{t,\hat{\xi}_{n/2}} \mid D'_n,D_{n,1}]
&= -\left\{\frac{\xi'_n}{t}-\frac{(\xi'_n-\hat{\xi}_{n/2})_+}{t-\hat{\xi}_{n/2}}\right\}
\left\{\mathbb{E}_{P_{0,n}}[\hat{\ell}_n(X)\mid D'_n]-\mathbb{E}_{P_{1,n}}[\hat{\ell}_n(X)\mid D'_n]\right\}\\
&\le-\frac{c}{4}(\mu_{0,n}-\mu_{1,n}). \tag*{(41)}
\end{aligned} E [ Δ t , ξ ^ n /2 ∣ D n ′ , D n , 1 ] = − { t ξ n ′ − t − ξ ^ n /2 ( ξ n ′ − ξ ^ n /2 ) + } { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } ≤ − 4 c ( μ 0 , n − μ 1 , n ) . (41)
An analogous calculation for t ≤ ξ n ′ − R t \le\xi'_n-R t ≤ ξ n ′ − R gives
E [ Δ t , ξ ^ n / 2 ∣ D n ′ , D n , 1 ] = − { m − ξ n ′ m − t − ( ξ ^ n / 2 − ξ n ′ ) + ξ ^ n / 2 − t } { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } ≤ − c 4 ( μ 0 , n − μ 1 , n ) . (42) \begin{aligned}
\mathbb{E}[\Delta_{t,\hat{\xi}_{n/2}} \mid D'_n,D_{n,1}]
&= -\left\{\frac{m-\xi'_n}{m-t}-\frac{(\hat{\xi}_{n/2}-\xi'_n)_+}{\hat{\xi}_{n/2}-t}\right\}
\left\{\mathbb{E}_{P_{0,n}}[\hat{\ell}_n(X)\mid D'_n]-\mathbb{E}_{P_{1,n}}[\hat{\ell}_n(X)\mid D'_n]\right\}\\
&\le-\frac{c}{4}(\mu_{0,n}-\mu_{1,n}). \tag*{(42)}
\end{aligned} E [ Δ t , ξ ^ n /2 ∣ D n ′ , D n , 1 ] = − { m − t m − ξ n ′ − ξ ^ n /2 − t ( ξ ^ n /2 − ξ n ′ ) + } { E P 0 , n [ ℓ ^ n ( X ) ∣ D n ′ ] − E P 1 , n [ ℓ ^ n ( X ) ∣ D n ′ ] } ≤ − 4 c ( μ 0 , n − μ 1 , n ) . (42)
Thus, conditional on ( D n ′ , D n , 1 ) (D'_n,D_{n,1}) ( D n ′ , D n , 1 ) , Δ t , ξ ^ n / 2 \Delta_{t,\hat{\xi}_{n/2}} Δ t , ξ ^ n /2 has negative mean on either side. Next, we show that the corresponding bound also holds with high probability.
Step 3: Uniform control of fluctuations around the drift. For i ∈ [ m ] i \in[m] i ∈ [ m ] , define W i , n = ℓ ^ n ( Y i , n ) − E [ ℓ ^ n ( Y i , n ) ∣ D n ′ , D n , 1 ] W_{i,n}=\hat{\ell}_n(Y_{i,n})-\mathbb{E}[\hat{\ell}_n(Y_{i,n})\mid D'_n,D_{n,1}] W i , n = ℓ ^ n ( Y i , n ) − E [ ℓ ^ n ( Y i , n ) ∣ D n ′ , D n , 1 ] . For t ≥ ξ n ′ + R t\ge\xi'_n+R t ≥ ξ n ′ + R ,
Δ t , ξ ^ n / 2 − E [ Δ t , ξ ^ n / 2 ∣ D n ′ , D n , 1 ] = ∑ i = ξ ^ n / 2 + 1 t W i , n t − ξ ^ n / 2 − ∑ i = 1 t W i , n t . \Delta_{t,\hat{\xi}_{n/2}}-\mathbb{E}[\Delta_{t,\hat{\xi}_{n/2}}\mid D'_n,D_{n,1}]
=
\frac{\sum_{i=\hat{\xi}_{n/2}+1}^{t}W_{i,n}}{t-\hat{\xi}_{n/2}}
-\frac{\sum_{i=1}^{t}W_{i,n}}{t}. Δ t , ξ ^ n /2 − E [ Δ t , ξ ^ n /2 ∣ D n ′ , D n , 1 ] = t − ξ ^ n /2 ∑ i = ξ ^ n /2 + 1 t W i , n − t ∑ i = 1 t W i , n .
The two averages contain at least R − u R-u R − u and ξ n ′ ≥ c m \xi'_n\ge cm ξ n ′ ≥ c m summands, respectively. These summands are conditionally independent but need not be identically distributed. Therefore, the general independent-variable bound in Lemma B.1 gives
P ( sup t ∈ [ m − 1 ] t ≥ ξ n ′ + R ∣ ∑ i = ξ ^ n / 2 + 1 t W i , n t − ξ ^ n / 2 ∣ > c ( μ 0 , n − μ 1 , n ) 16 ∣ D n ′ , D n , 1 ) ≤ 2 10 max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) c 2 ( μ 0 , n − μ 1 , n ) 2 ( R − u ) . \mathbb{P}\left(
\left.
\sup_{\substack{t\in[m-1]\\t\ge\xi'_n+R}}
\left|
\frac{\sum_{i=\hat{\xi}_{n/2}+1}^{t}W_{i,n}}{t-\hat{\xi}_{n/2}}
\right|
>
\frac{c(\mu_{0,n}-\mu_{1,n})}{16}
\right|D'_n,D_{n,1}\right)
\le
\frac{2^{10}\max_{j=0,1}\operatorname{Var}_{P_{j,n}}(\hat{\ell}_n(X)\mid D'_n)}
{c^2(\mu_{0,n}-\mu_{1,n})^2(R-u)}. P t ∈ [ m − 1 ] t ≥ ξ n ′ + R sup t − ξ ^ n /2 ∑ i = ξ ^ n /2 + 1 t W i , n > 16 c ( μ 0 , n − μ 1 , n ) D n ′ , D n , 1 ≤ c 2 ( μ 0 , n − μ 1 , n ) 2 ( R − u ) 2 10 max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) .
Similarly, we derive
P ( sup t ∈ [ m − 1 ] t ≥ ξ n ′ + R t ≠ ξ ^ n / 2 ∣ ∑ i = 1 t W i , n t ∣ > c ( μ 0 , n − μ 1 , n ) 16 | D n ′ , D n , 1 ) ≤ 2 10 max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) c 2 ( μ 0 , n − μ 1 , n ) 2 c m . \mathbb{P}\left(\sup_{\substack{t\in[m-1]\\t\geq\xi'_n+R\\t\neq\hat{\xi}_{n/2}}}\left|\frac{\sum_{i=1}^{t}W_{i,n}}{t}\right|>\frac{c(\mu_{0,n}-\mu_{1,n})}{16}\,\middle|\,D'_n,D_{n,1}\right)\leq\frac{2^{10}\max_{j=0,1}\operatorname{Var}_{P_{j,n}}(\hat{\ell}_n(X)\mid D'_n)}{c^2(\mu_{0,n}-\mu_{1,n})^2cm}. P t ∈ [ m − 1 ] t ≥ ξ n ′ + R t = ξ ^ n /2 sup t ∑ i = 1 t W i , n > 16 c ( μ 0 , n − μ 1 , n ) D n ′ , D n , 1 ≤ c 2 ( μ 0 , n − μ 1 , n ) 2 c m 2 10 max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) .
Together, these imply
P ( sup t ∈ [ m − 1 ] t ≥ ξ n ′ + R ∣ Δ t , ξ ^ n / 2 − E [ Δ t , ξ ^ n / 2 ∣ D n ′ , D n , 1 ] ∣ > c ( μ 0 , n − μ 1 , n ) 8 | D n ′ , D n , 1 ) ≤ 2 10 max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) c 2 ( μ 0 , n − μ 1 , n ) 2 ( 1 R − u + 1 c m ) . \mathbb{P}\left(\sup_{\substack{t\in[m-1]\\t\geq\xi'_n+R}}\left|\Delta_{t,\hat{\xi}_{n/2}}-\mathbb{E}[\Delta_{t,\hat{\xi}_{n/2}}\mid D'_n,D_{n,1}]\right|>\frac{c(\mu_{0,n}-\mu_{1,n})}{8}\,\middle|\,D'_n,D_{n,1}\right)
\leq\frac{2^{10}\max_{j=0,1}\operatorname{Var}_{P_{j,n}}(\hat{\ell}_n(X)\mid D'_n)}{c^2(\mu_{0,n}-\mu_{1,n})^2}\left(\frac{1}{R-u}+\frac{1}{cm}\right). P t ∈ [ m − 1 ] t ≥ ξ n ′ + R sup Δ t , ξ ^ n /2 − E [ Δ t , ξ ^ n /2 ∣ D n ′ , D n , 1 ] > 8 c ( μ 0 , n − μ 1 , n ) D n ′ , D n , 1 ≤ c 2 ( μ 0 , n − μ 1 , n ) 2 2 10 max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) ( R − u 1 + c m 1 ) .
For t ≤ ξ n ′ − R t\leq\xi'_n-R t ≤ ξ n ′ − R , the same argument, applied to the reversed sequences, gives
P ( sup t ∈ [ m − 1 ] t ≤ ξ n ′ − R ∣ Δ t , ξ ^ n / 2 − E [ Δ t , ξ ^ n / 2 ∣ D n ′ , D n , 1 ] ∣ > c ( μ 0 , n − μ 1 , n ) 8 | D n ′ , D n , 1 ) ≤ 2 10 max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) c 2 ( μ 0 , n − μ 1 , n ) 2 ( 1 R − u + 1 c m ) . \mathbb{P}\left(\sup_{\substack{t\in[m-1]\\t\leq\xi'_n-R}}\left|\Delta_{t,\hat{\xi}_{n/2}}-\mathbb{E}[\Delta_{t,\hat{\xi}_{n/2}}\mid D'_n,D_{n,1}]\right|>\frac{c(\mu_{0,n}-\mu_{1,n})}{8}\,\middle|\,D'_n,D_{n,1}\right)
\leq\frac{2^{10}\max_{j=0,1}\operatorname{Var}_{P_{j,n}}(\hat{\ell}_n(X)\mid D'_n)}{c^2(\mu_{0,n}-\mu_{1,n})^2}\left(\frac{1}{R-u}+\frac{1}{cm}\right). P t ∈ [ m − 1 ] t ≤ ξ n ′ − R sup Δ t , ξ ^ n /2 − E [ Δ t , ξ ^ n /2 ∣ D n ′ , D n , 1 ] > 8 c ( μ 0 , n − μ 1 , n ) D n ′ , D n , 1 ≤ c 2 ( μ 0 , n − μ 1 , n ) 2 2 10 max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) ( R − u 1 + c m 1 ) .
By the law of total variance,
E [ max j = 0 , 1 Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) ] ≤ σ 0 , n 2 + σ 1 , n 2 . \mathbb{E}\left[\max_{j=0,1}\operatorname{Var}_{P_{j,n}}(\hat{\ell}_n(X)\mid D'_n)\right]\leq\sigma_{0,n}^2+\sigma_{1,n}^2. E [ j = 0 , 1 max Var P j , n ( ℓ ^ n ( X ) ∣ D n ′ ) ] ≤ σ 0 , n 2 + σ 1 , n 2 .
Combining these bounds with (B.12)–(B.13), we obtain
P ( sup t ∈ [ m − 1 ] ∣ t − ξ n ′ ∣ ≥ R t ≠ ξ ^ n / 2 Δ t , ξ ^ n / 2 > − c ( μ 0 , n − μ 1 , n ) 8 , H n , ∣ ξ ^ n / 2 − ξ n ′ ∣ ≤ u ) ≤ 2 11 ( σ 0 , n 2 + σ 1 , n 2 ) c 2 ( μ 0 , n − μ 1 , n ) 2 ( 1 R − u + 1 c m ) . (43) \mathbb{P}\left(\sup_{\substack{t\in[m-1]\\|t-\xi'_n|\geq R\\t\neq\hat{\xi}_{n/2}}}\Delta_{t,\hat{\xi}_{n/2}}>-\frac{c(\mu_{0,n}-\mu_{1,n})}{8},\ H_n,\ |\hat{\xi}_{n/2}-\xi'_n|\leq u\right)
\leq\frac{2^{11}(\sigma_{0,n}^2+\sigma_{1,n}^2)}{c^2(\mu_{0,n}-\mu_{1,n})^2}\left(\frac{1}{R-u}+\frac{1}{cm}\right). \tag*{(43)} P t ∈ [ m − 1 ] ∣ t − ξ n ′ ∣ ≥ R t = ξ ^ n /2 sup Δ t , ξ ^ n /2 > − 8 c ( μ 0 , n − μ 1 , n ) , H n , ∣ ξ ^ n /2 − ξ n ′ ∣ ≤ u ≤ c 2 ( μ 0 , n − μ 1 , n ) 2 2 11 ( σ 0 , n 2 + σ 1 , n 2 ) ( R − u 1 + c m 1 ) . (43)
Step 4: Bound all remaining permutation p p p -values. Define
G n = { sup t ∈ [ m − 1 ] ∣ t − ξ n ′ ∣ ≥ R t ≠ ξ ^ n / 2 Δ t , ξ ^ n / 2 > − c ( μ 0 , n − μ 1 , n ) 8 } . \mathcal{G}_n=\left\{\sup_{\substack{t\in[m-1]\\|t-\xi'_n|\geq R\\t\neq\hat{\xi}_{n/2}}}\Delta_{t,\hat{\xi}_{n/2}}>-\frac{c(\mu_{0,n}-\mu_{1,n})}{8}\right\}. G n = ⎩ ⎨ ⎧ t ∈ [ m − 1 ] ∣ t − ξ n ′ ∣ ≥ R t = ξ ^ n /2 sup Δ t , ξ ^ n /2 > − 8 c ( μ 0 , n − μ 1 , n ) ⎭ ⎬ ⎫ .
On H n ∩ { ∣ ξ ^ n / 2 − ξ n ′ ∣ ≤ u } ∩ G n c H_n\cap\{|\hat{\xi}_{n/2}-\xi'_n|\leq u\}\cap\mathcal{G}_n^c H n ∩ { ∣ ξ ^ n /2 − ξ n ′ ∣ ≤ u } ∩ G n c , every t ∈ [ m − 1 ] t\in[m-1] t ∈ [ m − 1 ] with ∣ t − ξ n ′ ∣ ≥ R |t-\xi'_n|\geq R ∣ t − ξ n ′ ∣ ≥ R satisfies
∣ t − ξ ^ n / 2 ∣ ≥ R − u , Δ t , ξ ^ n / 2 ≤ − c ( μ 0 , n − μ 1 , n ) 8 . |t-\hat{\xi}_{n/2}|\geq R-u,\qquad\Delta_{t,\hat{\xi}_{n/2}}\leq-\frac{c(\mu_{0,n}-\mu_{1,n})}{8}. ∣ t − ξ ^ n /2 ∣ ≥ R − u , Δ t , ξ ^ n /2 ≤ − 8 c ( μ 0 , n − μ 1 , n ) .
For t ≥ ξ n ′ + R t \ge\xi'_n+R t ≥ ξ n ′ + R , we have m / t ≤ 1 / c m/t \le1/c m / t ≤ 1/ c ; for t ≤ ξ n ′ − R t \le\xi'_n-R t ≤ ξ n ′ − R , we have m / ( m − t ) ≤ 1 / c m/(m-t) \le1/c m / ( m − t ) ≤ 1/ c . Lemma B.3 therefore gives, on both sides,
V t , n π ≤ u ^ n c ( R − u ) , p t , n ≤ u ^ n / { c ( R − u ) } u ^ n / { c ( R − u ) } + c 2 ( μ 0 , n − μ 1 , n ) 2 / 64 . V_{t,n}^{\pi} \le\frac{\hat{u}_n}{c(R-u)}, \qquad p_{t,n} \le\frac{\hat{u}_n/\{c(R-u)\}}{\hat{u}_n/\{c(R-u)\}+c^2(\mu_{0,n}-\mu_{1,n})^2/64}. V t , n π ≤ c ( R − u ) u ^ n , p t , n ≤ u ^ n / { c ( R − u )} + c 2 ( μ 0 , n − μ 1 , n ) 2 /64 u ^ n / { c ( R − u )} .
Consequently, p t , n > α p_{t,n}>\alpha p t , n > α implies
v ^ n > α c 3 ( R − u ) ( μ 0 , n − μ 1 , n ) 2 64 ( 1 − α ) . \hat{v}_n > \frac{\alpha c^3(R-u)(\mu_{0,n}-\mu_{1,n})^2}{64(1-\alpha)}. v ^ n > 64 ( 1 − α ) α c 3 ( R − u ) ( μ 0 , n − μ 1 , n ) 2 .
By Markov’s inequality, the probability of this event is at most
64 ( 1 − α ) α c 3 ( R − u ) { σ 0 , n 2 + σ 1 , n 2 ( μ 0 , n − μ 1 , n ) 2 + 1 4 } . \frac{64(1-\alpha)}{\alpha c^3(R-u)}
\left\{\frac{\sigma_{0,n}^2+\sigma_{1,n}^2}{(\mu_{0,n}-\mu_{1,n})^2}+\frac{1}{4}\right\}. α c 3 ( R − u ) 64 ( 1 − α ) { ( μ 0 , n − μ 1 , n ) 2 σ 0 , n 2 + σ 1 , n 2 + 4 1 } .
Combining this bound with (B.11) and (B.14), we obtain
P ( max t ∈ [ m − 1 ] ∣ t − ξ n ′ ∣ ≥ R p t , n > α ) ≤ 8 ε n + P ( ∣ ξ ^ n / 2 − ξ ′ ∣ > u ) + 2 11 ( σ 0 , n 2 + σ 1 , n 2 ) c 2 ( μ 0 , n − μ 1 , n ) 2 ( 1 R − u + 1 c m ) + 64 ( 1 − α ) α c 3 ( R − u ) { σ 0 , n 2 + σ 1 , n 2 ( μ 0 , n − μ 1 , n ) 2 + 1 4 } . (44) \mathbb{P}\left(\max_{\substack{t\in[m-1]\\ |t-\xi'_n|\ge R}}p_{t,n}>\alpha\right)
\le8\varepsilon_n+\mathbb{P}(|\hat{\xi}_{n/2}-\xi'|>u)
+\frac{2^{11}(\sigma_{0,n}^2+\sigma_{1,n}^2)}{c^2(\mu_{0,n}-\mu_{1,n})^2}
\left(\frac{1}{R-u}+\frac{1}{cm}\right)
+\frac{64(1-\alpha)}{\alpha c^3(R-u)}
\left\{\frac{\sigma_{0,n}^2+\sigma_{1,n}^2}{(\mu_{0,n}-\mu_{1,n})^2}+\frac{1}{4}\right\}. \tag*{(44)} P t ∈ [ m − 1 ] ∣ t − ξ n ′ ∣ ≥ R max p t , n > α ≤ 8 ε n + P ( ∣ ξ ^ n /2 − ξ ′ ∣ > u ) + c 2 ( μ 0 , n − μ 1 , n ) 2 2 11 ( σ 0 , n 2 + σ 1 , n 2 ) ( R − u 1 + c m 1 ) + α c 3 ( R − u ) 64 ( 1 − α ) { ( μ 0 , n − μ 1 , n ) 2 σ 0 , n 2 + σ 1 , n 2 + 4 1 } . (44)
Step 5: Choose the exclusion radius. Recall R = ⌈ M r n ⌉ R=\lceil Mr_n\rceil R = ⌈ M r n ⌉ and u = ⌊ c R / ( 2 + c ) ⌋ u=\lfloor cR/(2+c)\rfloor u = ⌊ c R / ( 2 + c )⌋ . For sufficiently large M M M , u ≥ 2 u\ge2 u ≥ 2 , and both u − 1 u-1 u − 1 and R − u R-u R − u are bounded below by positive multiples of M r n Mr_n M r n , depending only on c c c . By (3.7),
σ 0 , n 2 + σ 1 , n 2 ( μ 0 , n − μ 1 , n ) 2 ≤ r n . \frac{\sigma_{0,n}^2+\sigma_{1,n}^2}{(\mu_{0,n}-\mu_{1,n})^2}\le r_n. ( μ 0 , n − μ 1 , n ) 2 σ 0 , n 2 + σ 1 , n 2 ≤ r n .
For the reference estimator in (3.4), Proposition 3.2 now bounds (B.15) by
( 8 + 4 κ 2 ) ε n + C c , κ ( 1 α M + r n m ) , \left(8+\frac{4}{\kappa^2}\right)\varepsilon_n+C_{c,\kappa}\left(\frac{1}{\alpha M}+\frac{r_n}{m}\right), ( 8 + κ 2 4 ) ε n + C c , κ ( α M 1 + m r n ) ,
for a finite constant C c , κ C_{c,\kappa} C c , κ depending only on c c c and κ \kappa κ . By Assumption 2(iii) and r n / n → 0 r_n/n\to0 r n / n → 0 , first let n → ∞ n\to\infty n → ∞ and then M → ∞ M\to\infty M → ∞ to obtain (5.4).
On the event that all candidates at distance at least R R R are excluded, the interval hull of the retained calibration locations contains at most 2 ⌈ M r n ⌉ + 1 2\lceil Mr_n\rceil+1 2 ⌈ M r n ⌉ + 1 locations. Therefore, ∣ C ‾ n , 1 − α C O N C H ∣ ≤ 4 ⌈ M r n ⌉ + 2 |\overline{C}^{\mathrm{CONCH}}_{n,1-\alpha}|\le4\lceil Mr_n\rceil+2 ∣ C n , 1 − α CONCH ∣ ≤ 4 ⌈ M r n ⌉ + 2 . This proves ∣ C ‾ n , 1 − α C O N C H ∣ = O P ( r n ) |\overline{C}^{\mathrm{CONCH}}_{n,1-\alpha}|=O_{\mathbb{P}}(r_n) ∣ C n , 1 − α CONCH ∣ = O P ( r n ) . Since r n / n → 0 r_n/n\to0 r n / n → 0 , its normalized cardinality converges to zero. □
Auxiliary lemma
Lemma B.3. Conditional on ( D n ′ , D n , 1 , Y n ) (D'_n, D_{n,1}, \mathbf{Y}_n) ( D n ′ , D n , 1 , Y n ) , let π \pi π be uniform on Π t \Pi_t Π t and write
V t , n π = Var π ( S n ( π ( Y n ) , t ) ∣ t − ξ ^ n / 2 ∣ ∣ D n ′ , D n , 1 , Y n ) , t ≠ ξ ^ n / 2 . V^\pi_{t,n} = \operatorname{Var}_\pi\left(\left.\frac{S_n(\pi(\mathbf{Y}_n),t)}{\lvert t-\widehat{\xi}_{n/2}\rvert}\right|D'_n,D_{n,1},\mathbf{Y}_n\right), \qquad t \ne\widehat{\xi}_{n/2}. V t , n π = Var π ( ∣ t − ξ n /2 ∣ S n ( π ( Y n ) , t ) D n ′ , D n , 1 , Y n ) , t = ξ n /2 . Then
E π [ S n ( π ( Y n ) , t ) ∣ t − ξ ^ n / 2 ∣ ∣ D n ′ , D n , 1 , Y n ] = { μ ^ t , n , L , t > ξ ^ n / 2 , μ ^ t , n , R , t < ξ ^ n / 2 , \mathbb{E}_\pi\left[\left.\frac{S_n(\pi(\mathbf{Y}_n),t)}{\lvert t-\widehat{\xi}_{n/2}\rvert}\right|D'_n,D_{n,1},\mathbf{Y}_n\right]
=
\begin{cases}
\widehat{\mu}_{t,n,L}, & t > \widehat{\xi}_{n/2},\\
\widehat{\mu}_{t,n,R}, & t < \widehat{\xi}_{n/2},
\end{cases} E π [ ∣ t − ξ n /2 ∣ S n ( π ( Y n ) , t ) D n ′ , D n , 1 , Y n ] = { μ t , n , L , μ t , n , R , t > ξ n /2 , t < ξ n /2 , and the corresponding variance satisfies
V t , n π ≤ { m v ^ n t ( t − ξ ^ n / 2 ) , t > ξ ^ n / 2 , m v ^ n ( m − t ) ( ξ ^ n / 2 − t ) , t < ξ ^ n / 2 . V^\pi_{t,n} \le
\begin{cases}
\frac{m\widehat{v}_n}{t(t-\widehat{\xi}_{n/2})}, & t > \widehat{\xi}_{n/2},\\
\frac{m\widehat{v}_n}{(m-t)(\widehat{\xi}_{n/2}-t)}, & t < \widehat{\xi}_{n/2}.
\end{cases} V t , n π ≤ ⎩ ⎨ ⎧ t ( t − ξ n /2 ) m v n , ( m − t ) ( ξ n /2 − t ) m v n , t > ξ n /2 , t < ξ n /2 . If Δ t , ξ ^ n / 2 < 0 \Delta_{t,\widehat{\xi}_{n/2}}<0 Δ t , ξ n /2 < 0 , then p t , n ≤ V t , n π / ( V t , n π + Δ t , ξ ^ n / 2 2 ) p_{t,n}\le V^\pi_{t,n}/(V^\pi_{t,n}+\Delta^2_{t,\widehat{\xi}_{n/2}}) p t , n ≤ V t , n π / ( V t , n π + Δ t , ξ n /2 2 ) . Further, E [ v ^ n ] ≤ σ 0 , n 2 + σ 1 , n 2 + ( μ 0 , n − μ 1 , n ) 2 / 4 \mathbb{E}[\widehat{v}_n]\le\sigma^2_{0,n}+\sigma^2_{1,n}+(\mu_{0,n}-\mu_{1,n})^2/4 E [ v n ] ≤ σ 0 , n 2 + σ 1 , n 2 + ( μ 0 , n − μ 1 , n ) 2 /4 .
Proof. Suppose t > ξ ^ n / 2 t>\widehat{\xi}_{n/2} t > ξ n /2 . By (19) ,
S n ( π ( Y n ) , t ) t − ξ ^ n / 2 = 1 t − ξ ^ n / 2 ∑ i = ξ ^ n / 2 + 1 t ℓ ^ n ( Y π ( i ) , n ) . \frac{S_n(\pi(\mathbf{Y}_n),t)}{t-\widehat{\xi}_{n/2}}
=
\frac{1}{t-\widehat{\xi}_{n/2}}\sum_{i=\widehat{\xi}_{n/2}+1}^{t}\widehat{\ell}_n(Y_{\pi(i),n}). t − ξ n /2 S n ( π ( Y n ) , t ) = t − ξ n /2 1 i = ξ n /2 + 1 ∑ t ℓ n ( Y π ( i ) , n ) . The set { π ( ξ ^ n / 2 + 1 ) , … , π ( t ) } \{\pi(\widehat{\xi}_{n/2}+1),\ldots,\pi(t)\} { π ( ξ n /2 + 1 ) , … , π ( t )} is sampled uniformly without replacement from [ t ] [t] [ t ] and has size t − ξ ^ n / 2 t-\widehat{\xi}_{n/2} t − ξ n /2 . Since the expression above averages the scores over these indices,
E π [ S n ( π ( Y n ) , t ) t − ξ ^ n / 2 ∣ D n ′ , D n , 1 , Y n ] = μ ^ t , n , L , \mathbb{E}_\pi\left[\left.\frac{S_n(\pi(\mathbf{Y}_n),t)}{t-\widehat{\xi}_{n/2}}\right|D'_n,D_{n,1},\mathbf{Y}_n\right]=\widehat{\mu}_{t,n,L}, E π [ t − ξ n /2 S n ( π ( Y n ) , t ) D n ′ , D n , 1 , Y n ] = μ t , n , L , V t , n π = ξ ^ n / 2 ( t − ξ ^ n / 2 ) ( t − 1 ) { 1 t ∑ i = 1 t ( ℓ ^ n ( Y i , n ) − μ ^ t , n , L ) 2 } . (45) V^\pi_{t,n}
=
\frac{\widehat{\xi}_{n/2}}{(t-\widehat{\xi}_{n/2})(t-1)}
\left\{\frac{1}{t}\sum_{i=1}^{t}\left(\widehat{\ell}_n(Y_{i,n})-\widehat{\mu}_{t,n,L}\right)^2\right\}. \tag*{(45)} V t , n π = ( t − ξ n /2 ) ( t − 1 ) ξ n /2 { t 1 i = 1 ∑ t ( ℓ n ( Y i , n ) − μ t , n , L ) 2 } . (45) Furthermore,
1 t ∑ i = 1 t ( ℓ ^ n ( Y i , n ) − μ ^ t , n , L ) 2 ≤ 1 t ∑ i = 1 t ( ℓ ^ n ( Y i , n ) − μ 0 , n + μ 1 , n 2 ) 2 ≤ m t v ^ n . \frac{1}{t}\sum_{i=1}^{t}\left(\widehat{\ell}_n(Y_{i,n})-\widehat{\mu}_{t,n,L}\right)^2
\le
\frac{1}{t}\sum_{i=1}^{t}\left(\widehat{\ell}_n(Y_{i,n})-\frac{\mu_{0,n}+\mu_{1,n}}{2}\right)^2
\le
\frac{m}{t}\widehat{v}_n. t 1 i = 1 ∑ t ( ℓ n ( Y i , n ) − μ t , n , L ) 2 ≤ t 1 i = 1 ∑ t ( ℓ n ( Y i , n ) − 2 μ 0 , n + μ 1 , n ) 2 ≤ t m v n . Since ξ ^ n / 2 / ( t − 1 ) ≤ 1 \widehat{\xi}_{n/2}/(t-1)\le1 ξ n /2 / ( t − 1 ) ≤ 1 , combining this with (B.16) proves the stated mean and variance bound when t > ξ ^ n / 2 t>\widehat{\xi}_{n/2} t > ξ n /2 . The case t < ξ ^ n / 2 t<\widehat{\xi}_{n/2} t < ξ n /2 follows analogously by considering the negative average of ξ ^ n / 2 − t \widehat{\xi}_{n/2}-t ξ n /2 − t scores sampled without replacement from { t + 1 , … , m } \{t+1,\ldots,m\} { t + 1 , … , m } .
By the definition of the permutation p p p -value,
p t , n = P π ( S n ( π ( Y n ) , t ) ∣ t − ξ ^ n / 2 ∣ − E π [ S n ( π ( Y n ) , t ) ∣ t − ξ ^ n / 2 ∣ ∣ D n , i ′ , D n , 1 , Y n ] ≤ Δ t , ξ ^ n / 2 | D n , i ′ , D n , 1 , Y n ) . p_{t,n}=\mathbb{P}_{\pi}\left(\frac{S_n(\pi(\mathbf{Y}_n),t)}{|t-\widehat{\xi}_{n/2}|}-\mathbb{E}_{\pi}\left[\left.\frac{S_n(\pi(\mathbf{Y}_n),t)}{|t-\widehat{\xi}_{n/2}|}\right|D'_{n,i},D_{n,1},\mathbf{Y}_n\right]\leq\Delta_{t,\widehat{\xi}_{n/2}}\ \middle|\ D'_{n,i},D_{n,1},\mathbf{Y}_n\right). p t , n = P π ( ∣ t − ξ n /2 ∣ S n ( π ( Y n ) , t ) − E π [ ∣ t − ξ n /2 ∣ S n ( π ( Y n ) , t ) D n , i ′ , D n , 1 , Y n ] ≤ Δ t , ξ n /2 D n , i ′ , D n , 1 , Y n ) .
Cantelli’s inequality therefore gives the bound on p t , n p_{t,n} p t , n whenever Δ t , ξ ^ n / 2 < 0 \Delta_{t,\widehat{\xi}_{n/2}}<0 Δ t , ξ n /2 < 0 .
Finally, for i ≤ ξ n ′ i\leq\xi'_n i ≤ ξ n ′ , the unconditional mean of ℓ ^ n ( Y i , n ) \widehat{\ell}_n(Y_{i,n}) ℓ n ( Y i , n ) is μ 0 , n \mu_{0,n} μ 0 , n , while for i > ξ n ′ i>\xi'_n i > ξ n ′ it is μ 1 , n \mu_{1,n} μ 1 , n . In either case, its distance from ( μ 0 , n + μ 1 , n ) / 2 (\mu_{0,n}+\mu_{1,n})/2 ( μ 0 , n + μ 1 , n ) /2 is ( μ 0 , n − μ 1 , n ) / 2 (\mu_{0,n}-\mu_{1,n})/2 ( μ 0 , n − μ 1 , n ) /2 . Therefore,
E [ v ^ n ] = ξ n ′ m { σ 0 , n 2 + ( μ 0 , n − μ 1 , n ) 2 4 } + m − ξ n ′ m { σ 1 , n 2 + ( μ 0 , n − μ 1 , n ) 2 4 } , \mathbb{E}[\widehat{v}_n]=\frac{\xi'_n}{m}\left\{\sigma_{0,n}^{2}+\frac{(\mu_{0,n}-\mu_{1,n})^{2}}{4}\right\}+\frac{m-\xi'_n}{m}\left\{\sigma_{1,n}^{2}+\frac{(\mu_{0,n}-\mu_{1,n})^{2}}{4}\right\}, E [ v n ] = m ξ n ′ { σ 0 , n 2 + 4 ( μ 0 , n − μ 1 , n ) 2 } + m m − ξ n ′ { σ 1 , n 2 + 4 ( μ 0 , n − μ 1 , n ) 2 } ,
which proves the final part.
Proof of Corollary 5.2: oracle localization rates
If ℓ ^ n = ℓ n \widehat{\ell}_n=\ell_n ℓ n = ℓ n , we observe that
μ 0 , n = KL ( P 0 , n ∥ P 1 , n ) , μ 1 , n = − KL ( P 1 , n ∥ P 0 , n ) , ε n = 0. \mu_{0,n}=\operatorname{KL}(P_{0,n}\Vert P_{1,n}),\qquad\mu_{1,n}=-\operatorname{KL}(P_{1,n}\Vert P_{0,n}),\qquad\varepsilon_n=0. μ 0 , n = KL ( P 0 , n ∥ P 1 , n ) , μ 1 , n = − KL ( P 1 , n ∥ P 0 , n ) , ε n = 0.
Hence, by definition, μ 0 , n − μ 1 , n = J n \mu_{0,n}-\mu_{1,n}=J_n μ 0 , n − μ 1 , n = J n , and the assumptions of the corollary imply Assumption 2. Moreover,
r n = 1 ∨ σ 0 , n 2 + σ 1 , n 2 J n 2 ≤ 1 ∨ 2 C v J n = O ( J n − 1 ) . r_n=1\vee\frac{\sigma_{0,n}^{2}+\sigma_{1,n}^{2}}{J_n^{2}}\leq1\vee\frac{2C_v}{J_n}=O(J_n^{-1}). r n = 1 ∨ J n 2 σ 0 , n 2 + σ 1 , n 2 ≤ 1 ∨ J n 2 C v = O ( J n − 1 ) .
Since n J n → ∞ nJ_n\to\infty n J n → ∞ , we have r n / n → 0 r_n/n\to0 r n / n → 0 . Proposition 3.2 and Theorems 5.1 and 3.3 give the stated oracle localization rates.
Proof of Proposition 5.3: lower bound on cardinality
We start by writing d = ( 1 − α ) 2 / 2 d=(1-\alpha)^2/2 d = ( 1 − α ) 2 /2 , and considering the interval J n = [ ξ n − d / J n , ξ n + d / J n ] ∩ Z \mathcal{J}_n=[\xi_n-d/J_n,\xi_n+d/J_n]\cap\mathbb{Z} J n = [ ξ n − d / J n , ξ n + d / J n ] ∩ Z . Since J n → 0 J_n\to0 J n → 0 , n J n → ∞ nJ_n\to\infty n J n → ∞ , and ξ n / n → τ ∈ ( 0 , 1 ) \xi_n/n\to\tau\in(0,1) ξ n / n → τ ∈ ( 0 , 1 ) , for large n n n , it holds that J n ⊆ T \mathcal{J}_n\subseteq\mathcal{T} J n ⊆ T and ∣ J n ∣ ≥ d / J n |\mathcal{J}_n|\geq d/J_n ∣ J n ∣ ≥ d / J n .
Recall that P t , n = P 0 , n ⊗ t ⊗ P 1 , n ⊗ ( n − t ) P_{t,n}=P_{0,n}^{\otimes t}\otimes P_{1,n}^{\otimes(n-t)} P t , n = P 0 , n ⊗ t ⊗ P 1 , n ⊗ ( n − t ) . Moreover, KL between product measures is sum of KL computed between individual measures. For t ∈ J n t\in\mathcal{J}_n t ∈ J n , therefore we have that
KL ( P ξ n , n ∥ P t , n ) ≤ ∣ t − ξ n ∣ J n ≤ d . \operatorname{KL}(P_{\xi_n,n}\Vert P_{t,n})\leq|t-\xi_n|J_n\leq d. KL ( P ξ n , n ∥ P t , n ) ≤ ∣ t − ξ n ∣ J n ≤ d .
Pinsker’s inequality and (25) therefore give, for each t ∈ J n t\in\mathcal{J}_n t ∈ J n ,
P ξ n , n ( t ∈ C ~ n ) ≥ P t , n ( t ∈ C ~ n ) − TV ( P ξ n , n , P t , n ) ≥ ( 1 − α ) − d / 2 = ( 1 − α ) / 2. \mathbb{P}_{\xi_n,n}(t\in\widetilde{\mathcal{C}}_n)\geq\mathbb{P}_{t,n}(t\in\widetilde{\mathcal{C}}_n)-\operatorname{TV}(P_{\xi_n,n},P_{t,n})\geq(1-\alpha)-\sqrt{d/2}=(1-\alpha)/2. P ξ n , n ( t ∈ C n ) ≥ P t , n ( t ∈ C n ) − TV ( P ξ n , n , P t , n ) ≥ ( 1 − α ) − d /2 = ( 1 − α ) /2.
Thus, each t ∈ J n t\in\mathcal{J}_n t ∈ J n can be missed by C ~ n \widetilde{\mathcal{C}}_n C n with probability at most ( 1 + α ) / 2 (1+\alpha)/2 ( 1 + α ) /2 . Summing over t ∈ J n t\in\mathcal{J}_n t ∈ J n gives
E X ∼ P ξ n , n [ ∣ J n ∖ C ~ n ∣ ] ≤ 1 + α 2 ∣ J n ∣ . \mathbb{E}_{X\sim P_{\xi_n,n}}\left[|\mathcal{J}_n\setminus\widetilde{\mathcal{C}}_n|\right]\leq\frac{1+\alpha}{2}|\mathcal{J}_n|. E X ∼ P ξ n , n [ ∣ J n ∖ C n ∣ ] ≤ 2 1 + α ∣ J n ∣.
Now, if C ~ n \widetilde{C}_n C n contains fewer than a fraction ( 1 − α ) / 4 (1-\alpha)/4 ( 1 − α ) /4 of the locations in J n \mathcal{J}_n J n , then J n ∖ C ~ n \mathcal{J}_n\setminus\widetilde{C}_n J n ∖ C n must contain more than a fraction ( 3 + α ) / 4 (3+\alpha)/4 ( 3 + α ) /4 of locations in J n \mathcal{J}_n J n . Hence, by Markov’s inequality,
P ξ , n ( ∣ C ~ n ∩ J n ∣ < 1 − α 4 ∣ J n ∣ ) ≤ ( 1 + α ) / 2 ( 3 + α ) / 4 = 2 ( 1 + α ) 3 + α . \mathbb{P}_{\xi,n}\left(\left|\widetilde{C}_n\cap\mathcal{J}_n\right|<\frac{1-\alpha}{4}|\mathcal{J}_n|\right)\leq\frac{(1+\alpha)/2}{(3+\alpha)/4}=\frac{2(1+\alpha)}{3+\alpha}. P ξ , n ( C n ∩ J n < 4 1 − α ∣ J n ∣ ) ≤ ( 3 + α ) /4 ( 1 + α ) /2 = 3 + α 2 ( 1 + α ) .
Consequently, with probability at least ( 1 − α ) / ( 3 + α ) (1-\alpha)/(3+\alpha) ( 1 − α ) / ( 3 + α ) ,
∣ C ~ n ∣ ≥ 1 − α 4 ∣ J n ∣ ≥ ( 1 − α ) d 4 J n = ( 1 − α ) 3 8 J n . |\widetilde{C}_n|\geq\frac{1-\alpha}{4}|\mathcal{J}_n|\geq\frac{(1-\alpha)d}{4J_n}=\frac{(1-\alpha)^3}{8J_n}. ∣ C n ∣ ≥ 4 1 − α ∣ J n ∣ ≥ 4 J n ( 1 − α ) d = 8 J n ( 1 − α ) 3 .
This proves (26) with c α = ( 1 − α ) 3 / 8 c_\alpha=(1-\alpha)^3/8 c α = ( 1 − α ) 3 /8 and p α = ( 1 − α ) / ( 3 + α ) p_\alpha=(1-\alpha)/(3+\alpha) p α = ( 1 − α ) / ( 3 + α ) .
Proof of results from Appendix A
Proof of Proposition A.1
Under H 0 , n \mathcal{H}_{0,n} H 0 , n , π ( X ) = d X \pi(\mathbf{X})\mathrel{\overset{d}{=}}\mathbf{X} π ( X ) = d X for every π ∈ S n \pi\in\mathfrak{S}_n π ∈ S n . Composition within S n \mathfrak{S}_n S n shows that the values p n ( π ( x ) ) p_n(\pi(\mathbf{x})) p n ( π ( x )) are normalized weak lower ranks of the scores S ( π ( x ) , n ) S(\pi(\mathbf{x}),n) S ( π ( x ) , n ) . Hence, for every u ∈ ( 0 , 1 ) u\in(0,1) u ∈ ( 0 , 1 ) ,
P H 0 , n ( p n ≤ u ) = E H 0 , n [ 1 ∣ S n ∣ ∑ π ∈ S n 1 { p n ( π ( X ) ) ≤ u } ] ≤ u . \mathbb{P}_{\mathcal{H}_{0,n}}(p_n\leq u)=\mathbb{E}_{\mathcal{H}_{0,n}}\left[\frac{1}{|\mathfrak{S}_n|}\sum_{\pi\in\mathfrak{S}_n}\mathbf{1}\{p_n(\pi(\mathbf{X}))\leq u\}\right]\leq u. P H 0 , n ( p n ≤ u ) = E H 0 , n [ ∣ S n ∣ 1 π ∈ S n ∑ 1 { p n ( π ( X )) ≤ u } ] ≤ u .
Taking u = β u=\beta u = β gives the detection bound.
Proof of Theorem A.2: finite-sample validity of DTL-CONCH
Suppose Assumption 1 holds for X \mathbf{X} X with changepoint at ξ ∈ [ n − 1 ] \xi\in[n-1] ξ ∈ [ n − 1 ] . We treat the detection rule A A A and the CPP score S S S fixed.
For a fixed sequence x \mathbf{x} x , write M ( x ) = ∑ π ∈ Π ξ 1 { A ( π ( x ) ) = 1 } M(\mathbf{x})=\sum_{\pi\in\Pi_\xi}\mathbf{1}\{A(\pi(\mathbf{x}))=1\} M ( x ) = ∑ π ∈ Π ξ 1 { A ( π ( x )) = 1 } . If A ( x ) = 1 A(\mathbf{x})=1 A ( x ) = 1 , then M ( x ) ≥ 1 M(\mathbf{x})\geq1 M ( x ) ≥ 1 since the identity permutation belongs to Π ξ \Pi_\xi Π ξ . For notational convenience, we set p ξ d e t ( x ) = 1 p^{\mathrm{det}}_\xi(\mathbf{x})=1 p ξ det ( x ) = 1 when A ( x ) = 0 A(\mathbf{x})=0 A ( x ) = 0 . Note that this does not affect the procedure.
Now, fix any x \mathbf{x} x with M ( x ) > 0 M(\mathbf{x})>0 M ( x ) > 0 . Then, for every π ∈ Π ξ \pi\in\Pi_\xi π ∈ Π ξ such that A ( π ( x ) ) = 1 A(\pi(\mathbf{x}))=1 A ( π ( x )) = 1 , we can write
p ξ d e t ( π ( x ) ) = ∑ σ ∈ Π ξ 1 { A ( σ ( x ) ) = 1 } 1 { S ( σ ( x ) , ξ ) ≤ S ( π ( x ) , ξ ) } M ( x ) . p^{\mathrm{det}}_\xi(\pi(\mathbf{x}))=\frac{\sum_{\sigma\in\Pi_\xi}\mathbf{1}\{A(\sigma(\mathbf{x}))=1\}\mathbf{1}\{S(\sigma(\mathbf{x}),\xi)\leq S(\pi(\mathbf{x}),\xi)\}}{M(\mathbf{x})}. p ξ det ( π ( x )) = M ( x ) ∑ σ ∈ Π ξ 1 { A ( σ ( x )) = 1 } 1 { S ( σ ( x ) , ξ ) ≤ S ( π ( x ) , ξ )} .
In words, p ξ d e t ( π ( x ) ) p^{\mathrm{det}}_\xi(\pi(\mathbf{x})) p ξ det ( π ( x )) is the normalized rank of S ( π ( x ) , ξ ) S(\pi(\mathbf{x}),\xi) S ( π ( x ) , ξ ) among the collection ${S(\sigma(\mathbf{x}),\xi):\sigma\in Π ξ , A ( σ ( x ) ) = 1 } \Pi_{\xi}, A(\sigma(x)) = 1\} Π ξ , A ( σ ( x )) = 1 } . As a result, by [8 Lemma 3] , we derive
1 M ( x ) ∑ π ∈ Π ξ 1 { A ( π ( x ) ) = 1 , p ξ d e t ( π ( x ) ) ≤ α } ≤ α \frac{1}{M(x)} \sum_{\pi\in\Pi_{\xi}} \mathbb{1}\left\{A(\pi(x)) = 1, p_{\xi}^{\mathrm{det}}(\pi(x)) \le\alpha\right\} \le\alpha M ( x ) 1 π ∈ Π ξ ∑ 1 { A ( π ( x )) = 1 , p ξ det ( π ( x )) ≤ α } ≤ α
and thus,
1 ∣ Π ξ ∣ ∑ π ∈ Π ξ 1 { A ( π ( x ) ) = 1 , p ξ d e t ( π ( x ) ) ≤ α } ≤ α M ( x ) ∣ Π ξ ∣ . (46) \frac{1}{|\Pi_{\xi}|} \sum_{\pi\in\Pi_{\xi}} \mathbb{1}\left\{A(\pi(x)) = 1, p_{\xi}^{\mathrm{det}}(\pi(x)) \le\alpha\right\} \le\frac{\alpha M(x)}{|\Pi_{\xi}|}. \tag*{(46)} ∣ Π ξ ∣ 1 π ∈ Π ξ ∑ 1 { A ( π ( x )) = 1 , p ξ det ( π ( x )) ≤ α } ≤ ∣ Π ξ ∣ α M ( x ) . (46)
Note that by construction, the same inequality holds when M ( x ) = 0 M(x) = 0 M ( x ) = 0 , since both sides are then zero.
Finally, since X = d π ( X ) \mathbf{X} \mathrel{\overset{d}{=}} \pi(\mathbf{X}) X = d π ( X ) for every π ∈ Π ξ \pi\in\Pi_{\xi} π ∈ Π ξ , by (C.1), we obtain that
P ξ ( A ( X ) = 1 , p ξ d e t ( X ) ≤ α ) = 1 ∣ Π ξ ∣ ∑ π ∈ Π ξ P ξ ( A ( π ( X ) ) = 1 , p ξ d e t ( π ( X ) ) ≤ α ) = E ξ [ 1 ∣ Π ξ ∣ ∑ π ∈ Π ξ 1 { A ( π ( X ) ) = 1 , p ξ d e t ( π ( X ) ) ≤ α } ] ≤ α ∣ Π ξ ∣ ∑ π ∈ Π ξ P ξ ( A ( π ( X ) ) = 1 ) = α P ξ ( A ( X ) = 1 ) . \begin{aligned}
\mathbb{P}_{\xi}\left(A(\mathbf{X}) = 1, p_{\xi}^{\mathrm{det}}(\mathbf{X}) \le\alpha\right) = \frac{1}{|\Pi_{\xi}|} \sum_{\pi\in\Pi_{\xi}} \mathbb{P}_{\xi}\left(A(\pi(\mathbf{X})) = 1, p_{\xi}^{\mathrm{det}}(\pi(\mathbf{X})) \le\alpha\right) \\
&= \mathbb{E}_{\xi}\left[\frac{1}{|\Pi_{\xi}|} \sum_{\pi\in\Pi_{\xi}} \mathbb{1}\left\{A(\pi(\mathbf{X})) = 1, p_{\xi}^{\mathrm{det}}(\pi(\mathbf{X})) \le\alpha\right\}\right] \\
&\le\frac{\alpha}{|\Pi_{\xi}|} \sum_{\pi\in\Pi_{\xi}} \mathbb{P}_{\xi}\left(A(\pi(\mathbf{X})) = 1\right) = \alpha\mathbb{P}_{\xi}\left(A(\mathbf{X}) = 1\right).
\end{aligned} P ξ ( A ( X ) = 1 , p ξ det ( X ) ≤ α ) = ∣ Π ξ ∣ 1 π ∈ Π ξ ∑ P ξ ( A ( π ( X )) = 1 , p ξ det ( π ( X )) ≤ α ) = E ξ ∣ Π ξ ∣ 1 π ∈ Π ξ ∑ 1 { A ( π ( X )) = 1 , p ξ det ( π ( X )) ≤ α } ≤ ∣ Π ξ ∣ α π ∈ Π ξ ∑ P ξ ( A ( π ( X )) = 1 ) = α P ξ ( A ( X ) = 1 ) .
On the event { A ( X ) = 1 } \{A(\mathbf{X}) = 1\} { A ( X ) = 1 } , the event ξ ∉ C n , 1 − α D T L − C O N C H \xi\notin\mathcal{C}^{\mathrm{DTL-CONCH}}_{n,1-\alpha} ξ ∈ / C n , 1 − α DTL − CONCH is exactly the event p ξ d e t ( X ) ≤ α p_{\xi}^{\mathrm{det}}(\mathbf{X}) \le\alpha p ξ det ( X ) ≤ α . Hence, we get
P ξ ( A ( X ) = 1 , ξ ∉ C n , 1 − α D T L − C O N C H ) ≤ α P ξ ( A ( X ) = 1 ) . \mathbb{P}_{\xi}\left(A(\mathbf{X}) = 1, \xi\notin\mathcal{C}^{\mathrm{DTL-CONCH}}_{n,1-\alpha}\right) \le\alpha\mathbb{P}_{\xi}\left(A(\mathbf{X}) = 1\right). P ξ ( A ( X ) = 1 , ξ ∈ / C n , 1 − α DTL − CONCH ) ≤ α P ξ ( A ( X ) = 1 ) .
Whenever the detection probability is positive, it further yields
P ξ ( ξ ∈ C n , 1 − α D T L − C O N C H ∣ A ( X ) = 1 ) ≥ 1 − α . \mathbb{P}_{\xi}\left(\xi\in\mathcal{C}^{\mathrm{DTL-CONCH}}_{n,1-\alpha} \mid A(\mathbf{X}) = 1\right) \ge1 - \alpha. P ξ ( ξ ∈ C n , 1 − α DTL − CONCH ∣ A ( X ) = 1 ) ≥ 1 − α .