Entropy, Relative Entropy, Mutual Information

Welcome to CoE 161 / CoE 197!

Since we are offering this class remotely, there will be many changes to our normal course delivery:

1. There will be no face-to-face lecture classes. All the material will be made available via this site.
2. There will be more emphasis on student-centric activities, e.g. analysis, design, and simulations. Thus, you will be mostly "learning by doing". In this context, we will set aside an hour every week for consultations and questions via video-conferencing.
3. Grades will be based on the submitted deliverables from the activities. Though we will not be very strict regarding the deadlines, it is a good idea to keep up with the class schedule and avoid cramming later in the semester.

Please remember that this semester is very different from those before, and please make sure you inform me if you have any issues or difficulties regarding the class. Also, keep in mind that you will need to pay a bit more attention to your time management as it will play a critical role during the course of the semester.

Let's get started!

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)