Abstractions & Latents: Natural Latents
Natural Latents
Each problem is broken into a sequence of lemmas leading to a main result. For each subquestion, try to prove the stated lemma before reading on. If you get stuck, you may treat the lemma as given and proceed to the next part.
Setup
Let \(X_1, \ldots, X_n\) be observable random variables, written \(X = (X_1, \ldots, X_n)\), and let \(Z\) be a latent variable — a finite-valued function of the underlying state \(D\). All entropy and mutual-information quantities are with respect to the joint distribution \(P[X, Z]\). We write \(X_{<i} = (X_1, \ldots, X_{i-1})\).
Total correlation. For a family \(X\), \[ \mathrm{TC}(X) = \sum_i H(X_i) - H(X), \qquad \mathrm{TC}(X \mid Z) = \sum_i H(X_i \mid Z) - H(X \mid Z). \] The conditional version measures the dependence that remains after conditioning on \(Z\).
Mediation. \(Z\) is an \(\varepsilon_{\mathrm{med}}\)-mediator of \(X\) if \(\mathrm{TC}(X \mid Z) \le \varepsilon_{\mathrm{med}}\). An exact mediator (\(\varepsilon_{\mathrm{med}} = 0\)) makes \(X_1, \ldots, X_n\) conditionally independent given \(Z\).
Redundancy. \(Z\) is an \(\varepsilon_{\mathrm{red}}\)-redund over \(X\) if it is recoverable from each observable individually: \(H(Z \mid X_i) \le \varepsilon_{\mathrm{red}}\) for all \(i\). Equivalently, \(r(Z; X) := \max_i H(Z \mid X_i) \le \varepsilon_{\mathrm{red}}\).
Natural latent. \(Z\) is an \((\varepsilon_{\mathrm{med}}, \varepsilon_{\mathrm{red}})\)-natural latent over \(X\) if it is simultaneously an \(\varepsilon_{\mathrm{med}}\)-mediator and an \(\varepsilon_{\mathrm{red}}\)-redund.
The default latent is written \(Z\). When a latent is specifically playing the role of a mediator we write \(Z_{\mathrm{med}}\), and when it is playing the role of a redund we write \(Z_{\mathrm{red}}\). We reserve \(\Lambda\) for a latent that is assumed to be both a mediator and a redund — that is, a natural latent.
Total correlation, the two conditions, and Mediator-Determines-Redund
Exercises 1–3 build fluency with total correlation and the two natural-latent conditions; Exercise 4 proves the core lemma that ties them together, and Exercise 5 shows that lemma is tight.
Exercise 1: Total correlation and screening off
🔵🔵🔵🔵⚫️ Importance 🔴🔴⚫️⚫️⚫️ Difficulty
Part 1(a). Show that \(\mathrm{TC}(X) = \sum_i H(X_i) - H(X) \ge 0\), with equality if and only if \(X_1, \ldots, X_n\) are jointly independent.
Hint for Part 1(a)
Use the chain rule \(H(X) = \sum_i H(X_i \mid X_{<i})\) and the fact that conditioning cannot increase entropy, \(H(X_i \mid X_{<i}) \le H(X_i)\). Summing gives \(H(X) \le \sum_i H(X_i)\), i.e. \(\mathrm{TC}(X) \ge 0\). Equality forces \(H(X_i \mid X_{<i}) = H(X_i)\) for every \(i\), i.e. each \(X_i\) is independent of its predecessors — which is exactly joint independence.
Part 1(b). Show the chain-rule decomposition of conditional total correlation: \[ \mathrm{TC}(X \mid Z) = \sum_{i} I\bigl(X_i; X_{<i} \mid Z\bigr). \] (This identity reappears as the workhorse of Exercise 4.)
Hint for Part 1(b)
Condition the whole of Part 1(a) on \(Z\): \(H(X \mid Z) = \sum_i H(X_i \mid X_{<i}, Z)\), so \[ \mathrm{TC}(X \mid Z) = \sum_i H(X_i \mid Z) - \sum_i H(X_i \mid X_{<i}, Z) = \sum_i \bigl[H(X_i \mid Z) - H(X_i \mid X_{<i}, Z)\bigr] = \sum_i I(X_i; X_{<i} \mid Z). \]
Part 1(c). Suppose there is a variable \(S\) such that \(X_1, \ldots, X_n\) are mutually conditionally independent given \(S\). Show that \(S\) is an exact mediator of \(X\). Then give an example showing that a mediator need not be recoverable from any single \(X_i\) — so mediation, unlike redundancy, does not demand recoverability.
Hint for Part 1(c)
Conditional independence given \(S\) means each \(I(X_i; X_{<i} \mid S) = 0\), so by Part 1(b) \(\mathrm{TC}(X \mid S) = 0\). For the second part, take the common-source story where \(S\) is much richer than any one observation (e.g. \(S\) is a high-resolution scene and each \(X_i\) is a noisy glimpse): \(S\) mediates, yet \(H(S \mid X_i)\) is large, so \(S\) is far from a redund.
Exercise 2: Why each condition alone is too weak
🔵🔵🔵🔵🔵 Importance 🔴⚫️⚫️⚫️⚫️ Difficulty
This exercise formalizes why both conditions are needed: each one, on its own, is satisfied by a trivial latent. In each part, come up with such a latent yourself.
Part 2(a) — mediation alone. Exhibit a latent \(Z\) that is an exact mediator of \(X\) (so \(\mathrm{TC}(X \mid Z) = 0\)) yet is not an explanation in any useful sense. Conclude that mediation alone is too weak a requirement.
Part 2(b) — redundancy alone. Exhibit a latent \(Z\) that is an exact redund over \(X\) (so \(H(Z \mid X_i) = 0\) for every \(i\)) yet carries no information about \(X\) — leaving \(\mathrm{TC}(X \mid Z) = \mathrm{TC}(X)\). Conclude that redundancy alone is too weak a requirement.
Part 2(c). Using 2(a) and 2(b), explain why mediation pushes a latent to be large/fine while redundancy pushes it to be small/coarse, so that only a latent satisfying both — a natural latent — is a nontrivial target.
Hint for Part 2(c)
Mediation is maximized (error driven to \(0\)) by recording all of \(X\); redundancy is maximized by recording nothing of \(X\). The two optima sit at opposite ends. A natural latent must thread the needle: informative enough to screen off the dependence, yet recoverable from each single observation. The next exercises show that, when such a latent exists, it is essentially pinned down.
Exercise 3: A worked natural latent
🔵🔵🔵🔵⚫️ Importance 🔴🔴⚫️⚫️⚫️ Difficulty
Let \(B \sim \mathrm{Bernoulli}(1/2)\), and for \(i = 1, 2\) let \(X_i = B \oplus N_i\) where \(N_1, N_2 \sim \mathrm{Bernoulli}(p)\) are independent of \(B\) and of each other, \(0 < p < 1/2\). Write \(h(p) = -p\ln p - (1-p)\ln(1-p)\).
Part 3(a). Compute \(\mathrm{TC}(X_1, X_2)\) and \(\mathrm{TC}(X_1, X_2 \mid B)\). Is \(B\) a mediator, and with what tolerance?
Hint for Part 3(a)
Given \(B\), \(X_1\) and \(X_2\) are independent (their noises are), so \(\mathrm{TC}(X_1, X_2 \mid B) = I(X_1; X_2 \mid B) = 0\) — \(B\) is an exact mediator. Unconditionally, each \(X_i \sim \mathrm{Bernoulli}(1/2)\) and \(X_1 \oplus X_2 = N_1 \oplus N_2 \sim \mathrm{Bernoulli}(2p(1-p))\), so \(\mathrm{TC}(X_1, X_2) = I(X_1; X_2) = \ln 2 - h\bigl(2p(1-p)\bigr) > 0\).
Part 3(b). Compute \(H(B \mid X_i)\). Is \(B\) a redund, and with what tolerance?
Hint for Part 3(b)
\(X_i = B \oplus N_i\), so conditioning on \(X_i\) leaves exactly the uncertainty of \(N_i\): \(H(B \mid X_i) = H(N_i) = h(p)\). So \(B\) is an \(h(p)\)-redund (with \(r(B; X) = h(p)\)), and a \((0, h(p))\)-natural latent.
Part 3(c). Place \(B\) between the two trivial latents of Exercise 2. Compare its entropy and its two errors to those of the constant latent and of \(Z = (X_1, X_2)\). Which latent is the natural one, and in what sense does it sit “in between”?
Hint for Part 3(c)
The constant latent is a perfect redund (\(\varepsilon_{\mathrm{red}} = 0\)) but a poor mediator (\(\mathrm{TC}(X \mid c) = \ln 2 - h(2p(1-p))\)). The latent \(Z = (X_1, X_2)\) is a perfect mediator (\(\mathrm{TC} = 0\), since it determines \(X\)) but a poor redund (\(H(Z \mid X_i) = H(X_{3-i} \mid X_i) > 0\)). \(B\) is the only one of the three that is small on both errors at once — it carries exactly the shared bit and nothing else. (A closely related single-noise family appears in Exercise 5.)
Exercise 4: Mediator Determines Redund
🔵🔵🔵🔵🔵 Importance 🔴🔴🔴⚫️⚫️ Difficulty
This is the engine of the whole framework. It says that any mediator already determines any redund, so the redundant information is contained in every mediator.
Theorem (Mediator Determines Redund). Let \(n \ge 2\). If \(Z_{\mathrm{med}}\) is an \(\varepsilon_{\mathrm{med}}\)-mediator of \(X\) and \(Z_{\mathrm{red}}\) is an \(\varepsilon_{\mathrm{red}}\)-redund over \(X\), then \[ H(Z_{\mathrm{red}} \mid Z_{\mathrm{med}}) \le \varepsilon_{\mathrm{med}} + 2\varepsilon_{\mathrm{red}}. \]
Prove this in the following steps. Fix two distinct indices \(j \ne k\).
Part 4(a). Show that \[ H(Z_{\mathrm{red}} \mid Z_{\mathrm{med}}) = I(Z_{\mathrm{red}}; X_k \mid Z_{\mathrm{med}}) + H(Z_{\mathrm{red}} \mid X_k, Z_{\mathrm{med}}). \]
Hint for Part 4(a)
This is just the definition of conditional mutual information, \(I(Z_{\mathrm{red}}; X_k \mid Z_{\mathrm{med}}) = H(Z_{\mathrm{red}} \mid Z_{\mathrm{med}}) - H(Z_{\mathrm{red}} \mid X_k, Z_{\mathrm{med}})\), rearranged.
Part 4(b). Show that the mutual-information term splits as \[ I(Z_{\mathrm{red}}; X_k \mid Z_{\mathrm{med}}) \le I(X_k; X_j \mid Z_{\mathrm{med}}) + I(X_k; Z_{\mathrm{red}} \mid X_j, Z_{\mathrm{med}}). \]
Hint for Part 4(b)
By monotonicity, \(I(X_k; Z_{\mathrm{red}} \mid Z_{\mathrm{med}}) \le I(X_k; Z_{\mathrm{red}}, X_j \mid Z_{\mathrm{med}})\) (adding \(X_j\) to the second slot can only increase the information). Now apply the chain rule for conditional mutual information to \(I(X_k; Z_{\mathrm{red}}, X_j \mid Z_{\mathrm{med}})\).
Part 4(c). Bound each of the three resulting terms and combine to finish the proof: \[ I(X_k; X_j \mid Z_{\mathrm{med}}) \le \varepsilon_{\mathrm{med}}, \qquad I(X_k; Z_{\mathrm{red}} \mid X_j, Z_{\mathrm{med}}) \le \varepsilon_{\mathrm{red}}, \qquad H(Z_{\mathrm{red}} \mid X_k, Z_{\mathrm{med}}) \le \varepsilon_{\mathrm{red}}. \] You may use the chain-rule form of conditional total correlation from Exercise 1(b), \(\mathrm{TC}(X \mid Z) = \sum_i I(X_i; X_{<i} \mid Z)\).
Hint for Part 4(c)
- First term: by monotonicity \(I(X_k; X_j \mid Z_{\mathrm{med}}) \le I(X_k; X_{<k} \mid Z_{\mathrm{med}})\), and by nonnegativity this is at most \(\sum_i I(X_i; X_{<i} \mid Z_{\mathrm{med}}) = \mathrm{TC}(X \mid Z_{\mathrm{med}}) \le \varepsilon_{\mathrm{med}}\).
- Second term: \(I(X_k; Z_{\mathrm{red}} \mid X_j, Z_{\mathrm{med}}) \le H(Z_{\mathrm{red}} \mid X_j, Z_{\mathrm{med}}) \le H(Z_{\mathrm{red}} \mid X_j) \le \varepsilon_{\mathrm{red}}\) (entropy bound on MI, then monotonicity).
- Third term: \(H(Z_{\mathrm{red}} \mid X_k, Z_{\mathrm{med}}) \le H(Z_{\mathrm{red}} \mid X_k) \le \varepsilon_{\mathrm{red}}\).
Adding the three bounds gives \(\varepsilon_{\mathrm{med}} + 2\varepsilon_{\mathrm{red}}\). The factor of \(2\) is exactly the two places redundancy is used.
Exercise 5: The Mediator-Determines-Redund bound is tight
🔵🔵🔵🔵⚫️ Importance 🔴🔴⚫️⚫️⚫️ Difficulty
Exercise 4 gives \(H(Z_{\mathrm{red}} \mid Z_{\mathrm{med}}) \le \varepsilon_{\mathrm{med}} + 2\varepsilon_{\mathrm{red}}\). This exercise shows the inequality cannot be improved in general: there is a family on which it holds with equality, with both errors strictly positive.
Let \(X_1 \sim \mathrm{Bernoulli}(1/2)\) and \(N \sim \mathrm{Bernoulli}(p)\) be independent, \(0 < p < 1/2\), and set \(X_2 = X_1 \oplus N\). Take the redund candidate \(Z_{\mathrm{red}} = (X_1, X_2)\) and the mediator candidate \(Z_{\mathrm{med}} = \text{constant}\). Write \(h(p) = -p\ln p - (1-p)\ln(1-p)\).
Part 5(a) — Redundancy tolerance. Compute \(\varepsilon_{\mathrm{red}} = \max_i H(Z_{\mathrm{red}} \mid X_i)\), and show it equals \(h(p)\).
Hint for Part 5(a)
\(Z_{\mathrm{red}} = (X_1, X_2)\), so \(H(Z_{\mathrm{red}} \mid X_1) = H(X_2 \mid X_1) = H(N) = h(p)\), and symmetrically \(H(Z_{\mathrm{red}} \mid X_2) = h(p)\).
Part 5(b) — Mediation tolerance. Compute \(\varepsilon_{\mathrm{med}} = \mathrm{TC}(X_1, X_2 \mid Z_{\mathrm{med}})\), and show it equals \(\ln 2 - h(p)\).
Hint for Part 5(b)
A constant carries no information, so \(\mathrm{TC}(X_1, X_2 \mid Z_{\mathrm{med}}) = \mathrm{TC}(X_1, X_2) = I(X_1; X_2)\). Both \(X_1\) and \(X_2\) are \(\mathrm{Bernoulli}(1/2)\), and \(H(X_2 \mid X_1) = H(N) = h(p)\), so \(I(X_1; X_2) = H(X_2) - H(X_2 \mid X_1) = \ln 2 - h(p)\).
Part 5(c) — Tightness. Compute \(H(Z_{\mathrm{red}} \mid Z_{\mathrm{med}})\) directly, and verify that it equals \(\varepsilon_{\mathrm{med}} + 2\varepsilon_{\mathrm{red}}\) — so the Mediator-Determines-Redund bound is attained with equality, with both errors strictly positive.
Hint for Part 5(c)
Since \(Z_{\mathrm{med}}\) is constant, \(H(Z_{\mathrm{red}} \mid Z_{\mathrm{med}}) = H(X_1, X_2) = H(X_1) + H(X_2 \mid X_1) = \ln 2 + h(p)\). And \(\varepsilon_{\mathrm{med}} + 2\varepsilon_{\mathrm{red}} = (\ln 2 - h(p)) + 2h(p) = \ln 2 + h(p)\) — equal. Both errors are strictly positive for every \(p \in (0, 1/2)\).
Minimal mediation, translatability, and coarsening
These exercises harvest Mediator-Determines-Redund. Exercise 6 shows a natural latent is essentially unique; Exercise 7 reads that same uniqueness across two agents as a translation guarantee (no new math — the work is in the setup and the assumptions); Exercise 8 explains, for \(n > 2\), exactly which global minimality property redundancy corresponds to. Exercise 9 then steps outside that arc to exhibit a family — synergistic structure — where no natural latent exists at all.
Setup recap: comparison notions
Fix tolerances \(\varepsilon_{\mathrm{med}}, \varepsilon_{\mathrm{red}} \ge 0\), and let \(\mathsf{Z}_D\) denote the deterministic latent class (finite-valued functions of \(D\)).
- Mediator class. \(\mathsf{M}_{\varepsilon_{\mathrm{med}}}(X) = \\{Z \in \mathsf{Z}_D : \mathrm{TC}(X \mid Z) \le \varepsilon_{\mathrm{med}}\\}\).
- Redund class. \(\mathsf{R}_{\varepsilon_{\mathrm{red}}}(X) = \\{Z \in \mathsf{Z}_D : r(Z; X) \le \varepsilon_{\mathrm{red}}\\}\), where \(r(Z; X) = \max_i H(Z \mid X_i)\).
- Minimal mediator. A mediator whose information is contained in every other mediator at the same tolerance — informally, the smallest sufficient explanation.
- Maximal redund. A redund that contains every other redund at the same tolerance — informally, the most one can redundantly extract.
- Coarsening. A coarsening scheme is a partition \(C = \\{A_1, \ldots, A_m\\}\) of \([n] = \\{1, \ldots, n\\}\); it is nontrivial if \(m \ge 2\). Writing \(X_A = (X_i)_{i \in A}\), the coarsening of \(X\) induced by \(C\) is the \(m\)-tuple \(X^{(C)} = (X_{A_1}, \ldots, X_{A_m})\).
Exercise 6: Minimality, maximality, and near-uniqueness
🔵🔵🔵🔵🔵 Importance 🔴🔴⚫️⚫️⚫️ Difficulty
Let \(\Lambda\) be an \((\varepsilon_{\mathrm{med}}, \varepsilon_{\mathrm{red}})\)-natural latent over \(X\), with \(n \ge 2\). Each part is a one-step application of Mediator-Determines-Redund (Exercise 4).
Part 6(a) — Minimality among mediators. Show that for any mediator \(Z\) with \(\mathrm{TC}(X \mid Z) \le \varepsilon'_{\mathrm{med}}\), \[ H(\Lambda \mid Z) \le \varepsilon'_{\mathrm{med}} + 2\varepsilon_{\mathrm{red}}. \] That is, \(\Lambda\) is approximately determined by every mediator.
Hint for Part 6(a)
Apply Mediator-Determines-Redund with \(Z_{\mathrm{med}} := Z\) and \(Z_{\mathrm{red}} := \Lambda\) (legitimate because \(\Lambda\) is a redund and \(Z\) is a mediator).
Part 6(b) — Maximality among redunds. Show that for any redund \(Z\) with \(\max_i H(Z \mid X_i) \le \varepsilon'_{\mathrm{red}}\), \[ H(Z \mid \Lambda) \le \varepsilon_{\mathrm{med}} + 2\varepsilon'_{\mathrm{red}}. \] That is, every redund is approximately determined by \(\Lambda\).
Hint for Part 6(b)
Apply Mediator-Determines-Redund with \(Z_{\mathrm{med}} := \Lambda\) and \(Z_{\mathrm{red}} := Z\) (legitimate because \(\Lambda\) is a mediator and \(Z\) is a redund).
Part 6(c) — Near-uniqueness. Let \(\Lambda\) and \(\Lambda'\) both be \((\varepsilon_{\mathrm{med}}, \varepsilon_{\mathrm{red}})\)-natural latents over \(X\). Show that each determines the other, \[ H(\Lambda \mid \Lambda') \le \varepsilon_{\mathrm{med}} + 2\varepsilon_{\mathrm{red}}, \qquad H(\Lambda' \mid \Lambda) \le \varepsilon_{\mathrm{med}} + 2\varepsilon_{\mathrm{red}}, \] and conclude that in the exact case (\(\varepsilon_{\mathrm{med}} = \varepsilon_{\mathrm{red}} = 0\)) a natural latent is unique up to relabeling.
Hint for Part 6(c)
Apply Part 6(a) with \(Z := \Lambda'\) (using that \(\Lambda'\) is a mediator with \(\varepsilon'_{\mathrm{med}} = \varepsilon_{\mathrm{med}}\)), and again with the roles of \(\Lambda, \Lambda'\) swapped. In the exact case both conditional entropies are \(0\), so each is a deterministic function of the other — i.e. they induce the same partition of \(D\), which is what “unique up to relabeling” means.
Exercise 7: Guaranteed Translatability (setup and assumptions)
🔵🔵🔵🔵🔵 Importance 🔴⚫️⚫️⚫️⚫️ Difficulty
This is the alignment payoff — and, crucially, it needs no new mathematics. Guaranteed Translatability is just Exercise 6 read across two agents instead of within one model. The work here is conceptual: pin down the setup, and the assumptions that make the result go through.
Alice and Bob model the same underlying world \(D\). Each has their own latent variables (functions of \(D\)), and their ontologies may differ arbitrarily. They share an observable family \(Y = (Y_1, \ldots, Y_k)\). Let \(Z^A\) and \(Z^B\) be a latent in Alice’s and Bob’s model respectively.
Part 7(a) — The setup. State precisely what it means for Alice and Bob to “share” the observables \(Y\). (Recall an observable is a partition of \(D\), defined only up to relabeling of its values.) What must the two agents actually agree on — and what are they free to disagree on?
Hint for Part 7(a)
Sharing \(Y_j\) means Alice’s and Bob’s \(Y_j\) pick out the same partition of \(D\) — they draw the same distinctions among world-states, even if they label the cells differently. They need agree on nothing else: their other latents, and whatever model each builds on top of \(Y\), can be completely different.
Part 7(b) — Why no new proof is needed. Suppose \(Z^A\) and \(Z^B\) are each natural latents over the shared family \(Y\). Explain why Exercise 6 already gives translation in both directions, \[ H(Z^A \mid Z^B) \le \varepsilon^B_{\mathrm{med}} + 2\varepsilon^A_{\mathrm{red}}, \qquad H(Z^B \mid Z^A) \le \varepsilon^A_{\mathrm{med}} + 2\varepsilon^B_{\mathrm{red}}, \] so each agent’s latent is a function of the other’s, up to the tolerances.
Hint for Part 7(b)
Look again at Mediator-Determines-Redund (Exercise 4): it takes one mediator and one redund of the same family and bounds \(H(\text{redund} \mid \text{mediator})\). It never uses that the two latents belong to the same agent. So this is exactly the near-uniqueness argument of Exercise 6(c), now with the two natural latents living in different models over the shared \(Y\): take \(Z^B\) as the mediator and \(Z^A\) as the redund for the first bound, then swap their roles for the second.
Part 7(c) — Which assumptions are load-bearing? Identify what the guarantee actually requires of the observables, and what it does not:
- Why must the shared family have at least two observables (\(k \ge 2\))? What goes wrong with a single shared observable?
- Why must \(Z^A\) and \(Z^B\) be natural over the shared \(Y\), rather than over each agent’s own private observables?
- How much of the two agents’ models must coincide for translation to be guaranteed?
Hint for Part 7(c)
Mediator-Determines-Redund needs \(n \ge 2\): with a single observable there is no cross-observable dependence to mediate (the total correlation of one variable is zero), so the bound says nothing. Naturality must be over the shared \(Y\) — a latent that mediates and is redundant over Alice’s private observables constrains Bob only insofar as those observables are also his. Beyond agreeing on \(Y\) and each using a natural latent over it, the two models may differ completely. That is the whole point: convergence is forced by the shared structure of the world, not negotiated between the agents.
Exercise 8: Natural latents are minimal mediators over every coarsening
🔵🔵🔵🔵⚫️ Importance 🔴🔴🔴🔴⚫️ Difficulty
Redundancy is a local condition — it constrains \(Z\) relative to each coordinate of \(X\). This exercise shows it has an equivalent global face: \(Z\) is approximately redundant over \(X\) exactly when it is approximately determined by the mediator of every coarsening of \(X\).
Fix \(\varepsilon_{\mathrm{med}} \ge 0\). For a candidate \(Z\), define the coarsening-determination error \[ S_{\varepsilon_{\mathrm{med}}}(Z; X) = \max_{C}\ \max_{W}\ H(Z \mid W), \] where the first maximum ranges over nontrivial coarsenings \(C\) of \([n]\) and the second over \(W \in \mathsf{Z}_D\) with \(\mathrm{TC}(X^{(C)} \mid W) \le \varepsilon_{\mathrm{med}}\). The goal is to prove \[ r(Z; X) \le S_{\varepsilon_{\mathrm{med}}}(Z; X) \le \varepsilon_{\mathrm{med}} + 2\,r(Z; X). \]
Part 8(a) — Upper bound. Fix a nontrivial coarsening \(C = \\{A_1, \ldots, A_m\\}\) and a \(W\) with \(\mathrm{TC}(X^{(C)} \mid W) \le \varepsilon_{\mathrm{med}}\). First show that \(Z\) is an \(r(Z;X)\)-redund over the coarsened tuple \(X^{(C)} = (X_{A_1}, \ldots, X_{A_m})\), then deduce \(H(Z \mid W) \le \varepsilon_{\mathrm{med}} + 2\,r(Z;X)\), and conclude \(S_{\varepsilon_{\mathrm{med}}}(Z; X) \le \varepsilon_{\mathrm{med}} + 2\,r(Z;X)\).
Hint for Part 8(a)
For each block \(A_\ell\) pick any \(i \in A_\ell\); by monotonicity \(H(Z \mid X_{A_\ell}) \le H(Z \mid X_i) \le r(Z; X)\). So \(\max_\ell H(Z \mid X_{A_\ell}) \le r(Z;X)\), i.e. \(Z\) is an \(r(Z;X)\)-redund over \(X^{(C)}\). Now \(X^{(C)}\) is itself a family of \(m \ge 2\) observables, \(W\) mediates it, and \(Z\) is redundant over it — so Mediator-Determines-Redund (Exercise 4), applied to \(X^{(C)}\) with \(Z_{\mathrm{med}} := W\), \(Z_{\mathrm{red}} := Z\), gives \(H(Z \mid W) \le \varepsilon_{\mathrm{med}} + 2\,r(Z;X)\). Take the maxima over \(C\) and \(W\).
Part 8(b) — Lower bound. Show that \(S_{\varepsilon_{\mathrm{med}}}(Z; X) \ge r(Z; X)\) by exhibiting, for each \(i\), a single admissible (coarsening, mediator) pair that already forces \(H(Z \mid X_i)\) into the maximum.
Hint for Part 8(b)
For each \(i\) use the two-block coarsening \(C_i = \\{\\{i\\}, [n] \setminus \\{i\\}\\}\), so \(X^{(C_i)} = (X_i, X_{-i})\), and take \(W = X_i\). Then \(\mathrm{TC}(X^{(C_i)} \mid X_i) = H(X_i \mid X_i) + H(X_{-i} \mid X_i) - H(X_i, X_{-i} \mid X_i) = 0 \le \varepsilon_{\mathrm{med}}\), so this pair is admissible and contributes \(H(Z \mid X_i)\) to the max defining \(S\). Hence \(S_{\varepsilon_{\mathrm{med}}}(Z;X) \ge H(Z \mid X_i)\) for every \(i\); take the max over \(i\).
Part 8(c) — Reading off the equivalence. Conclude the two corollaries:
- If \(Z\) is an \(\varepsilon_{\mathrm{red}}\)-redund over \(X\), then \(S_{\varepsilon_{\mathrm{med}}}(Z; X) \le \varepsilon_{\mathrm{med}} + 2\varepsilon_{\mathrm{red}}\).
- If \(S_{\varepsilon_{\mathrm{med}}}(Z; X) \le \delta\), then \(Z\) is a \(\delta\)-redund over \(X\).
Interpret this as the statement that redundancy and “being a minimal mediator over every coarsening” coincide up to the familiar constants. This is the correct general-\(n\) form of a fact that is special to pairs: when \(n = 2\), each single coordinate is itself a mediator of \((X_1, X_2)\) (since \(\mathrm{TC}(X_1, X_2 \mid X_1) = I(X_1; X_2 \mid X_1) = 0\)), so “determined by every mediator” already forces “recoverable from each coordinate,” i.e. redundancy. For \(n > 2\) a single coordinate need not mediate the whole tuple, which is why one must quantify over all coarsenings.
Hint for Part 8(c)
Both bullets are immediate from the two-sided inequality \(r(Z;X) \le S_{\varepsilon_{\mathrm{med}}}(Z;X) \le \varepsilon_{\mathrm{med}} + 2\,r(Z;X)\): substitute \(r(Z;X) \le \varepsilon_{\mathrm{red}}\) for the first, and \(r(Z;X) \le S_{\varepsilon_{\mathrm{med}}}(Z;X) \le \delta\) for the second.
Exercise 9: Synergy, and when natural latents fail to exist
🔵🔵🔵🔵⚫️ Importance 🔴🔴🔴⚫️⚫️ Difficulty
Some dependence is synergistic: it is present in a family jointly, yet invisible in every individual observable. Because a natural latent must be recoverable from each observable on its own, it is blind to such structure — and this can force natural latents not to exist.
Let \(X_1, X_2 \sim \mathrm{Bernoulli}(1/2)\) be independent, and set \(X_3 = X_1 \oplus X_2\). Consider the family \(X = (X_1, X_2, X_3)\).
Part 9(a) — The dependence is synergistic. Show that the three variables are pairwise independent (\(I(X_i; X_j) = 0\) for \(i \ne j\)) yet jointly dependent, by computing \(\mathrm{TC}(X)\). Conclude that the dependence is invisible to any single observable, but present in the triple.
Hint for Part 9(a)
Each of the three is a uniform bit, and any two of them are independent: e.g. \(P(X_1 = a, X_3 = c) = P(X_1 = a,\, X_2 = a \oplus c) = \tfrac14 = P(X_1=a)P(X_3=c)\), so \(I(X_i; X_j) = 0\) for every pair. But any two determine the third, so \(H(X) = 2\ln 2\), giving \(\mathrm{TC}(X) = 3\ln 2 - 2\ln 2 = \ln 2 > 0\). The dependence appears only when all three are considered together.
Part 9(b) — Only the constant is a redund. Show that any exact redund \(Z\) over \(X\) — i.e. \(H(Z \mid X_i) = 0\) for every \(i\) — must be constant.
Hint for Part 9(b)
\(H(Z \mid X_1) = 0\) makes \(Z\) a function of \(X_1\) alone, and \(H(Z \mid X_2) = 0\) makes it a function of \(X_2\) alone. A variable that is simultaneously a function of two independent variables is constant: writing \(\{Z = z\} = \{X_1 \in A\} = \{X_2 \in B\}\), independence gives \(P(Z = z) = P(X_1 \in A)\,P(X_2 \in B) = P(Z = z)^2\), so \(P(Z = z) \in \{0, 1\}\).
Part 9(c) — No natural latent. Conclude that no nontrivial natural latent exists over \(X\), and interpret the failure in terms of synergy.
Hint for Part 9(c)
By 9(b) the only exact redund is a constant \(c\), and \(\mathrm{TC}(X \mid c) = \mathrm{TC}(X) = \ln 2 > 0\), so \(c\) is not a mediator. Hence no variable is both a redund and a mediator — there is no exact natural latent, and (since any approximate redund is close to constant) no good approximate one either. The reason is structural: strong redundancy demands recoverability from a single observable, but the synergistic dependence here is carried by no single observable, so a redund cannot capture it. This is the obstruction behind the synergy open problem.