Asymptotics of Sequential Composite Hypothesis Testing under Probabilistic Constraints

Jiachun Pan, Yonglong Li, Vincent Y. F. Tan

Introduction

In classical sequential hypothesis testing, such as Wald’s Sequential Probability Ratio Test (SPRT), the primary objective is typically to minimize the expected number of observations required to reach a decision. However, many practical applications—ranging from clinical trials to time-critical signal detection—demand more stringent guarantees. In these scenarios, an average time is insufficient; instead, the test must conclude within a fixed deadline $n$ with a high probability $1-\epsilon$.

This work addresses the composite version of this problem. We consider a simple null hypothesis $H_0$ against a composite alternative $H_1$ governed by a parameter $\gamma$ in a set $\Gamma$. The goal is to characterize the trade-off between Type-I and Type-II error probabilities as the time budget $n$ grows to infinity under these probabilistic stopping time constraints.

Methodology

The analysis centers on the Generalized Sequential Probability Ratio Test (GSPRT). Unlike the standard SPRT, the GSPRT employs a maximum likelihood approach to manage the uncertainty inherent in the composite alternative hypothesis. To derive the fundamental limits, the researchers utilize several advanced mathematical tools:

  • Information-Theoretic Tools: The "change-of-measure" technique is employed to establish strong converses, proving that the identified limits are indeed optimal.
  • Asymptotic Analysis: Error probabilities are decomposed into first-order terms (the error exponents) and second-order terms (the fine-grained corrections for finite $n$).
  • A New Central Limit-Type Result: A significant technical contribution is the characterization of the maximum of an uncountable set of log-likelihood ratios. The authors derive a novel version of the Central Limit Theorem (CLT) for this maximum, which deviates from the classical Wilks’ Theorem typically found in standard statistical literature.

Key Insights and Ideas

  • Rectangular Error Region: At the first order, the set of achievable error exponents $(E_0, E_1)$ forms a rectangle. This implies that, unlike fixed-length testing, there is no smooth trade-off curve; both exponents can be maximized up to their individual limits simultaneously.
  • Strong Converse and Robustness: The first-order error exponents are independent of the probability threshold $\epsilon$. Whether the test is required to finish by time $n$ with 90% or 99.9% probability, the asymptotic rate of error decay remains unchanged.
  • The Second-Order "Backoff": For finite $n$, a penalty of order $\Theta(1/\sqrt{n})$ emerges. This "backoff" term is determined by the relative entropy variance $V$ and the inverse Gaussian cumulative distribution function ($\Phi^{-1}$).
  • Departure from Wilks’ Theorem: While log-likelihood ratios often follow a chi-squared distribution in standard settings, the authors show that under these specific sequential constraints and a simple null, a Gaussian distribution emerges for the maximum log-likelihood ratio.

Key Results

The optimal first-order error exponents are bounded by the minimum Kullback-Leibler (KL) divergences between the null and the alternative family:

  • $E_0 \leq \min_{\gamma \in \Gamma} D(p_\gamma || p_0)$
  • $E_1 \leq \min_{\gamma \in \Gamma} D(p_0 || p_\gamma)$
Geometric representation of the composite hypothesis testing problem in the probability simplex.

For finite alphabets, the second-order error region is explicitly defined. The cost of the probabilistic constraint is quantified as: $$G \leq \Phi^{-1}(\epsilon) \sqrt{V}$$ where $V$ is the relative entropy variance. This result provides a precise estimate of error probabilities for practical, finite-length tests, offering a significant improvement over first-order approximations alone.

Limitations and Future Work

While this work provides a comprehensive characterization for finite alphabets and simple null hypotheses, several avenues for future research remain. Extending the second-order results to continuous alphabets, such as general Gaussian processes, is a natural progression. Additionally, investigating the fully composite-vs-composite setting—where both $H_0$ and $H_1$ are families of distributions—presents a more complex challenge. Finally, relaxing the geometric assumptions on the parameter set $\Gamma$ (currently assumed to be convex and compact) would broaden the applicability of these results to more irregular statistical models.

Summary updated

BibTeX
@article{pan2022asymptotics,
  author = {Jiachun Pan and Yonglong Li and Vincent Y. F. Tan},
  title = {{Asymptotics of Sequential Composite Hypothesis Testing under Probabilistic Constraints}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  doi = {10.1109/tit.2022.3164139},
}
Figure