Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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
show 4 more comments

1 Answer 1

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

share|improve this answer
    
Can you explain please what do you mean by "a completed graph of F and G" ? Thx –  user140328 Apr 4 at 8:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.