# Math Help - Calculations give me a negative relative entropy

1. ## Calculations give me a negative relative entropy

The Kullback-Leibler Divergence, also known as Relative Entropy in Information Theory, measures the "distance" between two distributions. Usually, one of the distributions is the theoretical, and the other is the empirical. Now, based on Gibbs' Inequality, relative entropy is nonnegative; it is zero only when the two distributions are similar. Below is the general formula for discrete distributions:

$D(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)}. \!$

So, we take the logarithm of p relative to q and multiply it by p, summing over all the values.

My problem is the following. I have two empirical distributions, each having 8 values:

P(i)
=====
0.0152
0.1108
0.0297
0.0405
0.0757
0.0054
0.6405
0.0541

and

Q(i)
=====
0.0000
0.0375
0.0500
0.0625
0.0625
0.0000
0.7875
0.0000

Now, when I calculate the relative entropy D(P||Q), I get a negative value equal to -0.0444. This violates Gibbs' Inequality. Could you think of any possible reason why?

It seems to me that, the terms with indexes 3, 4, 7 yield negative logarithms (to base 2) in the summation, and the result is negative. What am I doing wrong here?

2. Originally Posted by EmpSci
The Kullback-Leibler Divergence, also known as Relative Entropy in Information Theory, measures the "distance" between two distributions. Usually, one of the distributions is the theoretical, and the other is the empirical. Now, based on Gibbs' Inequality, relative entropy is nonnegative; it is zero only when the two distributions are similar. Below is the general formula for discrete distributions:

$D(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)}. \!$

So, we take the logarithm of p relative to q and multiply it by p, summing over all the values.

My problem is the following. I have two empirical distributions, each having 8 values:

P(i)
=====
0.0152
0.1108
0.0297
0.0405
0.0757
0.0054
0.6405
0.0541

and

Q(i)
=====
0.0000
0.0375
0.0500
0.0625
0.0625
0.0000
0.7875
0.0000

Now, when I calculate the relative entropy D(P||Q), I get a negative value equal to -0.0444. This violates Gibbs' Inequality. Could you think of any possible reason why?

It seems to me that, the terms with indexes 3, 4, 7 yield negative logarithms (to base 2) in the summation, and the result is negative. What am I doing wrong here?
I don't know anything about K-L divergence, but your P's do not sum to 1. Could that be it?

3. Thanks for the input, awkward. I fixed the problem for P, now the new values are as follows:

P
=====
0.0432
0.1108
0.0297
0.0405
0.0757
0.0054
0.6405
0.0541

and

Q
=====
0.0000
0.0375
0.0500
0.0625
0.0625
0.0000
0.7875
0.0000

Apparently, in the overall summation, three logarithms are negative, and their sum is larger than the sum of the rest, so the relative entropy results in a negative value, which violates Gibbs' Inequality.

If I find out what the problem is, I'll post the solution here, unless somebody may have some other input on what the problem is.

4. OK, I fixed the problem, which was computational anyways.

As per the K-L Divergence definition, if a $q_{i}$ is 0, then the result of the logarithmic term is infinity, and so is supposed to be the sum (i.e. the relative entropy. Therefore, the result should be infinity wherever the computation gives a negative (for whatever reason), while I assumed (after my third glass of black label JD) that the term would be zero.

In the two distributions I gave above, I set the 0 values to 0.1 x 10^-10 for my own purposes. That gave me positive values.

So, in general, the definition of K-L Divergence is the following:

$

D(P\|Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)}. \!
$

where $0 \log 0 = 0$, for $P(i)=0$ and $P(i) \log \frac{P(i)}{0} = inf$, the latter implying that the pseudo-distance between the two distributions is practically huge.