TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pass

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.

Finite data processing for Kullback–Leibler divergence

Statement

For probability vectors $P, Q$ on a finite nonempty alphabet and a stochastic kernel $K$ to another finite nonempty alphabet, $D (P K ∥ Q K) \leq D (P ∥ Q) .$

Facts & Assumptions

Given: $P, Q, K$ as in the Statement.

[F1]

The finite KL generator has the required convex boundary extension: $f (t) = t \log t$ is convex, $f (1) = 0$ , $f (0) = 0$ , and $f_{\infty} = + \infty$ .

[F2]

Finite Kullback–Leibler divergence: $D (P ∥ Q)$ is the f-divergence with generator $t \log t$ , including value $+ \infty$ when $p_{x} > 0 = q_{x}$ .

[F3]

Finite data processing for f-divergences: applying any stochastic kernel to both arguments cannot increase the f-divergence.

[F4]

Finite f-divergence with support conventions: the f-divergence sums $q_{x} f (p_{x} / q_{x})$ on $q_{x} > 0$ and adds $p_{x} f_{\infty}$ on $q_{x} = 0$ .

Proof

1.1F1F2F4givenalgebra

By [F1], $f (t) = t \log t$ is an admissible convex generator with $f (1) = 0$ , $f (0) = 0$ , and $f_{\infty} = + \infty$ . The coordinate formula of [F2] and [F4] therefore contributes $p_{x} \log (p_{x} / q_{x})$ when $p_{x}, q_{x} > 0$ , zero when $p_{x} = 0 \leq q_{x}$ , and $+ \infty$ when $p_{x} > 0 = q_{x}$ . These are exactly the terms and support convention in [F2]; the same identification applies to $P K, Q K$ .

2.1F3step 1.1∎

Apply [F3] to this generator and to the given common kernel $K$ . Step 1.1 identifies the two f-divergences in that inequality with $D (P K ∥ Q K)$ and $D (P ∥ Q)$ , respectively, and gives the stated result.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

16 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

Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning, Chapter 7, §§7.1–7.2 (standard reference, not scraped)
Igal Sason and Sergio Verdú, f-Divergence Inequalities, §II-B, equations (43)–(45) (standard reference, not scraped)