Ball divergence

Short description: Nonparametric two-sample test methods

Ball Divergence (BD) is a nonparametric two‐sample statistic that quantifies the discrepancy between two probability measures $\mu$ and $\nu$ on a metric space $(V,\rho )$. It is defined by integrating the squared difference of the measures over all closed balls in $V$. Let $\bar{B}(u,r)=\{w\in V\mid \rho (u,w)\le r\}$ be the closed ball of radius $r\ge 0$ centered at $u\in V$. Equivalently, one may set $r=\rho (u,v)$ and write $\bar{B}(u,\rho (u,v))$. The Ball divergence is then defined by $$BD(\mu ,\nu )=\underset{V\times V}{\iint }[\mu (\bar{B}(u,\rho (u,v)))-\nu (\bar{B}(u,\rho (u,v))){]}^2[\mu (du)\mu (dv)+\nu (du)\nu (dv)].$$ This measure can be seen as an integral of the Harald Cramér's distance over all possible pairs of points. By summing squared differences of $\mu$ and $\nu$ over balls of all scales, BD captures both global and local discrepancies between distributions, yielding a robust, scale-sensitive comparison. Moreover, since BD is defined as the integral of a squared measure difference, it is always non-negative, and $BD(\mu ,\nu )=0$ if and only if $\mu =\nu$.

Testing for equal distributions

Next, we will try to give a sample version of Ball Divergence. For convenience, we can decompose the Ball Divergence into two parts: $$A=\underset{V\times V}{\iint }[\mu -\nu {]}^2(\overline{B}(u,\rho (u,v)))\mu (du)\mu (dv),$$ and $$C=\underset{V\times V}{\iint }[\mu -\nu {]}^2(\overline{B}(u,\rho (u,v)))\nu (du)\nu (dv).$$ Thus $BD(\mu ,\nu )=A+C.$

Let $\delta (x,y,z)=I(z\in \overline{B}(x,\rho (x,y)))$ denote whether point $z$ locates in the ball $\overline{B}(x,\rho (x,y))$. Given two independent samples $\{X_1,\dots ,X_n\}$ form $\mu$ and $\{Y_1,\dots ,Y_m\}$ form $\nu$

$$\begin{array}{rlrl}{A}_{ij}^X& =\frac{1}{n}\sum _{u=1}^n\delta (X_i,X_j,X_u),& A_{ij}^Y& =\frac{1}{m}\sum _{v=1}^m\delta (X_i,X_j,Y_v),\\ C_{kl}^X& =\frac{1}{n}\sum _{u=1}^n\delta (Y_k,Y_l,X_u),& C_{ij}^Y& =\frac{1}{m}\sum _{v=1}^m\delta (Y_k,Y_l,Y_v),\end{array}$$ where $A_{ij}^X$ means the proportion of samples from the probability measure $\mu$ located in the ball $\overline{B}(X_i,\rho (X_i,X_j))$ and $A_{ij}^Y$ means the proportion of samples from the probability measure $\nu$ located in the ball $\overline{B}(X_i,\rho (X_i,X_j))$. Meanwhile, $C_{ij}^X$ and $C_{ij}^Y$ means the proportion of samples from the probability measure $\mu$ and $\nu$ located in the ball $\overline{B}(Y_i,\rho (Y_i,Y_j))$. The sample versions of $A$ and $C$ are as follows

$$A_{n,m}=\frac{1}{n^2}\sum _{i,j=1}^n{(A_{ij}^X-A_{ij}^Y)}^2,C_{n,m}=\frac{1}{m^2}\sum _{k,l=1}^m{(C_{kl}^X-C_{kl}^Y)}^2.$$

Finally, we can give the sample ball divergence

$$B{D}_{n,m}=A_{n,m}+C_{n,m}.$$

It can be proved that $B{D}_{n,m}$ is a consistent estimator of BD. Moreover, if $\frac{n}{n+m}\to \tau$ for some $\tau \in [0,1]$, then under the null hypothesis $B{D}_{n,m}$ converges in distribution to a mixture of chi-squared distributions, whereas under the alternative hypothesis it converges to a normal distribution.

Properties

