Back to the on-screen lesson ·
Why no processing creates information about the source, what a cascade costs, and what makes a statistic sufficient.
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.
By the end of this lesson you will be able to recognise and draw a Markov chain $X \to Y \to Z$, prove the data processing inequality from the chain rule for mutual information written two ways, apply it to a cascade of channels by combining them into one, say which claims about processing follow from it and which do not, explain what makes a statistic sufficient, and use it as a ceiling on what any later analysis of reduced data could reveal.
Mutual information with its chain rule and its nonnegativity. This lesson puts three variables in a row and asks what survives the journey, which is the first result in the course that constrains what any algorithm can do.
Three variables form a Markov chain $X \to Y \to Z$ when $Z$ depends on $X$ only through $Y$. A cascade is two channels in a row, the standard example. A statistic $T(Y)$ is sufficient for $X$ when it loses nothing, $I(X; T) = I(X; Y)$ — the equality case of the inequality this lesson proves.
Random variables form a Markov chain $X \to Y \to Z$ when $Z$ depends on $X$ only through $Y$: $p(z \mid x, y) = p(z \mid y)$, equivalently $I(X; Z \mid Y) = 0$. Any deterministic or random processing of $Y$ that ignores $X$ produces such a chain. The data processing inequality says $$I(X; Z) \le I(X; Y),$$ proved from the chain rule written two ways, $I(X; Y, Z) = I(X; Y) + I(X; Z \mid Y) = I(X; Z) + I(X; Y \mid Z)$, since the first extra term is $0$ and the second is $\ge 0$. No clever function of the data can create information about $X$; it can only preserve or destroy it. A statistic $T(Y)$ is sufficient for $X$ when $I(X; T) = I(X; Y)$, that is when $X \to T \to Y$ also holds. Two channels in cascade illustrate the loss: two flips with probability $0.1$ behave like one flip with probability $0.18$.
Another way: story
A photocopy of a photocopy: each generation can only lose detail. A restoration algorithm that looks only at the copy cannot recover what the copy never had. Whatever information about the original survives in the copy is the most any processing can pass on.
Another way: steps
$X \to Y \to Z$ is a Markov chain when $p(x, y, z) = p(x)\, p(y \mid x)\, p(z \mid y)$: the last stage looks only at $Y$. Three equivalent ways to say it: $p(z \mid x, y) = p(z \mid y)$; $X$ and $Z$ are conditionally independent given $Y$; $I(X; Z \mid Y) = 0$. Any function $Z = g(Y)$, and any channel fed with $Y$ and fresh randomness, produces such a chain. The proof of the data processing inequality is two lines of the chain rule for mutual information:
| Expand $I(X; Y, Z)$ as | Term | Value |
|---|---|---|
| $I(X; Y) + I(X; Z \mid Y)$ | $I(X; Z \mid Y)$ | $0$ by the Markov property |
| $I(X; Z) + I(X; Y \mid Z)$ | $I(X; Y \mid Z)$ | $\ge 0$ always |
| equate | $I(X; Y) = I(X; Z) + I(X; Y \mid Z)$ | $\ge I(X; Z)$ |
Equality $I(X; Z) = I(X; Y)$ holds exactly when $I(X; Y \mid Z) = 0$, that is when $X \to Z \to Y$ is also a Markov chain: $Z$ kept everything about $X$ that $Y$ had. That is the definition of a sufficient statistic. The same argument with the roles reversed gives $I(Y; Z) \ge I(X; Z)$: the inequality cuts both ends of the chain.
Two symmetric channels in a row, with crossovers $p$ and $s$, deliver $Z \ne X$ exactly when one flip happened and the other did not: $$e = p(1 - s) + s(1 - p) = p + s - 2ps.$$ So the cascade is a single symmetric channel with crossover $e$, and with a fair input $I(X; Z) = 1 - h(e)$. The table shows the loss against $I(X; Y) = 1 - h(p)$, the information after the first stage alone:
| $p$ | $s$ | $e = p + s - 2ps$ | $h(e)$ | $1 - h(e)$ | $1 - h(p)$ |
|---|---|---|---|---|---|
| $0.1$ | $0.1$ | $0.18$ | $0.680$ | $0.320$ | $0.531$ |
| $0.1$ | $0.2$ | $0.26$ | $0.827$ | $0.173$ | $0.531$ |
| $0.2$ | $0.2$ | $0.32$ | $0.904$ | $0.096$ | $0.278$ |
| $0.05$ | $0.1$ | $0.14$ | $0.584$ | $0.416$ | $0.714$ |
| $0.1$ | $0.3$ | $0.34$ | $0.925$ | $0.075$ | $0.531$ |
Every row has $I(X; Z) \le I(X; Y)$, as the inequality demands, and $e$ is always closer to $\tfrac{1}{2}$ than $p$ is: noise accumulates toward complete ignorance. Note that $e < p + s$; two independent flips sometimes cancel.
Common mistakes
The first error is adding the flip probabilities of a cascade, $e = p + s$: that double-counts the cases where both channels flip and the bit arrives correct, so the right figure is $p + s - 2ps$. The second is multiplying the mutual informations of the two stages; information does not travel multiplicatively, and the cascade has to be combined into one channel first. The third is believing a clever enough $Z = g(Y)$ can exceed $I(X; Y)$ — at best it matches it. And the inequality is about information, not entropy: $H(Z)$ can easily exceed $H(Y)$ when the processing adds noise of its own.
$X \to Y$ flips with probability $0.1$: $I(X; Y) = 1 - h(0.1) = 0.531$.
The first link.
$Y \to Z$ flips again with probability $0.1$: $Z \ne X$ with probability $0.1 + 0.1 - 2(0.01) = 0.18$, so $I(X; Z) = 1 - h(0.18) = 0.320 < 0.531$.
Information only decreased.
Chain rule: $I(X; Y, Z) = I(X; Y) + I(X; Z \mid Y)$ and also $= I(X; Z) + I(X; Y \mid Z)$.
Expand the same quantity twice.
Markov: $I(X; Z \mid Y) = 0$; nonnegativity: $I(X; Y \mid Z) \ge 0$. Hence $I(X; Y) \ge I(X; Z)$.
Equality iff $I(X; Y \mid Z) = 0$.
$e = 0.05 + 0.1 - 2 \cdot 0.05 \cdot 0.1 = 0.15 - 0.01 = 0.14$.
$h(0.14) = 0.584$.
$-0.14 \log_2 0.14 = 0.397$ and $-0.86 \log_2 0.86 = 0.187$.
$I(X; Z) = 1 - 0.584 = 0.416$ bits, down from $I(X; Y) = 1 - h(0.05) = 0.714$ after the first stage.
For independent flips with bias $\theta$, $p(y_1, \ldots, y_n \mid \theta) = \theta^{t} (1 - \theta)^{n - t}$ where $t$ is the number of heads.
Given $T = t$, every arrangement of the flips has the same probability $1 / \binom{n}{t}$, which does not involve $\theta$: $\theta \to T \to Y$ is Markov.
So $I(\theta; T) = I(\theta; Y)$: keeping only the count loses nothing about the bias.
$Z$ depends on $X$ only through $Y$, so $X \to Y \to Z$ is Markov.
$I(X; f(Y)) \le I(X; Y)$, with equality exactly when $f(Y)$ is sufficient.
A photograph $X$ is scanned to a file $Y$, and a sharpening program turns the file into a print $Z$, looking only at the file. Draw the dependences that make this a Markov chain: join each variable to the one that depends directly on it.
This task has no paper form; do it on a device.
Build the proof that $I(X; Z) \le I(X; Y)$ whenever $X \to Y \to Z$ is a Markov chain.
This task has no paper form; do it on a device.
A fair bit $X$ passes through a channel that flips it with probability $0.2$ to give $Y$, and $Y$ passes through a second independent channel that flips with probability $0.2$ to give $Z$. Compute $I(X; Z)$ in bits, to three decimal places.
Answer:
$X \to Y \to Z$ is a Markov chain. Select every statement that must be true.
This task has no paper form; do it on a device.
A laboratory records measurements $Y$ of a specimen $X$, and computes $I(X; Y) = 4/5$ bits. The raw measurements are then destroyed, and all later work uses a summary $Z$ computed from $Y$ alone. Give the set of values $I(X; Z)$ could take, as an interval in bits.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Which statement is the data processing inequality?
You can bound the information that survives a processing chain and say when nothing is lost. Say in your own words why the entropy of the output can rise while the information about the input falls. Next: Fano's inequality, which turns leftover uncertainty into a floor under the error probability.
13. Your turn: $Z = f(Y)$ for a deterministic $f$; compare $I(X; Z)$ with $I(X; Y)$, step 2