Ball divergence

Ball Divergence (BD) is a nonparametric two‐sample statistic that quantifies the discrepancy between two probability measures ${\displaystyle \mu }$ and ${\displaystyle \nu }$ on a metric space ${\displaystyle (V,\rho )}$.¹ It is defined by integrating the squared difference of the measures over all closed balls in ${\displaystyle V}$. Let ${\displaystyle {\overline {B}}(u,r)=\{w\in V\mid \rho (u,w)\leq r\}}$ be the closed ball of radius ${\displaystyle r\geq 0}$ centered at ${\displaystyle u\in V}$. Equivalently, one may set ${\displaystyle r=\rho (u,v)}$ and write ${\displaystyle {\overline {B}}{\bigl (}u,\rho (u,v){\bigr )}}$. The Ball divergence is then defined by $${\displaystyle BD(\mu ,\nu )=\iint _{V\times V}{\bigl [}\mu ({\overline {B}}(u,\rho (u,v)))-\nu ({\overline {B}}(u,\rho (u,v))){\bigr ]}^{2}\;{\bigl [}\mu (du)\,\mu (dv)+\nu (du)\,\nu (dv){\bigr ]}.}$$ 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 ${\displaystyle \mu }$ and ${\displaystyle \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 ${\displaystyle BD(\mu ,\nu )=0}$ if and only if ${\displaystyle \mu =\nu }$.

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

Let ${\displaystyle \delta (x,y,z)=I(z\in {\bar {B}}(x,\rho (x,y)))}$ denote whether point ${\displaystyle z}$ locates in the ball ${\displaystyle {\bar {B}}(x,\rho (x,y))}$. Given two independent samples ${\displaystyle \{X_{1},\ldots ,X_{n}\}}$ form ${\displaystyle \mu }$ and ${\displaystyle \{Y_{1},\ldots ,Y_{m}\}}$ form ${\displaystyle \nu }$

$${\displaystyle {\begin{aligned}A_{ij}^{X}&={\frac {1}{n}}\sum _{u=1}^{n}\delta {\left(X_{i},X_{j},X_{u}\right)},&A_{ij}^{Y}&={\frac {1}{m}}\sum _{v=1}^{m}\delta {\left(X_{i},X_{j},Y_{v}\right)},\\C_{kl}^{X}&={\frac {1}{n}}\sum _{u=1}^{n}\delta {\left(Y_{k},Y_{l},X_{u}\right)},&C_{ij}^{Y}&={\frac {1}{m}}\sum _{v=1}^{m}\delta {\left(Y_{k},Y_{l},Y_{v}\right)},\end{aligned}}}$$ where ${\displaystyle A_{ij}^{X}}$ means the proportion of samples from the probability measure ${\displaystyle \mu }$ located in the ball ${\displaystyle {\bar {B}}\left(X_{i},\rho \left(X_{i},X_{j}\right)\right)}$ and ${\displaystyle A_{ij}^{Y}}$ means the proportion of samples from the probability measure ${\displaystyle \nu }$ located in the ball ${\displaystyle {\bar {B}}\left(X_{i},\rho \left(X_{i},X_{j}\right)\right)}$. Meanwhile, ${\displaystyle C_{ij}^{X}}$ and ${\displaystyle C_{ij}^{Y}}$ means the proportion of samples from the probability measure ${\displaystyle \mu }$ and ${\displaystyle \nu }$ located in the ball ${\displaystyle {\bar {B}}\left(Y_{i},\rho \left(Y_{i},Y_{j}\right)\right)}$. The sample versions of ${\displaystyle A}$ and ${\displaystyle C}$ are as follows

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

Finally, we can give the sample ball divergence

$${\displaystyle BD_{n,m}=A_{n,m}+C_{n,m}.}$$

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

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.¹

Ball divergence admits a straightforward extension to the K-sample setting. Suppose ${\displaystyle \mu _{1},\dots ,\mu _{K}}$ are ${\displaystyle K(\geq 2)}$ probability measures on a Banach space ${\displaystyle (V,\|\cdot \|)}$. Define the K-sample BD by

$${\displaystyle D(\mu _{1},\dots ,\mu _{K})=\sum _{1\leq k<l\leq K}\iint _{V\times V}{\bigl [}\mu _{k}{\bigl (}{\overline {B}}(u,\rho (u,v)){\bigr )}-\mu _{l}{\bigl (}{\overline {B}}(u,\rho (u,v)){\bigr )}{\bigr ]}^{2}\;{\bigl [}\mu _{k}(du)\,\mu _{k}(dv)+\mu _{l}(du)\,\mu _{l}(dv){\bigr ]}.}$$

It then follows from Theorems 1 and 2 that ${\displaystyle D(\mu _{1},\dots ,\mu _{K})=0}$ if and only if ${\displaystyle \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 ${\displaystyle {\tilde {\mu }}}$ on a metric space ${\displaystyle (V,\rho )}$, its metric distribution function is defined by

$${\displaystyle F_{\tilde {\mu }}^{M}(u,v)={\tilde {\mu }}{\bigl (}{\overline {B}}(u,\rho (u,v)){\bigr )}=\mathbb {E} {\bigl [}\delta (u,v,X){\bigr ]},\quad u,v\in V,}$$

where ${\displaystyle {\overline {B}}(u,r)=\{w\in V:d(u,w)\leq r\}}$ is the closed ball of radius ${\displaystyle r\geq 0}$ centered at ${\displaystyle u}$, and ${\displaystyle \delta (u,v,X)=\prod _{k=1}^{K}\mathbf {1} \{X^{(k)}\in {\overline {B}}_{k}(u_{k},\rho _{k}(u_{k},v_{k}))\}.}$

If ${\displaystyle (X_{1},\dots ,X_{N})}$ are i.i.d. draws from ${\displaystyle ({\tilde {\mu }})}$, the empirical version is

$${\displaystyle 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 $${\displaystyle \mathrm {MCVM} {\bigl (}\mu _{k}\parallel \mu {\bigr )}=\int _{V\times V}p_{k}^{2}\,w(u,v)\,{\bigl [}F_{\mu _{k}}^{M}(u,v)-F_{\mu }^{M}(u,v){\bigr ]}^{2}\,d\mu _{k}(u)\,d\mu _{k}(v),}$$

where ${\textstyle \mu =\sum _{k=1}^{K}p_{k}\,\mu _{k}}$ be their mixture with weights ${\displaystyle p_{1},\dots ,p_{K}}$, and ${\textstyle w(u,v)=\exp \left(-{\tfrac {d(u,v)^{2}}{2\sigma ^{2}}}\right)}$. The overall MCVM is then

$${\displaystyle \mathrm {MCVM} (\mu _{1},\dots ,\mu _{K})=\sum _{k=1}^{K}p_{k}^{2}\,\mathrm {MCVM} {\bigl (}\mu _{k}\parallel \mu {\bigr )}.}$$

The empirical MCVM is given by

$${\displaystyle {\widehat {\mathrm {MCVM} }}{\bigl (}\mu _{k}\parallel \mu {\bigr )}={\frac {1}{n_{k}^{2}}}\sum _{X_{i}^{(k)},X_{j}^{(k)}\in {\mathcal {X}}_{k}}w{\bigl (}X_{i}^{(k)},X_{j}^{(k)}{\bigr )}\,\left[F_{\mu _{k},n_{k}}^{M}{\bigl (}X_{i}^{(k)},X_{j}^{(k)}{\bigr )}-F_{\mu ,n}^{M}{\bigl (}X_{i}^{(k)},X_{j}^{(k)}{\bigr )}\right]^{2}.}$$

where ${\displaystyle {\mathcal {X}}_{k}=\{X_{1}^{(k)},\dots ,X_{n_{k}}^{(k)}\}}$ be an i.i.d. sample from ${\displaystyle \mu _{k}}$, and ${\displaystyle {\hat {p}}_{k}={\frac {n_{k}}{\sum _{\ell =1}^{K}n_{\ell }}}.}$ A practical choice for ${\displaystyle \sigma ^{2}}$ is the median of the squared distances $${\displaystyle \left\{d(X,X')^{2}:X,X'\in \bigcup _{k=1}^{K}{\mathcal {X}}_{k}\right\}.}$$