MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Question: What is known about algorithms for numerically computing/approximating the Prokhorov distance between two measures?

Recall that the Prokhorov distance metrizes the topology of weak(-*) convergence of measures on separable metric spaces, and is defined as follows.

Let $\mu_1$, $\mu_2$ be finite measures on a metric space $(X,d)$. The Prokhorov distance $\rho$ between them is, $$\rho(\mu_1,\mu_2):=\inf \left\{ \epsilon > 0 : \mu_1(A) \le \mu_2(A^\epsilon)+\epsilon~ \text{ for all } A \in \mathcal{B} \right\},$$ where $\mathcal{B}$ is the Borel $\sigma$-algebra on $X$ and $A^\epsilon$ is the $\epsilon$-neighborhood of $A$.

Has a constructive/algorithmic approach to the Prokhorov metric been studied in any contexts? How could one go about constructing numerical algorithms to compute it?

Note: Per asked this nearly identical question at math.stackexchange, where it got no answers even after having a bounty for a week. I'm reposting here with his/her permission.

share|cite|improve this question
It would probably be nice to have a specific space or family of spaces that are easily described if you want an algorithm... – Anthony Quas Nov 9 '12 at 3:30
My personal interest is the space of probability measures $\mathcal{P}(X)$ over the function space $X=L^2(\Omega)$ for lipschitz domains $Omega \subset \mathbb{R}^3$. There are several levels of "infiniteness" layered on each other here, so it seems pretty difficult. I would also be interested in methods on finite dimensional vector spaces $X$, or even discrete $X$. I believe this is what the original asker was going for in the math.stackexchange thread. – Nick Alger Nov 9 '12 at 4:24

Answered Per's post in the special case of distributions on $R$.

share|cite|improve this answer

Your Answer


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.