Back to the on-screen lesson · Print

Mutual information

How much one variable tells about another: the definition, the two channel formulas, and the divergence it secretly is.

Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.

1. What you will learn

By the end of this lesson you will be able to define mutual information as the reduction in uncertainty about one variable from observing another, write it in its three entropy forms and as a relative entropy, compute it for the flipping and erasure channels and for a variable paired with itself or with an independent one, sort the true statements about it from the false ones, and use it to rank candidate measurements by how much they tell you.

2. What you already have

Conditional entropy as what is left unknown, the chain rule, and relative entropy with Gibbs' inequality. This lesson combines them into the single quantity the rest of the course is about: how much one variable says about another.

3. Mutual information, noise entropy, overlap

The mutual information $I(X; Y)$ is the uncertainty about one variable that observing the other removes. For a channel, $H(Y \mid X)$ is the noise entropy — what the channel adds — and $I$ is the output entropy minus it. In the two-circle picture $I$ is the overlap. Capacity, later in the course, is the largest $I$ an input distribution can achieve.

4. Mutual information

The mutual information between $X$ and $Y$ is the reduction in uncertainty about one from learning the other: $$I(X; Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X) = H(X) + H(Y) - H(X, Y).$$ It also equals $D\big(p(x, y) \,\|\, p(x) p(y)\big)$, the divergence of the joint distribution from what it would be under independence, which by Gibbs makes it nonnegative and zero exactly when $X$ and $Y$ are independent. For a channel, $I(X; Y) = H(Y) - H(Y \mid X)$ reads as output entropy minus noise entropy: a fair bit through a binary symmetric channel with crossover $\varepsilon$ gives $1 - h(\varepsilon)$ bits, through an erasure channel with erasure probability $\alpha$ gives $1 - \alpha$ bits. When $Y = X$, $I = H(X)$: self-information is entropy. Capacity, the subject of unit 5, is the maximum of $I(X; Y)$ over input distributions.

5. Three ways to compute it

For a binary symmetric channel with crossover $p$ and a fair input, the output is still a fair bit ($H(Y) = 1$) and, given the input, the output is a coin with bias $p$ ($H(Y \mid X) = h(p)$). So $I(X; Y) = 1 - h(p)$:

The table is the capacity curve of lesson 13 in disguise: a crossover of $0.1$ leaves about half a bit per use, a crossover of $0.5$ leaves nothing, since the output is then independent of the input.

6. The erasure channel in full

With a fair input and erasure probability $\alpha$, the output takes three values:

Compute $H(Y)$ by grouping: first decide 'erased or not' ($h(\alpha)$ bits), then, if not erased, which bit ($1$ bit, with probability $1 - \alpha$): $H(Y) = h(\alpha) + (1 - \alpha)$. Given $X$, the only uncertainty is whether the erasure happened: $H(Y \mid X) = h(\alpha)$. Subtract: $$I(X; Y) = h(\alpha) + (1 - \alpha) - h(\alpha) = 1 - \alpha.$$ The $h(\alpha)$ cancels, which is why the erasure channel is so much friendlier than the symmetric one: an erasure tells you that something is missing, a flip does not.

Two more anchors. A perfect copy $Y = X$ gives $I(X; X) = H(X) - H(X \mid X) = H(X)$: a variable carries all of its own information. Independent variables give $I = 0$ whatever their entropies.

7. Solving the practice problems

1. Fair bit flipped with probability $p$: $I = 1 - h(p)$; take $h(p)$ from the table.
2. Fair bit erased with probability $\alpha = a / 2^b$: $I = 1 - \alpha$, a plain fraction, no logarithms.
3. $Y = X$ with $X$ uniform on $2^k$ values: $I = H(X) = k$ bits.
4. Independent $X, Y$: $I = 0$, regardless of $H(X)$ and $H(Y)$.

Common mistakes

• Writing $1 - h(\alpha)$ for the erasure channel: that is the symmetric channel's formula. Erasures cost $\alpha$, not $h(\alpha)$.
• Answering $h(p)$ instead of $1 - h(p)$: $h(p)$ is the noise, the information is what is left.
• Giving $H(X) + H(Y)$ or $\min(H(X), H(Y))$ for independent variables; independence means the overlap is empty.

8. Where this usually goes wrong

The commonest error is writing $1 - h(\alpha)$ for the erasure channel: that is the flipping channel's formula. An erasure announces itself, so the cost is $\alpha$ and not $h(\alpha)$. The second is answering $h(p)$ instead of $1 - h(p)$ for a channel that flips: $h(p)$ is the noise, and the information is what is left after it. The third is giving $H(X) + H(Y)$ or $\min(H(X), H(Y))$ for independent variables; independence means the overlap is empty, so $I = 0$ whatever the entropies are. And $I$ is the overlap, never the union: the union is the joint entropy.

9. A noisy channel

1. $X$ uniform binary, $Y$ flips with probability $0.1$: $H(Y) = 1$ (still uniform), $H(Y \mid X) = h(0.1) = 0.469$.

   Output entropy and noise entropy.

2. $I(X; Y) = 1 - 0.469 = 0.531$ bits per use.

   The information that gets through.

10. Mutual information as a divergence

1. $I(X; Y) = \sum p(x, y) \log_2 \dfrac{p(x, y)}{p(x) p(y)} = D(p_{XY} \| p_X p_Y)$.

   Expand $p(x \mid y) / p(x)$.

2. Gibbs: $I \ge 0$, with $I = 0$ exactly when $p(x, y) = p(x) p(y)$, independence.

11. A symmetric channel with crossover $0.25$

1. Fair input, so $H(Y) = 1$: the output is $0$ with probability $\tfrac{1}{2} \cdot 0.75 + \tfrac{1}{2} \cdot 0.25 = \tfrac{1}{2}$.

2. $H(Y \mid X) = h(0.25) = 0.811$.

3. $I(X; Y) = 1 - 0.811 = 0.189$ bits per use.

   A quarter of the bits flipped destroys more than four fifths of the information.

12. An erasure channel with $\alpha = \tfrac{3}{8}$

1. $H(Y) = h(\tfrac{3}{8}) + \tfrac{5}{8}$ and $H(Y \mid X) = h(\tfrac{3}{8})$.

   No need to evaluate $h(3/8)$: it cancels.

2. $I(X; Y) = 1 - \tfrac{3}{8} = \tfrac{5}{8} = 0.625$ bits.

3. Compare: a symmetric channel that flips $\tfrac{3}{8}$ of the bits keeps only $1 - h(0.375) = 0.046$ bits.

13. Your turn: $I(X; Y)$ for a fair bit through an erasure channel with $\alpha = 0.3$

1. $H(X \mid Y) = 0.3 \cdot 1 + 0.7 \cdot 0 = 0.3$.

2. Your turn: work this step out. Its working is at the end of the packet.

   $I = 1 - 0.3 = 0.7$ bits.

14. Guided practice

$X$ is a fair bit. With probability $1/4$ the channel outputs an erasure symbol, and otherwise it outputs $X$ itself. Fill in $H(X)$, $H(X \mid Y)$ and $I(X; Y)$, in bits.

15. Guided practice

The input $X$ is uniform on $8$ values. Match each channel to the mutual information $I(X; Y)$ it achieves, in bits.

16. Practice

$X$ is a fair bit sent through a channel that flips it with probability $0.05$, giving $Y$. Compute $I(X; Y)$ in bits, to three decimal places.

Answer:

17. Practice

Select every statement that is true of $I(X; Y)$ for all random variables $X$ and $Y$.

This task has no paper form; do it on a device.

18. Somewhere new

A label $L$ is uniform on $4$ equally likely classes, so $H(L) = 2$ bits. Three candidate features are measured. Put them in order, most informative first, by $I(L; F)$.

Number the steps in order (write the number in the box):

• Feature A: determines the class outright
• Feature B: narrows it to two equally likely classes
• Feature C: recorded independently of the class

19. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

20. Test question

In the Venn diagram with circles $H(X)$ and $H(Y)$, which region is $I(X; Y)$, and which is $H(X \mid Y)$?

• $I$ is the overlap; $H(X \mid Y)$ is the part of the $X$ circle outside the $Y$ circle
• $I$ is the union; $H(X \mid Y)$ is the overlap
• $I$ is the whole $X$ circle; $H(X \mid Y)$ is the whole $Y$ circle

21. What you can do now

You can compute mutual information for the standard channels and say which region of the entropy diagram it is. Say in your own words why an erasure costs $\alpha$ bits while a flip costs $h(\varepsilon)$, and what the difference between those two channels is. Next: the identities and bounds that connect mutual information to every other quantity so far.

Working for the steps left to you

13. Your turn: $I(X; Y)$ for a fair bit through an erasure channel with $\alpha = 0.3$, step 2