Let X sim f_X and Z sim f_Z be independent random variables, where f_X and f_Z are densities with cumulative distribution functions F_X and F_Z, respectively. Integral inequality conjecture. The inequality int_r=-∞^∞int_alpha=0^∞(F_X(r)-F_Z(r))(f_X(r-alpha)f_Z(r+alpha)-f_X(r+alpha)f_Z(r-alpha)),d alpha,dr≥ 0 holds. This inequality is presented as a sufficient-and-necessary reformulation of the expected-error comparison underlying the proposed nearest-neighbor rule, and its validity is left unresolved.

Integral inequality for nearest-neighbor classification

About 2 years old · traced to 2024

Let $X\sim f_X$ and $Z\sim f_Z$ be independent random variables, where $f_X$ and $f_Z$ are densities with cumulative distribution functions $F_X$ and $F_Z$ , respectively. Integral inequality conjecture. The inequality

\int_{r=-\infty}^{\infty}\int_{\alpha=0}^{\infty}\left(F_X(r)-F_Z(r)\right)\left(f_X(r-\alpha)f_Z(r+\alpha)-f_X(r+\alpha)f_Z(r-\alpha)\right)\,d\alpha\,dr\geq 0

holds. This inequality is presented as a sufficient-and-necessary reformulation of the expected-error comparison underlying the proposed nearest-neighbor rule, and its validity is left unresolved.

References

Primary source

Kevin Bleakley, “Extreme change-point detection”, arXiv:2403.19237 (2024).

classification probability-distributions probability-inequalities

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A posted calculation claims an explicit smooth counterexample, so the inequality is false in general, but the calculation has not been independently verified.

The conjecture asks whether the displayed integral is nonnegative for all pairs of probability densities. Bleakley’s 2024 paper introduced the underlying nearest-neighbor conjecture: nearest-neighbor prediction should outperform chance for arbitrary distributions and be optimal without distributional knowledge.

Known results

For Gaussian densities, nearest-neighbor prediction beats chance without knowing the parameters (Bleakley, 2024).

August 2026 posted counterexample

An attempted calculation takes mixtures of compactly supported uniform components centered at $0$ , $2$ , $3$ , and $5$ , and claims the integral equals $-1/512<0$ . It further claims the same value for smooth compactly supported bump densities. This is presented as a complete counterexample, but it has not been independently verified.

Current status (as of August 2026): The Gaussian case is established, while a claimed smooth counterexample would refute the general inequality; that counterexample remains unverified.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

The integral can be strictly negative for explicit absolutely continuous probability densities.

For $c\in\mathbb R$ , define

u_c(t)=5\mathbf1_{\{|t-c|<1/10\}},

and take

f_X=\frac14u_2+\frac34u_5, \qquad f_Z=\frac18u_0+\frac18u_3+\frac34u_5.

Both are probability densities. Write $D=F_X-F_Z$ , and denote the conjectured integral by $I$ . The substitution

x=r-\alpha,\qquad z=r+\alpha, \qquad dr\,d\alpha=\frac12\,dx\,dz

gives

I=\frac12\int_{x<z} D\left(\frac{x+z}{2}\right) \left(f_X(x)f_Z(z)-f_X(z)f_Z(x)\right)\,dx\,dz.

At the ordered centers $(0,2,3,5)$ , the respective component-mass vectors are

p=(0,1/4,0,3/4), \qquad q=(1/8,0,1/8,3/4).

For distinct centers $c_i<c_j$ , all corresponding midpoints lie in the same gap between the four supports. Thus $D$ is constant on that entire block, and

I=\frac12\sum_{i<j} D\left(\frac{c_i+c_j}{2}\right) (p_iq_j-p_jq_i).

The complete exact calculation is

\begin{array}{c|c|c|c} (c_i,c_j)&D((c_i+c_j)/2)&p_iq_j-p_jq_i& \text{contribution to }I\\ \hline (0,2)&-1/8&-1/32&1/512\\ (0,3)&-1/8&0&0\\ (0,5)&1/8&-3/32&-3/512\\ (2,3)&1/8&1/32&1/512\\ (2,5)&0&3/16&0\\ (3,5)&0&-3/32&0 \end{array}

and hence

\boxed{I=-\frac1{512}<0}.

The same construction works with smooth densities: replace every $u_c$ by the translate of any normalized $C^\infty$ bump supported in $(-1/10,1/10)$ . Every midpoint remains in the same gap, so the exact value $-1/512$ is unchanged.