8
$\begingroup$

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.

  • 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.2012-11-01
  • 0
    Since no one answered in the allotted time, you could try asking at [mathoverflow](http://mathoverflow.net/)? If you don't want to ask there for some reason, would you give me permission to post your question there?2012-11-08
  • 0
    Hi Nick. Feel free to ask it there if you think that could get an answer!2012-11-09
  • 0
    Ok, I asked it here: http://mathoverflow.net/questions/111865/algorithm-for-numerically-approximating-the-prokhorov-metric2012-11-09
  • 0
    Also, I just found [this paper](http://www.springerlink.com/content/4322554233v53q12/) which looks promising.2012-11-09
  • 0
    Just out of curiosity, is there any particular reason for desiring the value of the Prokhorov metric as opposed to, say, the Wasserstein distance? They both metrize the weak topology on probability measures. I can think of a few methods for computing the latter, which has connections to optimal transport theory and Monge-Ampere equations.2012-11-15
  • 0
    @icurays1. My motivation is purely to get a deeper understanding of the Prokhorov metric itself. I was hoping that a constructive approach through algorithms was one such path.2012-11-15

1 Answers 1