LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pending

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Mutual information tensorizes over a memoryless vector channel

Statement

Assume AC. Let $X_{1}, \dots, X_{n}$ and $Y_{1}, \dots, Y_{n}$ take values in standard-Borel spaces. Let their joint law have an arbitrary input marginal $P_{X^{n}}$ and the memoryless conditional channel law $P_{Y^{n} ∣ X^{n}} (d y^{n} ∣ x^{n}) = \prod_{i = 1}^{n} W_{i} (d y_{i} ∣ x_{i}),$ where each $W_{i}$ is a probability kernel. No independence across the input coordinates is assumed. Then, as an inequality in $[0, + \infty]$ , $I (X^{n}; Y^{n}) \leq \sum_{i = 1}^{n} I (X_{i}; Y_{i}) .$

Facts & Assumptions

Given: AC, standard-Borel coordinate spaces, an arbitrary joint input law, and the displayed product conditional channel law.

[A1]

The Axiom of Choice: AC is the choice axiom required by the standard-Borel conditional-law and mutual-information chain-rule suppliers.

[F1]

Standard Borel spaces and Finite products of standard Borel spaces are standard Borel: each coordinate space and each finite product used below is standard Borel.

[F2]

Mutual-information chain rule without subtracting infinities: for standard-Borel random elements, $I ((Z, X); Y) = I (Z; Y) + I (X; Y ∣ Z)$ as an equality of extended nonnegative quantities.

[F3]

Conditional mutual information by a same-marginal product law: conditional mutual information is the KL divergence from the same-marginal conditionally independent product law; it is zero when the conditional joint law equals that product law.

[F4]

Kullback–Leibler divergence is nonnegative: mutual information and conditional mutual information, being KL divergences, are nonnegative.

[F5]

KL is invariant under a measurable bijection: a measurable coordinate permutation preserves KL divergence, so mutual information and conditional mutual information are symmetric in their two unconditioned variables.

[F6]

KL chain rule for standard-Borel disintegrations: when two laws have the same conditioning marginal, their joint KL is the integral of the conditional KLs.

Proof

1.1A1F1F2F5givenalgebra

By [F2], successively adjoining $Y_{i}$ to $Y^{i - 1}$ gives $I (X^{n}; Y^{n}) = I (Y^{n}; X^{n}) = \sum_{i = 1}^{n} I (Y_{i}; X^{n} ∣ Y^{i - 1}) = \sum_{i = 1}^{n} I (X^{n}; Y_{i} ∣ Y^{i - 1}) .$ The first equality and the last equality use the coordinate swap in [F5]; the initial term for the empty tuple $Y^{0}$ is zero. Every term is an extended nonnegative quantity, so no subtraction of infinities is involved.

1.2A1F1F2F3F6givenalgebra

Fix $i$ and put $U = X_{i}$ , $V = X_{[n] ∖ {i}}$ , and $W = Y^{i - 1}$ . For $P_{W}$ -almost every $w$ , the conditional channel law makes $Y_{i}$ independent of $V$ given $U$ . Apply [F2] to the conditional law of $(U, V, Y_{i})$ given $W = w$ and use [F3]: $I ((U, V); Y_{i} ∣ W = w) = I (U; Y_{i} ∣ W = w) + I (V; Y_{i} ∣ U, W = w) = I (U; Y_{i} ∣ W = w) .$ Integrating this identity over $P_{W}$ gives $I (X^{n}; Y_{i} ∣ Y^{i - 1}) = I (X_{i}; Y_{i} ∣ Y^{i - 1})$ by [F6] and the conditional-KL definition [F3].

1.3A1F2F3F4F5givenalgebra

The product channel law gives $I (Y^{i - 1}; Y_{i} ∣ X_{i}) = 0$ by [F3]. Expanding $I ((X_{i}, Y^{i - 1}); Y_{i})$ with [F2] first in the order $X_{i}, Y^{i - 1}$ gives $I ((X_{i}, Y^{i - 1}); Y_{i}) = I (X_{i}; Y_{i})$ . Expanding in the reverse order and using the coordinate-swap invariance [F5] gives $I (X_{i}; Y_{i}) = I (Y^{i - 1}; Y_{i}) + I (X_{i}; Y_{i} ∣ Y^{i - 1}) .$ Because the omitted term $I (Y^{i - 1}; Y_{i} ∣ X_{i})$ is zero and $I (Y^{i - 1}; Y_{i}) \geq 0$ by [F4], this proves $I (X_{i}; Y_{i} ∣ Y^{i - 1}) \leq I (X_{i}; Y_{i})$ in the extended nonnegative order.

2.1step 1.1step 1.2step 1.3algebra∎

Sum the coordinate inequalities from step 1.3 and use the chain-rule expansion in step 1.1 together with step 1.2. This gives $I (X^{n}; Y^{n}) \leq \sum_{i = 1}^{n} I (X_{i}; Y_{i})$ for arbitrary dependent input coordinates.

Depends on

Used by

Dependency tree · two levels

74 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Robert M. Gray, Entropy and Information Theory, corrected author-hosted first edition (standard reference, not scraped)
John Duchi, Lecture Notes on Statistics and Information Theory (standard reference, not scraped)