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.

Conditional entropy of finite memory given side information

Statement

Let $M$ and $R$ take values in finite sets under a joint probability law $p (m, r) \geq 0$ with $\sum_{m, r} p (m, r) = 1$ . For any finite random variable $Y$ with law $p_{Y}$ , define its Shannon entropy by $H (Y) : = - \sum_{y : p_{Y} (y) > 0} p_{Y} (y) \log p_{Y} (y)$ ; for a pair, $H (M, R)$ means this definition applied to its joint law. Put $a_{r} : = \sum_{m} p (m, r)$ and, when $a_{r} > 0$ , $q (m ∣ r) : = p (m, r) / a_{r}$ . Thus $H (R) = - \sum_{r : a_{r} > 0} a_{r} \log a_{r}$ . Define $H (M ∣ R) : = \sum_{r : a_{r} > 0} a_{r} [- \sum_{m : q (m ∣ r) > 0} q (m ∣ r) \log q (m ∣ r)]$ . Then $H (M, R) = H (R) + H (M ∣ R)$ and $H (M ∣ R) \geq 0$ .

Facts & Assumptions

Given: As stated in the item.

[A1]

$M, R$ take values in finite sets under the joint probability law $p (m, r)$ .

[F1]

Finite probability spaces, outcome weights, events, and event probabilities and Finite sums and finite products, by recursion: joint weights are nonnegative and sum to one, and all displayed sums are finite.

[F2]

The natural logarithm as the inverse of the exponential function and Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: logarithms of positive products add, $\log 1 = 0$ , and $\log x \leq 0$ for $0 < x \leq 1$ .

Proof

Given: A finite joint probability law for $M$ and $R$ .

1.1A1F1F2

For every $r$ with $a_{r} > 0$ , the numbers $q (m ∣ r)$ are nonnegative and sum to one. The joint identity $p (m, r) = a_{r} q (m ∣ r)$ on positive entries gives $\log p (m, r) = \log a_{r} + \log q (m ∣ r)$ ; summing $- p \log p$ over each fixed $r$ yields $- a_{r} \log a_{r} + a_{r} [- \sum_{m : q (m ∣ r) > 0} q (m ∣ r) \log q (m ∣ r)]$ . Terms with $a_{r} = 0$ have all $p (m, r) = 0$ and contribute nothing. Summing over finite $r$ proves the chain rule.

2.1A1F1F2step 1.1∎

For each positive conditional probability $q (m ∣ r) \leq 1$ , [F2] gives $- q (m ∣ r) \log q (m ∣ r) \geq 0$ . Multiplying by $a_{r} \geq 0$ and summing proves $H (M ∣ R) \geq 0$ .

Conditional entropy of finite memory given side information

Statement

Facts & Assumptions

Proof

Depends on

Dependency tree · 2 levels

Sources