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.

| cite | improve this question | | | | |
  • $\begingroup$ It would probably be nice to have a specific space or family of spaces that are easily described if you want an algorithm... $\endgroup$ – Anthony Quas Nov 9 '12 at 3:30
  • $\begingroup$ 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. $\endgroup$ – Nick Alger Nov 9 '12 at 4:24

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

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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