1. The square root of Ball Divergence is a symmetric divergence but not a metric, because it does not satisfy the triangle inequality.
2. It can be shown that Ball divergence, energy distance test, and MMD are unified within the variogram framework; for details see Remark 2.4 in.

Homogeneity Test

Ball divergence admits a straightforward extension to the K-sample setting. Suppose ${\mu }_1,\dots ,{\mu }_K$ are $K(\ge 2)$ probability measures on a Banach space $(V,\Vert \cdot \Vert )$. Define the K-sample BD by

$$D({\mu }_1,\dots ,{\mu }_K)=\sum _{1\le k<l\le K}\underset{V\times V}{\iint }\left[{\mu }_k\right(\bar{B}(u,\rho (u,v)))-{\mu }_l(\bar{B}(u,\rho (u,v))\left){]}^2\right[{\mu }_k(du){\mu }_k(dv)+{\mu }_l(du){\mu }_l(dv)].$$

It then follows from Theorems 1 and 2 that $D({\mu }_1,\dots ,{\mu }_K)=0$ if and only if ${\mu }_1={\mu }_2=\cdots ={\mu }_K.$

By employing closed balls to define a metric distribution function, one obtains an alternative homogeneity measure.

Given a probability measure $\tilde{\mu }$ on a metric space $(V,\rho )$, its metric distribution function is defined by

$$F_{\tilde{\mu }}^M(u,v)=\tilde{\mu }(\bar{B}(u,\rho (u,v)))=\mathbb{𝔼}[\delta (u,v,X)],u,v\in V,$$

where $\bar{B}(u,r)=\{w\in V:d(u,w)\le r\}$ is the closed ball of radius $r\ge 0$ centered at $u$, and $\delta (u,v,X)=\prod _{k=1}^K\mathbf{𝟏}\{X^{(k)}\in {\bar{B}}_k(u_k,{\rho }_k(u_k,v_k))\}.$

If $(X_1,\dots ,X_N)$ are i.i.d. draws from $(\tilde{\mu })$, the empirical version is

$$F_{\tilde{\mu },N}^M(u,v)=\frac{1}{N}\sum _{i=1}^N\delta (u,v,X_i).$$

Based on these, the homogeneity measure based on MDF, also called metric Cramér-von Mises (MCVM) is $$\mathrm{M}\mathrm{C}\mathrm{V}\mathrm{M}({\mu }_k\parallel \mu )=\underset{V\times V}{\int }{p}_k^{2}w(u,v)[F_{{\mu }_k}^M(u,v)-F_{\mu }^M(u,v){]}^{2}d{\mu }_k(u)d{\mu }_k(v),$$

where $\mu ={\sum }_{k=1}^K{p}_k{\mu }_k$ be their mixture with weights $p_1,\dots ,p_K$, and $w(u,v)=\exp (-\frac{d(u,v{)}^2}{2{\sigma }^2})$. The overall MCVM is then

$$\mathrm{M}\mathrm{C}\mathrm{V}\mathrm{M}({\mu }_1,\dots ,{\mu }_K)=\sum _{k=1}^K{p}_k^2\mathrm{M}\mathrm{C}\mathrm{V}\mathrm{M}({\mu }_k\parallel \mu ).$$

The empirical MCVM is given by

$$\widehat{\mathrm{M}\mathrm{C}\mathrm{V}\mathrm{M}}({\mu }_k\parallel \mu )=\frac{1}{n_k^2}\sum _{X_i^{(k)},X_j^{(k)}\in {{𝒳}}_k}w(X_i^{(k)},X_j^{(k)}){\left[F_{{\mu }_k,n_k}^M\right(X_i^{(k)},X_j^{(k)})-F_{\mu ,n}^M(X_i^{(k)},X_j^{(k)}\left)\right]}^2.$$

where ${{𝒳}}_k=\{X_1^{(k)},\dots ,X_{n_k}^{(k)}\}$ be an i.i.d. sample from ${\mu }_k$, and ${\hat{p}}_k=\frac{n_k}{\sum _{\ell =1}^K{n}_{\ell }}.$ A practical choice for ${\sigma }^2$ is the median of the squared distances $$\{d(X,X^{\prime }{)}^2:X,X^{\prime }\in \bigcup _{k=1}^K{{𝒳}}_k\}.$$