# Algorithm for numerically approximating the Prokhorov metric?

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.

• 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$.