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

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)