🔢 mathematics

Second-Order Asymptotics of Two-Sample Tests

This paper generalizes the Gutman two-sample test by replacing the Jensen-Shannon divergence with an arbitrary divergence, demonstrating that while all such divergence tests achieve the optimal first-order error exponent, those utilizing invariant divergences further match the Gutman test's second-order asymptotic performance.

Original authors: K V Harsha, Jithin Ravi, Tobias Koch

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: K V Harsha, Jithin Ravi, Tobias Koch

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery: Are these two piles of data coming from the same source, or are they imposters?

In the world of statistics, this is called "two-sample testing." You have two long lists of random numbers (let's call them Sequence X and Sequence Y). Maybe they are both lists of dice rolls from the same fair die, or maybe one is from a fair die and the other is from a weighted, cheating die. Your job is to look at the lists and shout, "Same!" or "Different!" without knowing the secret recipe (the probability distribution) behind either list.

The Old Detective's Tool: The Gutman Test

For a long time, the best detective tool for this job was the Gutman test. Think of it like a "Similarity Score." The Gutman test takes the two lists, counts up how often each number appears (creating an "empirical distribution"), and then measures the distance between them using a specific ruler called the Jensen-Shannon (JS) divergence.

If the distance is small, the detective says, "They look the same!" (Null Hypothesis). If the distance is huge, they say, "They are different!" (Alternative Hypothesis).

The New Idea: The "Divergence Test"

The authors of this paper asked a fun question: What if we swapped the JS ruler for a different kind of ruler?

There are many ways to measure "distance" between two lists of numbers. Some are called Rényi divergences, others are f-divergences, and so on. The paper proposes a generalized "Divergence Test" that lets you pick any of these rulers to do the job.

The Big Discovery: Does the Ruler Matter?

Here is where the magic happens. The authors ran the numbers to see if changing the ruler changed the detective's success rate. They looked at two levels of success:

The Long-Run Success (First-Order): As the lists get infinitely long, how fast does the chance of making a mistake drop?
- The Finding: It turns out, it doesn't matter which ruler you use! Whether you use the classic JS ruler, the Rényi ruler, or any other "invariant" ruler, the speed at which your mistakes disappear is exactly the same. They all achieve the "optimal" speed.
- The Speed Limit: The paper proves that no matter what, you cannot beat a specific speed limit determined by something called the Bhattacharyya distance (a fancy way of measuring how much two probability distributions overlap). The best any test can do is make the error probability drop at a rate of $2 \times$ the Bhattacharyya distance. The new Divergence Test hits this ceiling perfectly, no matter which ruler you pick.
The Fine-Tuned Success (Second-Order): This is the "teenager" level of detail. It asks: If we have a fixed amount of time (a fixed sample size $n$ ), how close can we get to the perfect answer?
- The Finding: If you use a ruler that is "invariant" (a special mathematical property that means the ruler behaves consistently no matter how you stretch or shrink the data), you get the exact same fine-tuned performance as the classic Gutman test.
- The "Invariance" Club: The paper lists a huge club of rulers that are "invariant," including the famous Kullback-Leibler (KL) divergence and the JS divergence. If you pick one of these, you are just as good as the original Gutman test.

What About the "Tricky" Rulers?

The paper also looked at rulers that are not "invariant."

The Verdict: The paper shows that even with these tricky, non-invariant rulers, you still get the same long-run speed (the first-order result) as the Gutman test. You still hit that optimal $2 \times$ Bhattacharyya distance limit.
The Unknown: However, the authors admit they cannot yet prove exactly how these tricky rulers perform in the "fine-tuned" (second-order) scenario. It's like saying, "We know this car drives fast on the highway, but we haven't finished testing how it handles sharp turns yet." They suspect the performance might be different, but the math to prove it is too hard right now because the "tricky" rulers depend on secrets about the data that the detective doesn't know.

The "Robust" Connection

The paper also connects this detective work to another field called Robust Goodness-of-Fit testing. They show that the Gutman test is actually a special version of a "Generalized Likelihood Ratio Test" (GLRT). It's like realizing that your favorite detective story was actually a specific chapter in a much bigger, more famous book about robust testing. This connection helps explain why the Gutman test works so well and confirms that the new Divergence Test is just as solid.

Summary for the Curious Teen

The Main Point: You can swap the standard ruler (JS divergence) for almost any other "invariant" ruler in your two-sample test, and you won't lose any performance. You get the same best possible speed for catching errors.
The Catch: If you pick a ruler that isn't "invariant," you still get the best long-run speed, but we don't fully know how it behaves in the short run (the second-order details) yet.
The Proof: The authors didn't just guess; they used rigorous math (Taylor series, eigenvalues, and chi-square distributions) to prove that the first-order speed is optimal and that the second-order performance is identical for all invariant divergences.
The Limits: They explicitly state that extending these "fine-tuned" results to infinite data types (like continuous numbers on a line) is currently too hard to solve, so their results are strictly for lists of discrete items (like dice rolls or letters).

So, if you are building a system to tell if two data streams are the same, you have a lot of freedom to choose your "distance ruler." As long as you pick one from the "invariant" club, you are guaranteed to be as sharp as the best detective in the business.

Technical Summary: Second-Order Asymptotics of Two-Sample Tests

Problem Formulation
The paper addresses the fundamental problem of two-sample testing in statistical hypothesis testing. The objective is to determine whether two independent sequences of i.i.d. random variables, $X^n$ and $Y^n$ , generated from distributions $P_1$ and $P_2$ respectively, originate from the same underlying distribution. This is framed as a binary hypothesis test:

$H_0: P_1 = P_2$
$H_1: P_1 \neq P_2$

The study operates in Stein's regime, where the type-I error probability ( $\alpha_n$ ) is constrained to be below a fixed $\epsilon \in (0, 1)$ , and the goal is to analyze the asymptotic behavior of the type-II error probability ( $\beta_n$ ) as the sample size $n \to \infty$ . Specifically, the authors characterize the first-order term ( $\beta'$ ) and the second-order term ( $\beta''$ ) of the error exponent $-\frac{1}{n}\ln \beta_n$ .

