ExampleConstruction: AI-generatedVerification: 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.

Binary f-, KL-, and Rényi divergences

Example

On $X = {0, 1}$ , take $P = (3 / 4, 1 / 4)$ and $Q = (1 / 4, 3 / 4)$ . Their supports agree and all coordinates are positive.

Facts & Assumptions

Given: The displayed $P, Q$ and the definitions of f-, KL-, and Rényi divergence below.

[F1]

Finite probability vectors: a finite probability vector has nonnegative coordinates summing to one.

[F2]

Finite Kullback–Leibler divergence: $D (P ∥ Q) = \sum_{x : p_{x} > 0} p_{x} \log (p_{x} / q_{x})$ with natural logarithms.

[F3]

Finite Rényi divergence: for $α \neq 1$ , $D_{α} (P ∥ Q) = \log S_{α} (P, Q) / (α - 1)$ with the support conventions stated in its Definition.

[F4]

Finite f-divergence with support conventions: the generator must be finite and convex on $(0, \infty)$ and satisfy $f (1) = 0$ ; its coordinate terms here are $q_{x} f (p_{x} / q_{x})$ .

[F5]

Absolute value in an ordered field and Basic properties of the absolute value: absolute value is real-valued, $∣ c ∣ = c$ for $c \geq 0$ , and $∣ c z ∣ = ∣ c ∣ ∣ z ∣$ .

[F6]

The triangle inequality: $∣ u + v ∣ \leq ∣ u ∣ + ∣ v ∣$ .

[F7]

Convex and strictly convex functions on Euclidean convex sets: a function is convex when it lies below each two-point chord.

Verification

Given: $P = (3 / 4, 1 / 4)$ and $Q = (1 / 4, 3 / 4)$ .

1.1F1F2algebra

By [F2], $D (P ∥ Q) = \frac{3}{4} \log 3 + \frac{1}{4} \log (1 / 3) = \frac{1}{2} \log 3$ . The direction is $P$ to $Q$ ; reversing the vectors gives the same value here by symmetry.

1.2F3algebra

For order $1 / 2$ , each affinity term is $\sqrt{p_{x} q_{x}}$ , so $S_{1 / 2} = 2 \sqrt{3 / 16} = \sqrt{3} / 2$ by [F3]. Therefore $D_{1 / 2} = - 2 \log (\sqrt{3} / 2) = \log (4 / 3)$ .

1.3F3algebra

For order $2$ , [F3] gives $S_{2} = (9 / 16) / (1 / 4) + (1 / 16) / (3 / 4) = 9 / 4 + 1 / 12 = 7 / 3$ , so $D_{2} = \log (7 / 3)$ .

1.4F4F5F6F7algebra

Put $f (t) = \frac{1}{2} ∣ t - 1 ∣$ for $t > 0$ . It is finite-valued and $f (1) = 0$ . For $x, y > 0$ and $s \in [0, 1]$ , $(1 - s) x + s y > 0$ , so [F5] and [F6] give $f ((1 - s) x + s y) = \frac{1}{2} ∣ (1 - s) (x - 1) + s (y - 1) ∣ \leq (1 - s) f (x) + s f (y) .$ Thus [F7] proves that $f$ is convex, so it is an admissible generator in [F4].

2.1F1F4step 1.4algebra∎

The generator in [F4] now gives $D_{f} (P ∥ Q) = \frac{1}{2} \sum_{x} ∣ p_{x} - q_{x} ∣ = \frac{1}{2} (1 / 2 + 1 / 2) = 1 / 2$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

24 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 and 7.12 (standard reference, not scraped)
Tim van Erven and Peter Harremoës, Rényi Divergence and Kullback-Leibler Divergence, §§I-A and II-A (standard reference, not scraped)