Edward Yu personal website

A proposed proof of Open Question 3 in instance-optimal identity testing

22 Jul 2026

Editor’s note: this proof was entirely generated by ChatGPT 5.6, I didn’t contribute anything! I’m publishing this in case it will be a useful reference for others.

In identity testing, we know a reference distribution $q$, receive independent samples from an unknown distribution $p$, and want to distinguish

\[p=q \qquad\text{from}\qquad d_{\mathrm{TV}}(p,q)>\varepsilon.\]

The usual worst-case sample complexity depends on the size of the domain. Instance-optimal identity testing asks a more refined question: how many samples are necessary for this particular $q$?

Gregory Valiant and Paul Valiant gave upper and lower bounds in terms of an $\ell_{2/3}$-quasinorm of a truncated version of $q$. Their lower-bound argument, however, does not cover distributions that are very close to a point mass. Clément Canonne’s 2024 COLT note isolates this issue as Open Question 3:

Fix the (small) gap in the lower bound proof of Valiant and Valiant (2014), described in Section 4.

The problem occurs when the largest atom $q_{\max}$ is greater than $1-2\varepsilon$. The parameter required by the original hard-prior construction then need not exist. This is not automatically handled by the elementary $\Omega(1/\varepsilon)$ lower bound: when $q_{\max}\in[1-2\varepsilon,1-\varepsilon]$, the truncated $\ell_{2/3}$ term can still be much larger.

Below is a proposed repair. The central idea is to group the non-maximal atoms into blocks and collapse each block onto a randomly selected atom. Every alternative preserves the block masses, and therefore total probability, exactly. This avoids the random normalization step responsible for the corner case.

Statement

Let $q$ be a distribution on $\mathbb N$, let $0<\varepsilon<1$, and suppose

\[q_{\max}\geq 1-2\varepsilon.\]

Then identity testing to $q$, against alternatives satisfying $d_{\mathrm{TV}}(p,q)>\varepsilon$, requires

\[\Omega\!\left( \max\left\{ \frac{1}{\varepsilon}, \frac{\Phi_{\mathrm{VV}}(q,\varepsilon)}{\varepsilon^2} \right\} \right)\]

samples. This is the corner case missing from the Valiant–Valiant lower-bound proof.

Proof

Remove one maximum-probability atom of $q$, and sort the remaining masses:

\[w_1\geq w_2\geq\cdots, \qquad r:=\sum_i w_i=1-q_{\max}\leq 2\varepsilon.\]

Define the Valiant–Valiant cutoff

\[J:=\min\left\{ j:\sum_{i>j}w_i\leq\varepsilon \right\}, \qquad A:=\left(\sum_{i=1}^{J}w_i^{2/3}\right)^{3/2}.\]

Thus $A=\Phi_{\mathrm{VV}}(q,\varepsilon)$.

There is always a standard $\Omega(1/\varepsilon)$ two-point lower bound. If $r\leq\varepsilon$, then $A\leq\varepsilon$, so that lower bound already proves the result. We may therefore assume

\[\varepsilon<r\leq 2\varepsilon.\]

1. Find a useful suffix scale

For $1\leq k\leq J$, set

\[T_k:=\sum_{i\geq k}w_i=\varepsilon+d_k, \qquad V_k:=\sum_{i\geq k}w_i^2,\]

and

\[P_k:=\max\left\{ w_k,\frac{V_k}{d_k} \right\}, \qquad P:=\min_{k\leq J}P_k.\]

Minimality of $J$ implies $d_k>0$. We claim that, for a universal constant $C$,

\[A\leq C\left( \varepsilon+\frac{\varepsilon^{3/2}}{\sqrt P} \right). \tag{1}\]

Indeed,

\[V_k\leq w_kT_k\leq 2\varepsilon w_k.\]

Since $P\leq P_k$, either $w_k\geq P$, or $V_k/d_k\geq P$. In either case,

\[w_k\geq\frac{Pd_k}{2\varepsilon}. \tag{2}\]

For $k<J$, we have $w_k=d_k-d_{k+1}$, and therefore

\[\begin{aligned} w_k^{2/3} &\leq \left(\frac{2\varepsilon}{P}\right)^{1/3} (d_k-d_{k+1})d_k^{-1/3}\\ &\leq \left(\frac{2\varepsilon}{P}\right)^{1/3} \int_{d_{k+1}}^{d_k}x^{-1/3}\,dx. \end{aligned}\]

Summing and using $d_1=r-\varepsilon\leq\varepsilon$ gives

\[\sum_{k<J}w_k^{2/3} \leq C\varepsilon P^{-1/3}.\]

Also, $w_J^{2/3}\leq(2\varepsilon)^{2/3}$. Raising the resulting bound to the $3/2$ power proves (1).

If $A\leq C’\varepsilon$, the $\Omega(1/\varepsilon)$ lower bound suffices. Otherwise, (1) gives

\[P\leq C''\frac{\varepsilon^3}{A^2}. \tag{3}\]

