# Algorithms for computing or numerically approximating the Prokhorov metric?

I am interested in the following practical question: Given two measures (say those of two parametric distributions), is there an algorithm for computing the Prokhorov metric between them?

The general definition of the Prokhorov metric is as follows. For two finite measures $\mu_1$, $\mu_2$ on a separable metric space $\left( X, d \right)$, that metric is defined as $\rho \left( \mu_1, \mu_2 \right) = \inf \left\{ \varepsilon > 0 : \mu_1 \left( G \right) \leqslant \mu_2 \left( G^{\varepsilon} \right) + \varepsilon, \forall G \in \mathcal{B} \right\}$ where $\mathcal{B}$ is the Borel $\sigma$-algebra on $X$ and $G^{\varepsilon} = \left\{ x \in X : \inf_{y \in G} d \left( x, y \right) < \varepsilon \right\}$.

This metric is quite useful in the theory of weak convergence of probability measures on metric spaces (See Billingsley [Convergence of Probability Measures] or van der Vaart and Wellner [Weak Convergence and Empirical Processes]). The purpose of my question is that I am curious about whether a constructive algorithmic approach has been already studied. And if not, how could that be accomplished.

-
I'm also very interested in what is known about this problem and will award an additional 250 reputation for a good answer to that effect. – Nick Alger Nov 1 '12 at 12:47
Thanks Nick :)! – Per Nov 1 '12 at 12:51
Since no one answered in the allotted time, you could try asking at mathoverflow? If you don't want to ask there for some reason, would you give me permission to post your question there? – Nick Alger Nov 8 '12 at 18:05
Hi Nick. Feel free to ask it there if you think that could get an answer! – Per Nov 9 '12 at 1:16
Ok, I asked it here: mathoverflow.net/questions/111865/… – Nick Alger Nov 9 '12 at 3:20

A quick answer in the special case of the Levy metric, i.e., the Levy-Prokhorov metric $\rho(\cdot,\cdot)$ for distributions on $R$ is as follows:

Let $h_C(\cdot,\cdot)$ be the Hausdorff metric induced by the Chebyshev metric on the space of all closed subsets of $R^2$ (Details here: http://math.stackexchange.com/a/218747/45639 ).

For two distribution functions $F$ and $G$, denoting their respective completed graphs by $\bar{F}$ and $\bar{G}$, we have

$\rho(F,G) = h_C(\bar{F},\bar{G})$.

Once you realize this, there are many algorithms available to calculate $h_C(\bar{F},\bar{G})$. The brute force method for paths (like $\bar{F}$ and $\bar{G}$) in $R^2$ is quite quick.

Here's a reference that lists some basic algorithms:

Nutanong et al, An Incremental Hausdorff Distance Calculation Algorithm, Proceedings of the VLDB Endowment, Vol 4, Issue 8, May 2011:

http://www.vldb.org/pvldb/vol4/p506-nutanong.pdf

-
Can you explain please what do you mean by "a completed graph of F and G" ? Thx – user140328 Apr 4 '14 at 8:11