First versus full or first versus last: U-statistic change-point tests under fixed and local alternatives

1. Problem Statement

The paper addresses the construction and comparison of CUSUM-type change-point tests based on U-statistics for detecting structural breaks in the parameter $\theta$ of a stationary stochastic process.

When extending the classical CUSUM test (which uses the sample mean) to general parameters estimated by U-statistics, two distinct approaches emerge for constructing the test statistic at a potential change-point $k$:

1. First-vs-Full ($T_1$): Compares the estimator based on the first $k$ observations ($\hat{\theta}_{1:k}$) against the estimator based on the entire sample ($\hat{\theta}_{1:n}$).
2. First-vs-Last ($T_2$): Compares the estimator based on the first $k$ observations ($\hat{\theta}_{1:k}$) against the estimator based on the remaining $n-k$ observations ($\hat{\theta}_{(k+1):n}$).

While these two approaches are identical for linear statistics (like the sample mean), they differ for non-linear U-statistics. The authors investigate whether these differences are merely finite-sample artifacts or if they lead to fundamentally different asymptotic behaviors and power properties, particularly under fixed alternatives (where the magnitude of the change does not vanish as $n \to \infty$).

2. Methodology

The authors analyze the asymptotic behavior of the two test statistics under three regimes:

• Null Hypothesis ($H_0$): No change occurs.
• Local Alternatives: The distribution changes slightly such that the parameter difference is of order $O(n^{-1/2})$.
• Fixed Alternatives: The distribution changes significantly (parameter difference is constant).

Key Definitions:
Let $h$ be a symmetric kernel function. The U-statistic is defined as:
$$U_n = \binom{n}{2}^{-1} \sum_{1 \le i < j \le n} h(X_i, X_j)$$
The test statistics are defined as:
$$T_1(h) = \max_{1 \le k \le n} \frac{k}{\sqrt{n}} |U_{1:k} - U_{1:n}|$$
$$T_2(h) = \max_{1 \le k \le n} \frac{k(n-k)}{n^{3/2}} |U_{1:k} - U_{(k+1):n}|$$

Theoretical Framework:

• Hoeffding Decomposition: The authors utilize the Hoeffding decomposition of U-statistics to separate linear and degenerate components.
• Weak Dependence: The results are derived for strongly stationary sequences that satisfy Near Epoch Dependence (NED) conditions (specifically P-NED), allowing for heavy-tailed distributions and short-range dependence.
• Limit Processes: Under $H_0$ and local alternatives, the processes are scaled by $n^{-1/2}$. Under fixed alternatives, they are scaled by $n^{-1}$.

3. Key Contributions and Results

A. Asymptotic Equivalence under Null and Local Alternatives

• Result: Under the null hypothesis and under sequences of local alternatives, the two test statistics are asymptotically equivalent.
• Implication: Both $T_1$ and $T_2$, when studentized by the long-run variance, converge to the supremum of a Brownian bridge ($\sup |B(t)|$). Consequently, they share the same critical values and asymptotic power in large samples. This explains why simulation results for large $n$ (e.g., $n=4000$) show negligible differences in power.

B. Divergence under Fixed Alternatives

• Result: Under fixed alternatives, the two statistics converge to different deterministic limit functions, denoted $\Psi_1(t)$ and $\Psi_2(t)$.
• The Criterion: The relative power of the two tests is determined by a quantity called the eccentricity ($\rho_{FG}$):
  $$\rho_{FG} = \theta_{FG} - \frac{\theta_F + \theta_G}{2}$$
  Where:
  • $\theta_F = E[h(X, X')]$ (parameter before change)
  • $\theta_G = E[h(Y, Y')]$ (parameter after change)
  • $\theta_{FG} = E[h(X, Y')]$ (mixed parameter)
• Power Ranking Rule:
  1. If $\text{sign}(\rho_{FG}) = \text{sign}(\theta_G - \theta_F)$, the First-vs-Full test is more powerful.
  2. If $\text{sign}(\rho_{FG}) \neq \text{sign}(\theta_G - \theta_F)$, the First-vs-Last test is more powerful.
  3. If $\rho_{FG} = 0$, the tests are equally powerful (this occurs if the U-statistic is strictly linear).

C. Specific Applications

The authors derive explicit conditions for four common U-statistics:

1. Gini's Mean Difference ($h(x,y) = |x-y|$):

   • For scale changes in normal distributions, $\rho_{FG} \ge 0$.
   • Conclusion: If the scale increases ($\theta_G > \theta_F$), First-vs-Full is superior. If the scale decreases, First-vs-Last is superior. This holds regardless of the change location or distribution shape.

2. Sample Variance ($h(x,y) = (x-y)^2/2$):

   • $\rho_{FG} = \frac{1}{2}(\mu_F - \mu_G)^2 \ge 0$.
   • Conclusion: If there is no change in mean, both tests are equally powerful. If there is a change in mean, the ranking follows the same rule as Gini's mean difference (First-vs-Full better for variance increase, First-vs-Last for decrease).

3. Sample Covariance:

   • Similar to variance, the eccentricity depends on the product of mean shifts. The same ranking logic applies.

4. Kendall's Tau:

   • Unlike the previous cases, $\rho_{FG}$ can be positive, negative, or zero depending on the correlation structure.
   • Conclusion: The "better" test depends entirely on the specific correlation change. For example, if correlations decrease from a positive value to zero, First-vs-Full may be better; if they change from positive to negative, the ranking might flip.

D. Consistency and Estimation

• Consistency: Both tests are consistent (power $\to 1$) if either $\theta_F \neq \theta_G$ or $\rho_{FG} \neq 0$. Notably, even if the parameter $\theta$ remains constant (e.g., variance is constant but mean shifts), the tests can still detect the change if $\rho_{FG} \neq 0$.
• Change-Point Estimation: The authors provide conditions under which the argmax estimators ($\hat{\tau}$) are consistent. They show that for certain combinations of $\theta_F, \theta_G,$ and $\rho_{FG}$, the estimator may be inconsistent (converging to a wrong location), highlighting that the choice of test statistic affects not just detection power but also localization accuracy.

4. Significance and Practical Implications

1. Resolution of a Debate: The paper settles the debate on whether First-vs-Last is universally superior. It demonstrates that no single approach is uniformly better; the optimal choice depends on the direction of the change and the specific kernel properties.
2. Small Sample Guidance: While asymptotic equivalence holds for large $n$, the paper provides a rigorous criterion for small-to-moderate sample sizes where differences in power are substantial (up to 10% in simulations).
3. Data-Driven Selection: The authors provide a simple, computable criterion ($\rho_{FG}$ vs. $\theta_G - \theta_F$) for practitioners to decide which test to use before analyzing data.
4. Real-World Application: The paper applies these findings to the Colorado River discharge data (Lees Ferry vs. Cameo).
   • For the Lees Ferry series (post-dam construction), the variance decreased. The First-vs-Last test correctly detected the change with a p-value of 0.019, while First-vs-Full was marginal (0.076).
   • For the correlation between the two series, the correlation decreased. The First-vs-Full test was more powerful (p-value 0.006 vs 0.02).
   • This real-world example validates the theoretical prediction that the "best" test flips depending on the nature of the structural break.

Conclusion

The paper establishes that while First-vs-Full and First-vs-Last CUSUM tests are asymptotically equivalent under the null and local alternatives, they exhibit distinct behaviors under fixed alternatives. The eccentricity of the kernel function serves as the decisive factor for power ranking. Practitioners should not default to one method but should evaluate the expected direction of change and the specific kernel properties to maximize detection power, particularly in finite samples.