By choosing the easy-case constant $C’$ sufficiently large, we may also assume

\[KP\leq\frac{\varepsilon}{2}, \qquad K:=12.\]

2. Construct normalized hard alternatives

Choose $k$ attaining $P=P_k$, and write

\[S:=\{i:i\geq k\}, \qquad T:=T_k=\varepsilon+d, \qquad V:=V_k, \qquad \pi:=KP.\]

Because $P=P_k$,

\[\max_{i\in S}w_i=w_k\leq P=\frac{\pi}{K}, \qquad \frac{V}{\pi}\leq\frac{d}{K}. \tag{4}\]

Greedily partition $S$ into blocks $G_b$ of $q$-mass

\[\pi\leq g_b:=q(G_b)\leq(2+1/K)\pi. \tag{5}\]

This is possible because $T\geq\varepsilon\geq2\pi$, while every atom has mass at most $\pi/K$. Any final remainder of mass below $\pi$ is merged into the preceding block.

Independently in each block, choose $I_b\in G_b$ according to

\[\Pr(I_b=i)=\frac{w_i}{g_b}.\]

Define $p^I$ by collapsing each block onto its selected atom:

\[p^I_{I_b}=g_b, \qquad p^I_i=0 \quad \text{for }i\in G_b\setminus\{I_b\},\]

and leave $q$ unchanged outside $S$. Every $p^I$ is exactly normalized.

Let

\[U:=\sum_b w_{I_b}.\]

On block $G_b$, the total variation distance is $g_b-w_{I_b}$, so

\[d_{\mathrm{TV}}(p^I,q)=T-U.\]

Moreover, by (4) and (5),

\[\mathbb E U =\sum_b\frac{\sum_{i\in G_b}w_i^2}{g_b} \leq\frac{V}{\pi} \leq\frac{d}{K}.\]

Markov’s inequality therefore gives

\[\begin{aligned} \Pr\!\left(d_{\mathrm{TV}}(p^I,q)>\varepsilon\right) &=\Pr(U<d)\\ &\geq1-\frac{1}{K}. \end{aligned} \tag{6}\]

3. Show that the sample mixture is close to the null

Let

\[M_n:=\mathbb E_I\!\left[(p^I)^{\otimes n}\right].\]

First reveal only the block label of each observation, retaining individual labels outside $S$. This coarse sequence has exactly the same law under $q$ and every $p^I$, since every block preserves its total mass $g_b$.

If no block is observed twice, the fine symbol within every observed block also has the same law under the two experiments: under $q$, it is $w_i/g_b$; under the mixture, it is the selected $I_b$, which has precisely that distribution. Consequently,

\[\begin{aligned} d_{\mathrm{TV}}(M_n,q^{\otimes n}) &\leq \Pr(\text{some block is sampled twice})\\ &\leq {n\choose 2}\sum_b g_b^2\\ &\leq \frac{n^2}{2}(2+1/K)\pi T. \end{aligned} \tag{7}\]

Suppose a tester with error at most $1/3$ existed. Under $q$, its rejection probability would be at most $1/3$. By (6), under $M_n$, its rejection probability would be at least

\[\frac{2}{3}\left(1-\frac{1}{K}\right).\]

For $K=12$, the resulting gap is

\[\frac{2}{3}\left(1-\frac{1}{12}\right)-\frac{1}{3} =\frac{5}{18}.\]

Thus $d_{\mathrm{TV}}(M_n,q^{\otimes n})\geq5/18$. Comparing this with (7) yields

\[n=\Omega\!\left(\frac{1}{\sqrt{\pi T}}\right).\]

Finally, using $T\leq2\varepsilon$ and (3),

\[\pi T=KP\,T \leq C\frac{\varepsilon^4}{A^2},\]

and hence

\[n =\Omega\!\left(\frac{A}{\varepsilon^2}\right) =\Omega\!\left( \frac{\Phi_{\mathrm{VV}}(q,\varepsilon)}{\varepsilon^2} \right).\]

Together with the universal $\Omega(1/\varepsilon)$ bound, this proves the proposition. $\square$

Remarks

The useful feature of the block-collapse construction is exact normalization: every alternative is a probability distribution before sampling. No random-sign normalization argument is needed.

The argument also extends to countable supports. There can be only finitely many positive-mass blocks because every block has mass at least $\pi$, although the final block may contain countably many atoms.

There is also a convention issue worth making explicit. Valiant–Valiant use ordinary $\ell_1$ distance in parts of their presentation, while Canonne defines

\[d_{\mathrm{TV}}(p,q)=\frac{1}{2}\lVert p-q\rVert_1.\]

The alternatives constructed above satisfy the literal, stronger condition $d_{\mathrm{TV}}(p^I,q)>\varepsilon$, so the repair does not conceal a factor-of-two substitution.

This appears to be a new proof rather than a published resolution. It should receive independent expert review before being treated as a formal solution.

Sources

Related posts