Entropy, Relative Entropy, Mutual Information

Definitions

Entropy

• a measure of the uncertainty of a random variable
• The entropy of a random variable is a measure of the uncertainty of the random variable
  • it is a measure of the amount of information required on the average to describe the random variable

Relative Entropy

• a measure of the distance between two distributions
• a measure of the inefficiency of assuming that the distribution is $q$ when the true distribution is $p$.

Mutual Information

• a measure of the amount of information that one random variable contains about another random variable

Entropy

Definitions:

• Shannon entropy
• a measure of the uncertainty of a random variable
• The entropy of a random variable is a measure of the uncertainty of the random variable
  • it is a measure of the amount of information required on the average to describe the random variable

Desired Properties

1. Uniform distributions have maximum uncertainty.
2. Uncertainty is additive for independent events.
3. Adding an outcome with zero probability has no effect.
4. The measure of uncertainty is continuous in all its arguments.
5. Uniform distributions with more outcomes have more uncertainty.
6. Events have non-negative uncertainty.
7. Events with a certain outcome have zero uncertainty.
8. Flipping the arguments has no effect.

Formulation

The entropy of a discrete random variable, $X$, is

$H\left(X\right)=-\sum _{x\in {\mathcal {X}}}p\left(x\right)\cdot \log _{2}p\left(x\right)$

(1)

where $X$ has a probability mass function (pmf), $p\left(x\right)$, and an alphabet ${\mathcal {X}}$.

Expected Value

For a discrete random variable, $X$, with probability mass function, $p\left(x\right)$, the expected value of $X$ is

$E\left[X\right]=\sum _{x\in {\mathcal {X}}}x\cdot p\left(x\right)$

(2)

For a discrete random variable, $X$, with probability mass function, $p\left(x\right)$, the expected value of $g\left(X\right)$ is

$E\left[g\left(X\right)\right]=\sum _{x\in {\mathcal {X}}}g\left(x\right)\cdot p\left(x\right)$

(3)

Consider the case where $g\left(x\right)=\log _{2}\left({\tfrac {1}{p\left(x\right)}}\right)$. We get

$E\left[\log _{2}\left({\tfrac {1}{p\left(x\right)}}\right)\right]=\sum _{x\in {\mathcal {X}}}\log _{2}\left({\tfrac {1}{p\left(x\right)}}\right)\cdot p\left(x\right)=-\sum _{x\in {\mathcal {X}}}p\left(x\right)\cdot \log _{2}p\left(x\right)=H\left(X\right)$

(4)

Lemma 1: Entropy is greater than or equal to zero

$H\left(X\right)\geq 0$

(5)

Proof: Since $0\leq p\left(x\right)\leq 1$, then $\log _{2}\left({\tfrac {1}{p\left(x\right)}}\right)\geq 0$, and subsequently, $E\left[\log _{2}\left({\tfrac {1}{p\left(x\right)}}\right)\right]\geq 0$. Thus from Eq. (4) we get $H\left(X\right)\geq 0$.

Lemma 2: Changing the logarithm base

$H_{b}\left(X\right)=\left(\log _{b}a\right)\cdot H_{a}\left(X\right)$

(6)

Proof:

• Given that
  • $H_{b}\left(X\right)=-\sum _{x\in {\mathcal {X}}}p\left(x\right)\cdot \log _{b}p\left(x\right)$
  • $H_{a}\left(X\right)=-\sum _{x\in {\mathcal {X}}}p\left(x\right)\cdot \log _{a}p\left(x\right)$
• And since $\log _{b}p=\log _{b}a\cdot log_{a}p$
• We get $H_{b}\left(X\right)=\left(\log _{b}a\right)\cdot H_{a}\left(X\right)$

Note that the entropy, $H_{b}\left(X\right)$, has units of bits for $b=2$, or nats (natural units) for $b=e$, or dits (decimal digits) for $b=10$.

Joint Entropy

Definition:

• a measure of the uncertainty associated with a set of variables

The joint entropy of a pair of discrete random variables $\left(X,Y\right)$ with joint pmf $p\left(x,y\right)$ is defined as

$H\left(X,Y\right)=-\sum _{x\in {\mathcal {X}}}\sum _{y\in {\mathcal {Y}}}p\left(x,y\right)\cdot \log _{2}p\left(x,y\right)$

(7)