Comparing divergence from uniform distributions with differing supports (discrete)
Imagine we have a potentially biased coin and a potentially biased six-sided die and we want to know which is more biased than the other.
Firstly, is this a reasonable goal? Could it make sense to say, for example, that the coin is more biased than the die?
Secondly, assuming the goal is reasonable, can we use the KL-divergence from the natural uniform (unbiased) distribution to the observed distribution as a measure of bias in such a setup? If not, what might we use instead?
Lastly, if using KL-divergence is reasonable, can we obtain any meaning from the degree of difference between the divergences? For example, if the coin diverges by 2 and the die diverges by 1, can we say the coin is twice as biased as the die?
The coin is to be compared with the uniform distribution over two outcomes while the die is to be compared with a uniform distribution over six outcomes. Clearly, if both discrete random variables were over the same number of possible outcomes, a direct comparison of the KL-divergences would be reasonable. But does this remain true when the number of the outcomes differs?
random-variable discrete-data kullback-leibler
Daniel RenshawDaniel Renshaw
$\begingroup$ The term 'bias' has a particular meaning in statistics (which you wouldn't estimate by K-L divergence). If you mean something different, you should probably use a different term. $\endgroup$ – Glen_b -Reinstate Monica Apr 10 '13 at 11:29
$\begingroup$ Right, I'm not talking of an estimator's bias. But I felt that "biased coin" was a sufficiently well understood idea that the polysemy wouldn't be a problem. $\endgroup$ – Daniel Renshaw Apr 10 '13 at 12:18
$\begingroup$ But there's a direct sense in which 'biased coin' is akin to that meaning - the bias of a coin would be $\pi - 0.5$, if $\pi = P(\textrm{Head})\,$, say, and similarly with a die. If someone says 'what's the bias of this die', my first instinct would be to think they mean $E(X) - 3.5$ - again, the amount that the expectation deviates from the 'fair' value. As such, the question 'which is more biased?' has a direct, obvious answer that doesn't rely on anything more sophisticated than a notion of expectations. So if you mean something else, make it precise, and I'd suggest call it something else. $\endgroup$ – Glen_b -Reinstate Monica Apr 10 '13 at 12:54
$\begingroup$ You must clearly state what you mean, not just in words, but by providing a measure of goodness (mog), in order to evaluate performance to that measure. Flipping the coin is binomial. Rolling the die is multinomial. I'm sure that you could determine a good approximation to the analytic expressions using some reasonably large number of rolls/flips. Without a clear expression for mog, where do you go? KL gives you the KL measure. IMO KL is useful for classification. I have not used it beyond that because a KL value of -2 or of +2 is less relevant for my mog than a KL value of 0. $\endgroup$ – EngrStudent - Reinstate Monica Apr 10 '13 at 13:24
$\begingroup$ I'm wondering if there is some form of 'fairness' that can be compared across random variables that can each take on different numbers of values. For example a coin that always shows heads or a die that always shows 6 is given a minimum fairness (e.g. zero) while a coin or die that does not favour any outcome over others would have maximum fairness (e.g. 1 or infinity). $\endgroup$ – Daniel Renshaw Apr 10 '13 at 13:47
One method that comes to mind is perplexity, which is a common idea in information theory and NLP. Essentially it is defined as $$ \text{Perplexity} = 2^{-\sum_{i}p_i\log_2 p_i} $$ where the exponent can readily be interpreted as the entropy of your probability distribution in bits. The general idea is that if your distribution were encoded as a fair n-sided die, how many faces would it have?
For instance, a fair 6-sided die has distribution $\{\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6}\}$ so it has perplexity $$ \text{Perplexity} = 2^{-\sum_{i=1}^{6}\frac{1}{6}\log_2 \frac{1}{6}} = 2^{\log_2 6} = 6 $$ as we would expect. Now let's consider a die which has distribution $\{\frac{1}{2},\frac{1}{2},0,0,0,0\}$. This has perplexity 2 (note that $0\log 0 = 0$ for us) so is equivalent to a 2-sided die, or an unbiased coin. Try this on a few other examples and you'll find it's a really nice measure of how far a discrete distribution is away from uniform, what you called 'biased'.
Note that you don't have to use the base 2, but it is the most standard form, followed by $e$.
Daniel WorrallDaniel Worrall
$\begingroup$ (+1) Thank you for resurrecting this thread with a nice clear answer. Welcome to our site! $\endgroup$ – whuber♦ Jun 22 '15 at 22:03
Not the answer you're looking for? Browse other questions tagged random-variable discrete-data kullback-leibler or ask your own question.
Kullback–Leibler divergence between two Wishart distributions
Comparing two (or more) discrete distributions
Kullback-Leibler divergence WITHOUT information theory
Obtaining Shannon entropy from "KL-divergence to uniform distribution"
KL Divergence between parallel lines
KL Divergence with different domains
KL divergence of models with both continuous and discrete variables