A list of different measures of distance/difference/dissimilarities/similarity of two probability distributions?

Question

I wanted to know more about the different methods for comparing the similarities of two probability distributions P and Q.

I wanted a list of the different methods that exist for comparing probability distributions.

For example, the two that I am aware that exist are:

1. KL-Divergence
2. EMD (earths mover's distance)

I was wondering if people knew about more different measures and if they could provide maybe a good reference for learning about it. Also, on top of providing the distance measure that you are suggesting, if you could provide a brief intuition on it before I research it more, it could be very helpful!

Answer 1

There is the total variation distance between finite measures $\mu$ and $\nu$: $$ \frac{1}{2} \sum_{i \in S} |\mu(i) - \nu(i)| \qquad \ (\text{discrete case}) $$

$$ \frac{1}{2} \int_\Omega |\mu(i) - \nu(i)|d\pi \qquad \ (\text{continuous case}) $$ (here $\mu,\nu << \pi$).

There is the $\chi^2$ distance which J.A. Fill used in a paper (can't recall the name) to measure the distance between the distribution $\pi_n$ at time $n$ with the steady state $\pi$ for a Markov Chain on a countable state space $S$: $$ \chi^2_n = \sum_{i \in S} \frac{(\pi_n(i) - \pi(i))^2}{\pi(i)}. $$ This is giving the relative distance at $i$ compared to the size of $\pi(i)$, so the effect is amplified where $\pi$ is small. Fill bounds the total variational distance with the $\chi^2$ distance.

This link lists several other metrics about which I'm afraid I don't know much (sorry!).

Answer 2

The "classical" reference: http://arxiv.org/abs/math/0209021 (this answer was already provided in: Prokhorov metric vs. total variation norm)

Answer 3

Another paper related to the question:

http://arxiv.org/pdf/1403.7164v4.pdf

---

First observation that we can provide is the relation between two common distances: total variation distance and KL-divergence. This is given by Pinkser inequality: $$ \frac{1}{2}\sum_{x\in\mathcal{X}} |P(x)-Q(x)|\leq \sqrt{\frac 12 D(P||Q)}. $$

---

However KL-divergence appears in some other contexts too. Suppose that $X$ and $Y$ are two random variables defined on the same set $\mathcal{X}$. Then consider the following probability: $$ \Pr(X = Y)=\sum_{x,y\in \mathcal{X}}P(x)Q(y)\mathbf{1}(x=y)=\sum_{x\in \mathcal{X}}P(X)Q(X) $$ We can further simplify the previous one: $$ \sum_{x\in \mathcal{X}}P(X)Q(X)=\mathbb{E}(Q(X))=\mathbb{E}(e^{\log Q(X)}) \geq e^{\mathbb{E}(\log Q(X))} $$ And finally: $$ \mathbb{E}(\log Q(X))=\mathbb{E}(\log \frac {Q(X)}{P(X)}+\log P(X))=-H(X)-D(P||Q). $$ So we have:

$$ \Pr(X = Y)\geq e^{-H(X)-D(P||Q)} $$

where: $$ D(P||Q)=\sum_{x\in\mathcal{X}}P(x)\log\frac{P(x)}{Q(x)}. $$

---

We can see that KL-divergence naturally appears here. It appears in other places too, For instance, in large deviation theory. Consider a sequence of i.i.d. Bernoulli random variables $X_1,...,X_n$ with parameter $p$. We know from law of large numbers that for $S_n=X_1+...+X_n$, $\frac{S_n}n$ will be a.e. $p$ as $n\to\infty$. Now what is the probability that $\frac{S_n}n$ deviates from $p$ by $\epsilon$ (of course for non-trivial choice of $\epsilon$)? From large deviation theory, we know that: $$ \Pr(\frac{S_n}n \geq (p+\epsilon))\approx e^{-nD(p+\epsilon||p)} $$ where $D(p+\epsilon||p)$ is KL-divergence between two Bernoulli with parameters $p+\epsilon$ and $p$.

---

To sum up, KL-divergence seems very appealing because of its recurrent appearances but there is no "personal preference" in math. Everything depends on the problem you are working on and the context.