Integral inequality for nearest-neighbor classification

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.