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)

  • $\begingroup$ In the paper it uses so kind of function called $sup$, do you know what its referring to? $\endgroup$ – Pinocchio Apr 13 '14 at 18:22
  • 2
    $\begingroup$ supremum (of a set). $\endgroup$ – 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:


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.


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