LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedverified 2026-10-15 (gpt-6-luna, gpt-6.1-sol, and delegated Codex review/repair agents; see completed run evidence)

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 of finite random variables

Statement

For finite random variables $M, R$ with joint law $p (m, r)$ and marginals $p_{M}, p_{R}$ , use the entropy definition $H (Y)$ of Conditional entropy of finite memory given side information for $Y = M, R, (M, R)$ . Define $I (M; R) : = \sum_{p (m, r) > 0} p (m, r) \log \frac{p (m, r)}{p_{M} (m) p_{R} (r)}$ . Then $I (M; R) = H (M) + H (R) - H (M, R) = H (M) - H (M ∣ R) \geq 0$ , with equality exactly when $p (m, r) = p_{M} (m) p_{R} (r)$ for every pair.

Facts & Assumptions

Given: As stated in the item.

[A1]

$p (m, r)$ is a joint probability law on finite sets and $p_{M}, p_{R}$ are its marginal laws.

[F1]

Finite probability spaces, outcome weights, events, and event probabilities and Finite sums and finite products, by recursion: the joint and marginal probabilities are finite normalized sums, and if $p (m, r) > 0$ then both marginals are positive.

[F2]

Conditional entropy of finite memory given side information: finite Shannon entropies are defined there and satisfy $H (M, R) = H (R) + H (M ∣ R)$ .

[F3]

The natural logarithm as the inverse of the exponential function and The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $\log t$ is differentiable for $t > 0$ with derivative $1 / t$ .

[F4]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : derivative signs determine monotonicity on an interval.

Proof

Given: A finite joint law $p (m, r)$ and its two marginals.

1.1F3F4

Define $ϕ (t) : = t - 1 - \log t$ for $t > 0$ . Its derivative is $1 - 1 / t$ , nonpositive on $(0, 1]$ and nonnegative on $[1, \infty)$ ; the mean-value theorem [F4] gives $ϕ (t) \geq ϕ (1) = 0$ , with equality only at $t = 1$ . Thus $- \log t \geq 1 - t$ , strictly unless $t = 1$ .

1.2A1F1F2F3algebra

Expanding the finite logarithmic sum gives $I (M; R) = H (M) + H (R) - H (M, R)$ ; applying [F2] rewrites it as $H (M) - H (M ∣ R)$ .

2.1A1F1step 1.1step 1.2∎

Put $q (m, r) : = p_{M} (m) p_{R} (r)$ . For $p (m, r) > 0$ , $q (m, r) > 0$ by [F1], and step 1.1 with $t = q / p$ gives $p \log (p / q) \geq p - q$ . Summing over the support of $p$ yields $I (M; R) \geq 1 - \sum_{p > 0} q \geq 0$ . Equality forces $q = p$ on the support and no $q$ -mass outside it, hence equality at every pair; conversely independence makes each positive logarithm zero.

Mutual information of finite random variables

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources