# A list of different measures of distance/difference/dissimilarities/similarity of two probability distributions? [duplicate]

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!

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

• In the paper it uses so kind of function called $sup$, do you know what its referring to? – Pinocchio Apr 13 '14 at 18:22
• supremum (of a set). – Thomas Rippl Apr 13 '14 at 20:04

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!).

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.