On the space of probability measures on a metric Polish space, the Prokhorov metric is among the most popular distances between probability distributions. As it is the sole metric equivalent to the weak topology without further assumptions, it is usually mainly considered from a theoretical point of view. In this presentation, we want to highlight that although the definition of the Prokhorov metric seems rather stodgy, its computation is noticeably not more involved than the computation of the much more popular Wasserstein metric. For this purpose, we investigate the computation of the Prokhorov metric for finitely supported distributions. We especially compare our approach to the only other related work by Garel and Masse (2009). Specifically, we demonstrate that their fixed point approach fails for specific problems, while their max flow approach can be significantly improved. By distinguishing different settings, we are able to provide algorithms with proven correctness, together with worst case complexities. We conclude with a quasilinear algorithm for the most important case of real numbers with the usual metric. If time allows we will also briefly cover known and unknown inequalities concerning the Prokhorov metric, as well as its asymptotic behavior. Finally, we also shed some light on the connection of the Prokhorov metric to the Wasserstein infinity metric.
Personal website of Ralf Werner