Methodology and Definitions
The paper generalizes the Gutman test, which relies on the Jensen-Shannon (JS) divergence, by introducing a "divergence test." This test accepts $H_0$ if the divergence $D(P_{X^n} \| P_{Y^n})$ between the empirical distributions (types) of the two sequences is below a threshold $r$ .

Key definitions include:

Divergence: A smooth function $D(S \| R)$ satisfying non-negativity, identity of indiscernibles ( $D(S\|R)=0 \iff S=R$ ), and a specific quadratic expansion near the diagonal involving a positive-definite matrix $G(R)$ .
Invariant Divergence: A divergence where the matrix associated with its second-order expansion at any distribution $R$ takes the form $\eta \Sigma_R$ , where $\Sigma_R$ is a specific matrix structure related to the geometry of the probability simplex. This class includes the Kullback-Leibler (KL) divergence, JS divergence, $f$ -divergences, and Rényi divergences.

The authors establish a theoretical link between two-sample testing and robust goodness-of-fit (GoF) testing. They demonstrate that the Gutman test is equivalent to the Generalized Likelihood Ratio Test (GLRT) for a specific robust GoF problem where the uncertainty class consists of pairs of identical distributions.

Key Contributions and Results

First-Order Optimality:
The paper proves that the divergence test achieves the optimal first-order error exponent, $2D_B(P_1, P_2)$ (twice the Bhattacharyya distance), regardless of the specific divergence measure $D$ chosen. This confirms that the choice of divergence does not affect the exponential decay rate of the type-II error in the limit.
Second-Order Asymptotics for Invariant Divergences:
The primary contribution is the characterization of the second-order asymptotics for divergence tests using invariant divergences. The authors show that for any invariant divergence, the second-order term $\beta''$ is identical to that of the Gutman test (which uses the JS divergence).
The asymptotic expansion is given by:
$-\frac{1}{n} \ln \beta_n \approx 2D_B(P_1, P_2) - \frac{\sqrt{V_{KL}(P^* \| P_1) + V_{KL}(P^* \| P_2)}}{\sqrt{n}} Q^{-1}_{\chi^2_{k-1}}(\epsilon)$
where $P^*$ is the distribution minimizing the sum of KL divergences to $P_1$ and $P_2$ , $V_{KL}$ denotes the KL divergence variance, and $Q^{-1}_{\chi^2_{k-1}}$ is the inverse tail probability of a chi-square distribution with $k-1$ degrees of freedom.
Non-Invariant Divergences:
For non-invariant divergences, the paper establishes that the first-order optimality still holds. However, the characterization of the second-order term remains an open problem. The difficulty arises because the tail probability of the test statistic depends on the eigenvalues of a matrix that varies with the unknown distribution $P$ , making the threshold selection and error bounding significantly more complex. The authors note that while non-invariant divergences might theoretically offer better second-order performance in robust GoF testing (as shown in prior work), it is not yet determined if this holds for the two-sample problem.

Significance and Claims
The paper claims to demonstrate that the class of invariant divergences is robust in terms of asymptotic performance; replacing the JS divergence with any other invariant divergence (such as KL or Rényi) in the Gutman test does not alter the first- or second-order asymptotic behavior of the type-II error. This unifies the understanding of various divergence-based tests under a common asymptotic framework.

Furthermore, the work clarifies the connection between two-sample testing and robust goodness-of-fit testing, showing that the Gutman test is a specific instance of a GLRT in the robust GoF setting. The authors remain modest regarding non-invariant divergences, acknowledging that while first-order optimality is guaranteed, the second-order behavior is not fully characterized and may depend on the specific properties of the divergence and the underlying distributions. The analysis is currently restricted to finite alphabets, and the authors note that extending these second-order results to arbitrary Polish spaces (as done for first-order MMD results) presents significant challenges due to the dependence of the second-order term on the alphabet size.