Pipeline-generated

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.

✓ 10 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 10 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

F-Divergences, Rényi Information, and Hypothesis Testing

1 · Prerequisites

2 · Summary

This finite-alphabet development defines probability vectors, stochastic kernels, support-aware f-divergences, KL divergence, and positive-order Rényi divergence using natural logarithms. It proves data processing for f-divergences, KL, and Rényi orders other than one, then proves the two-sided finite Rényi limit at order one, including the singular-support case. The type-II testing function explicitly takes P as null and Q as alternative, constrains rejection under P, and minimizes acceptance under Q; the final theorem proves that its iid exponent is the directional quantity $D (P ∥ Q)$ .

Applying a channel K to both laws is represented below. Each row is one probability law passed through the same row-stochastic kernel; the diagram records the operation, while the written proofs establish contraction.

\begin{tikzcd}
P \arrow[r, "K"] & PK \\
Q \arrow[r, "K"'] & QK
\end{tikzcd}

The declarations and arguments are finite-alphabet statements. Support mismatch is retained explicitly in every divergence convention.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite probability vectors

Definition

Let $X$ be a finite nonempty set. A probability vector on $X$ is a family $P = (p_{x})_{x \in X}$ of real numbers such that $p_{x} \geq 0$ for every $x$ and $\sum_{x \in X} p_{x} = 1$ . Its support is $supp P : = {x \in X : p_{x} > 0}$ . Coordinates outside the support are retained as zeros; they are not deleted from the alphabet.

For another probability vector $Q = (q_{x})_{x \in X}$ , the notation $P ≪ Q$ means $supp P \subseteq supp Q$ . All finite sums over $X$ use the displayed alphabet and ordinary finite real arithmetic, extended to $+ \infty$ only where a later definition says so.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

Boundary limits of a normalized finite convex generator exist

Statement

Let $f : (0, \infty) \to R$ be convex and satisfy $f (1) = 0$ . Then $f$ is continuous on $(0, \infty)$ , and both extended-real limits $f (0) : = \lim_{t ↓ 0} f (t), f_{\infty} : = \lim_{t \to \infty} \frac{f (t)}{t}$ exist in $R \cup {+ \infty}$ ; neither limit is $- \infty$ .

Facts & Assumptions

Given: A finite convex function $f : (0, \infty) \to R$ with $f (1) = 0$ .

[F1]

Convex and strictly convex functions on Euclidean convex sets: convexity means $f ((1 - s) x + s y) \leq (1 - s) f (x) + s f (y)$ for positive $x, y$ and $s \in [0, 1]$ .

[F2]

The real numbers, The reals form a totally ordered field, The Cauchy-sequence reals have the least-upper-bound property, and Complete ordered field (least-upper-bound property): $R$ is the Cauchy-sequence real field with the least-upper-bound property, so every nonempty set of real numbers bounded above has a real supremum and every nonempty set bounded below has a real infimum.

Proof

1.1F1givenconstructalgebra

Fix $c > 0$ and let $u = c / 2$ , $a = 3 c / 4$ , $b = 5 c / 4$ , and $v = 3 c / 2$ . For $r < s$ , write $m (r, s) = (f (s) - f (r)) / (s - r)$ . If $a \leq x < y \leq b$ , convexity at $a$ between $u, x$ , at $x$ between $u, y$ , at $y$ between $x, v$ , and at $b$ between $y, v$ gives $m (u, a) \leq m (u, x) \leq m (x, y) \leq m (y, v) \leq m (b, v)$ by rearranging the four two-point inequalities in [F1]. All these endpoint slopes are finite. Thus with $M = \max {∣ m (u, a) ∣, ∣ m (b, v) ∣}$ , one has $∣ f (y) - f (x) ∣ \leq M ∣ y - x ∣$ for $x, y \in [a, b]$ , including $x = y$ .

1.2F1F2givenalgebra

Fix $a = 1 / 2$ and set $n (x) = (f (a) - f (x)) / (a - x)$ for $0 < x < a$ . If $0 < x < y < a$ , then $y$ is a convex combination of $x$ and $a$ ; [F1] gives $f (y) \leq \frac{a - y}{a - x} f (x) + \frac{y - x}{a - x} f (a)$ . Rearranging yields $n (x) \leq n (y)$ . Also $a$ is a convex combination of $x$ and $1$ , so another application of [F1] gives $n (x) \leq (f (1) - f (a)) / (1 - a)$ , a finite upper bound. Therefore $L : = \inf_{0 < x < a} n (x)$ is either real or $- \infty$ ; the infimum property from [F2] gives $n (x) \to L$ as $x ↓ 0$ (if $L$ is finite, approximate it within any $ε > 0$ ; if $L = - \infty$ , use any real lower target). Since $f (x) = f (a) - (a - x) n (x)$ , its limit is $f (a) - a L$ if $L$ is finite and $+ \infty$ if $L = - \infty$ . Thus $f (0)$ exists and is not $- \infty$ .

2.1step 1.1givenchoosealgebra

Given $ε > 0$ , choose $δ = \min {c / 4, ε / (M + 1)}$ . If $∣ x - c ∣ < δ$ , then $x, c \in [a, b]$ , and step 1.1 gives $∣ f (x) - f (c) ∣ \leq M ∣ x - c ∣ < ε$ . This is continuity at the arbitrary $c > 0$ , so $f$ is continuous on $(0, \infty)$ .

3.1F1F2givenalgebra∎

For $t > 1$ , put $r (t) = f (t) / (t - 1)$ . If $1 < s < t$ , then $s$ is a convex combination of $1$ and $t$ . By [F1] and $f (1) = 0$ , this gives $r (s) \leq r (t)$ . Hence $r$ is nondecreasing on $(1, \infty)$ and bounded below on $[2, \infty)$ by the finite value $r (2)$ . By the supremum property in [F2], its limit is the real supremum $R$ if it is bounded above, and is $+ \infty$ otherwise: for finite $R$ , values eventually lie between $R - ε$ and $R$ ; when unbounded, they eventually exceed any prescribed real number. Since $f (t) / t = ((t - 1) / t) r (t)$ and $(t - 1) / t \to 1$ , this quotient tends to $R$ if $R$ is finite; if $R = + \infty$ , the factor is at least $1 / 2$ for $t \geq 2$ and the quotient tends to $+ \infty$ . Thus $f_{\infty}$ exists and is not $- \infty$ .

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

The finite KL generator has the required convex boundary extension

Statement

For $f (t) = t \log t$ on $t > 0$ , one has $f (1) = 0$ , $f$ is convex on $(0, \infty)$ , $\lim_{t ↓ 0} f (t) = 0$ , and $\lim_{t \to \infty} f (t) / t = + \infty$ .

Facts & Assumptions

Given: The function $f : (0, \infty) \to R$ defined by $f (t) = t \log t$ .

[F1]

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: $\log$ is defined on $(0, \infty)$ , is strictly increasing and onto $R$ , satisfies $\log 1 = 0$ , and $\log (1 / t) = - \log t$ .

[F2]

The derivative $f^{'} (c) = \lim_{x \to c} \frac{f (x) - f (c)}{x - c}$ of $f : A \to R$ at a point $c \in A$ that is a limit point of $A$ , and differentiability on a set, The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : $\log^{'} (t) = 1 / t$ , and the product rule holds. The identity function has derivative $1$ and constant functions have derivative $0$ , directly from the difference quotient in The derivative $f^{'} (c) = \lim_{x \to c} \frac{f (x) - f (c)}{x - c}$ of $f : A \to R$ at a point $c \in A$ that is a limit point of $A$ , and differentiability on a set.

[F3]

A twice-differentiable function on an open interval is convex if and only if its second derivative is nonnegative and Convex and strictly convex functions on Euclidean convex sets: a twice differentiable function on an open interval is convex when its second derivative is nonnegative there.

[F4]

The logarithm grows more slowly than every positive real power: $\log s / s \to 0$ as $s \to + \infty$ .

Proof

1.1F1F2F3givenalgebra

By [F1], $f (1) = \log 1 = 0$ . The difference quotient in [F2] gives derivative $1$ for the identity function and $0$ for a constant function. Applying the product rule and then the logarithm derivative in [F2] yields $f^{'} (t) = \log t + 1$ and $f^{''} (t) = 1 / t > 0$ for every $t > 0$ . Thus [F3] gives convexity on $(0, \infty)$ .

1.2F1F4givenalgebra

Put $s = 1 / t$ . As $t ↓ 0$ , $s \to + \infty$ and [F1] gives $t \log t = - \log (s) / s$ . Its limit is zero by [F4], so $\lim_{t ↓ 0} f (t) = 0$ .

2.1F1givenchoosealgebra∎

For $t > 0$ , $f (t) / t = \log t$ . Since $\log$ is increasing and onto $R$ by [F1], for each real $M$ there exists $a > 0$ with $\log a > M$ , and every $t > a$ has $\log t \geq \log a > M$ . Thus $\lim_{t \to \infty} f (t) / t = + \infty$ .

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

The finite Rényi generators are convex with stated boundary values

Statement

For $α > 1$ , the generator $h_{α} (t) = t^{α} - 1$ is convex on $(0, \infty)$ , satisfies $h_{α} (1) = 0$ , has $h_{α} (0 +) = - 1$ , and has recession limit $\lim_{t \to \infty} h_{α} (t) / t = + \infty$ . For $0 < α < 1$ , the generator $g_{α} (t) = 1 - t^{α}$ is convex on $(0, \infty)$ , satisfies $g_{α} (1) = 0$ , has $g_{α} (0 +) = 1$ , and has recession limit $\lim_{t \to \infty} g_{α} (t) / t = 0$ .

Facts & Assumptions

Given: The positive-base power functions in the Statement and the corresponding exponent range.

[F1]

Real powers for positive bases, with the zero-base positive-exponent convention: for $t > 0$ , $t^{γ} = \exp (γ \log t)$ .

[F2]

Continuity and derivatives of positive-base real powers and Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : $(t^{γ})^{'} = γ t^{γ - 1}$ and the derivative algebra rules hold for real $γ$ .

[F3]

[F4]

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: $\log$ is an increasing surjection onto $R$ and $\log (1 / t) = - \log t$ .

[F5]

The exponential tends to $+ \infty$ at $+ \infty$ and to $0$ at $- \infty$ : $\exp u \to + \infty$ as $u \to + \infty$ , and $\exp u > 0$ .

[F6]

The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ : $\exp (- u) = 1 / \exp (u)$ for every real $u$ .

Proof

1.1F1F4F5givenalgebra

Let $γ > 0$ . As $t \to + \infty$ , $\log t \to + \infty$ because [F4] is increasing and onto. Hence $γ \log t \to + \infty$ , so $t^{γ} = \exp (γ \log t) \to + \infty$ by [F1, F5].

1.2F1F4F5F6givenalgebra

Let $γ > 0$ and put $s = 1 / t$ . As $t ↓ 0$ , $s \to + \infty$ . By [F1], [F4], and [F6], $t^{γ} = \exp (- γ \log s) = 1 / \exp (γ \log s) \to 0$ by [F5].

2.1F1F2F3step 1.1step 1.2algebra

For $α > 1$ , [F2] gives $h_{α}^{''} (t) = α (α - 1) t^{α - 2} > 0$ , so [F3] proves convexity; also $h_{α} (1) = 0$ . By step 1.2, $h_{α} (0 +) = 0^{α} - 1 = - 1$ . By step 1.1 with $γ = α - 1$ , $t^{α - 1} \to + \infty$ , and $1 / t \leq 1$ for $t \geq 1$ , so $h_{α} (t) / t = t^{α - 1} - 1 / t \to + \infty$ .

3.1F1F2F3step 1.2constructalgebra∎

For $0 < α < 1$ , [F2] gives $g_{α}^{''} (t) = α (1 - α) t^{α - 2} > 0$ , so [F3] proves convexity; also $g_{α} (1) = 0$ . By step 1.2, $g_{α} (0 +) = 1$ . Put $u = 1 / t$ . As $t \to + \infty$ , $u ↓ 0$ , and step 1.2 with $γ = 1 - α$ gives $u^{1 - α} \to 0$ , that is, $t^{- (1 - α)} \to 0$ . For $t \geq 1$ , $0 \leq ∣ g_{α} (t) / t ∣ = t^{- (1 - α)} - 1 / t \leq t^{- (1 - α)}$ . Therefore $g_{α} (t) / t \to 0$ .

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite f-divergence with support conventions

Definition

Let $P = (p_{x})$ and $Q = (q_{x})$ be probability vectors on a finite nonempty alphabet $X$ (Finite probability vectors). A convex generator is a finite convex function $f : (0, \infty) \to R$ with $f (1) = 0$ ; convexity uses the two-point inequality of Convex and strictly convex functions on Euclidean convex sets. Use its extended boundary values $f (0) : = \lim_{t ↓ 0} f (t), f_{\infty} : = \lim_{t \to \infty} \frac{f (t)}{t} .$ These limits exist in $R \cup {+ \infty}$ by Boundary limits of a normalized finite convex generator exist. Define the finite f-divergence from $P$ to $Q$ by $D_{f} (P ∥ Q) : = \sum_{x : q_{x} > 0} q_{x} f (p_{x} / q_{x}) + f_{\infty} \sum_{x : q_{x} = 0} p_{x} .$ In the first sum, if $p_{x} = 0$ , the term means $q_{x} f (0)$ . A coordinate with $p_{x} = q_{x} = 0$ contributes zero and is omitted. The second term is defined as zero when its coefficient $\sum_{q_{x} = 0} p_{x}$ is zero, even if $f_{\infty} = + \infty$ ; if that coefficient is positive and $f_{\infty} = + \infty$ , the divergence is $+ \infty$ .

The boundary term is essential when $P ≪̸ Q$ . It is the recession contribution of the generator and is not the value $f (0)$ .

DefinitionDefinition: AI-adaptedProof: Not applicableOpen item page →

Finite type-II testing function with explicit orientation

Definition

Let $P, Q$ be probability vectors on a finite nonempty alphabet $X$ (Finite probability vectors). They define finite probability spaces with outcome weights $p_{x}$ and $q_{x}$ , respectively (Finite probability spaces, outcome weights, events, and event probabilities). For $h : X \to R$ , write $E_{P} h : = \sum_{x} p_{x} h (x)$ and $E_{Q} h : = \sum_{x} q_{x} h (x)$ ; these are the finite expectations (Expectation of a real random variable on a finite probability space). Test the simple null $H_{0} : P$ against the simple alternative $H_{1} : Q$ . A randomized test is a function $ϕ : X \to [0, 1]$ , where $ϕ (x)$ is the probability of rejecting $H_{0}$ after observing $x$ ; thus $1 - ϕ (x)$ is the probability of accepting $H_{0}$ (Randomized tests). Its type-I error is $\sum_{x} p_{x} ϕ (x)$ , and its type-II error is $\sum_{x} q_{x} (1 - ϕ (x))$ (Test size and power).

For $ϵ \in [0, 1]$ , define the oriented type-II testing function $β_{ϵ} (P, Q) : = \inf_{\begin{array}{c} ϕ : X \to [0, 1] \\ \sum_{x} p_{x} ϕ (x) \leq ϵ \end{array}} \sum_{x} q_{x} (1 - ϕ (x)) .$ Here the first argument is the null law and the second is the alternative law; $ϵ$ bounds rejection under the first law, while the objective is acceptance of the null under the second. The feasible set is nonempty because $ϕ = 0$ is allowed, and every objective value lies in $[0, 1]$ . Thus the set of objective values is nonempty and bounded below in $R$ , so it has a real infimum: The real numbers identifies $R$ with the Cauchy-sequence reals, The reals form a totally ordered field gives their ordered-field structure, and The Cauchy-sequence reals have the least-upper-bound property gives their least-upper-bound property. Complete ordered field (least-upper-bound property) gives the equivalent infimum property. Since the set also lies in $[0, 1]$ , that infimum lies in $[0, 1]$ . In the Neyman–Pearson-region convention that constrains null acceptance below by $γ$ , this is the lower boundary value at $γ = 1 - ϵ$ .

Remarks

The symbol $β_{ϵ} (P, Q)$ here is the infimum type-II error. It is not the power function $E_{θ} [ϕ]$ from Test size and power; under $Q$ , it minimizes one minus that power.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite stochastic kernels

Definition

Let $X, Y$ be finite nonempty sets. A stochastic kernel from $X$ to $Y$ is a matrix $K = (K (y ∣ x))_{x \in X, y \in Y}$ such that $K (y ∣ x) \geq 0$ and $\sum_{y \in Y} K (y ∣ x) = 1$ for every $x \in X$ . The convention is input first in the condition and output first in the value $K (y ∣ x)$ .

For a probability vector $P = (p_{x})_{x \in X}$ , the output vector $P K$ on $Y$ is $(P K)_{y} : = \sum_{x \in X} p_{x} K (y ∣ x) .$ It is a probability vector because its coordinates are nonnegative and $\sum_{y} (P K)_{y} = \sum_{x} p_{x} \sum_{y} K (y ∣ x) = \sum_{x} p_{x} = 1$ .

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite Kullback–Leibler divergence

Definition

For probability vectors $P = (p_{x})$ and $Q = (q_{x})$ on the same finite nonempty alphabet, their Kullback–Leibler divergence (or relative entropy) in the stated direction from $P$ to $Q$ is $D (P ∥ Q) : = \sum_{x : p_{x} > 0} p_{x} \log \frac{p_{x}}{q_{x}} .$ The logarithm is natural. If $p_{x} > 0$ and $q_{x} = 0$ for at least one $x$ , set $D (P ∥ Q) = + \infty$ . If $p_{x} = 0$ , its contribution is zero, including when $q_{x} = 0$ ; equivalently, $0 \log (0 / q_{x}) = 0$ . When $P ≪ Q$ , all ratios in the sum are positive and finite.

The generator $f (t) = t \log t$ is admissible for Finite f-divergence with support conventions by The finite KL generator has the required convex boundary extension. Its boundary values $f (0) = 0$ and $f_{\infty} = + \infty$ make that f-divergence exactly the displayed KL formula, including the singular-support case.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

The closed convex perspective is subadditive

Statement

Let $f$ be a convex generator from Finite f-divergence with support conventions. Define its closed perspective on $a, b \geq 0$ by $Π_{f} (a, b) : = {\begin{cases} b f (a / b), & b > 0, a > 0, \\ b f (0), & b > 0, a = 0, \\ a f_{\infty}, & b = 0, a > 0, \\ 0, & a = b = 0. \end{cases}$ For every finite family $(a_{i}, b_{i}) \in [0, \infty)^{2}$ , $Π_{f} ⁣ (\sum_{i} a_{i}, \sum_{i} b_{i}) \leq \sum_{i} Π_{f} (a_{i}, b_{i}) .$

Facts & Assumptions

Given: A convex generator $f$ with the extended boundary values $f (0)$ and $f_{\infty}$ defined in Finite f-divergence with support conventions, and a finite family of nonnegative pairs $(a_{i}, b_{i})$ .

[F1]

Finite f-divergence with support conventions: $f$ is convex on $(0, \infty)$ , $f (1) = 0$ , $f (0) = \lim_{t ↓ 0} f (t)$ , and $f_{\infty} = \lim_{t \to \infty} f (t) / t$ ; the value at a positive first coordinate and zero second coordinate is the corresponding first coordinate times $f_{\infty}$ .

[F2]

Finite Jensen inequality for convex functions on $R^{n}$ : for a finite family of points in a convex domain and nonnegative weights summing to one, the convex function at their weighted average is at most the weighted sum of its values.

[F3]

Boundary limits of a normalized finite convex generator exist: every finite convex generator is continuous at every positive argument.

Proof

1.1F1givenalgebra

Put $A = \sum_{i} a_{i}$ and $B = \sum_{i} b_{i}$ . If $B = 0$ , all $b_{i} = 0$ . If $A = 0$ , every pair is $(0, 0)$ and both sides are zero. If $A > 0$ , both sides equal $A f_{\infty}$ by the definition of $Π_{f}$ , including the convention that a positive coefficient times $+ \infty$ is $+ \infty$ .

1.2F1F2F3givenalgebra

Suppose $B > 0$ and no index has $b_{i} = 0 < a_{i}$ . If any $b_{i} > 0 = a_{i}$ with $f (0) = + \infty$ , the right side is $+ \infty$ and the inequality holds. If $f (0)$ is finite, extend $f$ to the convex domain $[0, \infty)$ by that value. This extension is convex at the endpoint too: approximate a zero argument in any convexity inequality by positive arguments and pass to the limit using $f (0) = \lim_{t ↓ 0} f (t)$ from [F1] and continuity at positive arguments from [F3]. If $f (0) = + \infty$ , the excluded case shows that every index with $b_{i} > 0$ has $a_{i} > 0$ , so all ratios used below lie in the original convex domain $(0, \infty)$ . For indices with $b_{i} > 0$ , the weights $b_{i} / B$ sum to one and $A / B = \sum_{b_{i} > 0} (b_{i} / B) (a_{i} / b_{i})$ . Applying [F2] gives $B f (A / B) \leq \sum_{b_{i} > 0} b_{i} f (a_{i} / b_{i})$ ; terms $(a_{i}, b_{i}) = (0, 0)$ contribute zero. This is the asserted inequality.

2.1F1F2F3givenconstructalgebra∎

Suppose $B > 0$ and $J : = {i : b_{i} = 0 < a_{i}}$ is nonempty. If $f_{\infty} = + \infty$ , the right side is $+ \infty$ , so the inequality holds. If any $b_{i} > 0 = a_{i}$ with $f (0) = + \infty$ , the right side is $+ \infty$ and the inequality holds. Otherwise, if $f_{\infty}$ is finite, replace each $b_{i} = 0$ with $i \in J$ by $b_{i}^{(η)} = η > 0$ , leaving all other second coordinates unchanged. the finite Jensen inequality [F2] then gives $(B + ∣ J ∣ η) f (A / (B + ∣ J ∣ η)) \leq \sum_{b_{i} > 0} b_{i} f (a_{i} / b_{i}) + \sum_{i \in J} η f (a_{i} / η)$ . As $η ↓ 0$ , the left side tends to $B f (A / B)$ by [F3] at the positive number $A / B$ , and each last summand tends to $a_{i} f_{\infty}$ by the definition of $f_{\infty}$ . The resulting inequality is exactly $Π_{f} (A, B) \leq \sum_{i} Π_{f} (a_{i}, b_{i})$ .

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite Rényi divergence

Definition

Let $P = (p_{x})$ and $Q = (q_{x})$ be probability vectors on the same finite nonempty alphabet. For order $α \in (0, \infty)$ with $α \neq 1$ , put $S_{α} (P, Q) : = \sum_{x : q_{x} > 0} p_{x}^{α} q_{x}^{1 - α} .$ If $α > 1$ and $p_{x} > 0 = q_{x}$ for some $x$ , define $S_{α} (P, Q) = + \infty$ ; if $0 < α < 1$ , such coordinates contribute zero. In the displayed sum, $p_{x} = 0 < q_{x}$ contributes zero. If the sum is zero, then necessarily $α < 1$ and the logarithmic expression below is defined as $+ \infty$ . The Rényi divergence of order $α$ from $P$ to $Q$ is $D_{α} (P ∥ Q) : = \frac{\log S_{α} (P, Q)}{α - 1} .$ At order one define $D_{1} (P ∥ Q) : = D (P ∥ Q),$ using Finite Kullback–Leibler divergence. All divergences are extended-real-valued; the direction is always first argument to second.

For $0 < α < 1$ , a point with $p_{x} > 0 = q_{x}$ contributes zero to the affinity $S_{α}$ rather than infinity. For $α > 1$ , the same support mismatch makes $D_{α} (P ∥ Q) = + \infty$ . The sign of $α - 1$ is part of the definition and reverses inequalities when $0 < α < 1$ .

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

Finite iid log-likelihood averages concentrate

Statement

Let $P = (p_{x})$ and $Q = (q_{x})$ be probability vectors on a finite nonempty alphabet with $P ≪ Q$ . For $n \geq 1$ , write $P^{n} (x_{1}, \dots, x_{n}) = \prod_{i} p_{x_{i}}$ and $Q^{n} (x_{1}, \dots, x_{n}) = \prod_{i} q_{x_{i}}$ . Let $X_{1}, \dots, X_{n}$ be independent with common law $P$ , define $ℓ (x) = \log (p_{x} / q_{x})$ when $p_{x} > 0$ and $ℓ (x) = 0$ when $p_{x} = 0$ , and put $L_{n} = \sum_{i = 1}^{n} ℓ (X_{i})$ . Then $L_{n} / n \to D (P ∥ Q)$ in probability as $n \to \infty$ . For every $x^{n} \in supp (P)^{n}$ , one also has $Q^{n} (x^{n}) = P^{n} (x^{n}) \exp (- L_{n} (x^{n}))$ .

Facts & Assumptions

Given: $P, Q$ with $P ≪ Q$ , and an independent identically distributed sample $X_{1}, \dots, X_{n}$ with law $P$ .

[F1]

Finite probability vectors: $supp P$ is finite and all its coordinates have positive mass; $P ≪ Q$ gives $q_{x} > 0$ whenever $p_{x} > 0$ .

[F2]

Finite Kullback–Leibler divergence: the finite mean of $ℓ (X) = \log (p_{X} / q_{X})$ under $P$ is $\sum_{x : p_{x} > 0} p_{x} \log (p_{x} / q_{x}) = D (P ∥ Q)$ .

[F3]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: the logarithm of a finite product of positive ratios is the sum of their logarithms.

[F4]

The natural logarithm as the inverse of the exponential function: $\exp (\log r) = r$ for $r > 0$ .

[F5]

The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ : $\exp (- u) = 1 / \exp (u)$ for every real $u$ .

[F6]

Expectation of a real random variable on a finite probability space: on a finite probability space, expectation is the finite probability-weighted sum.

Proof

1.1F1F3F4F5givenalgebra

For $x^{n} \in supp (P)^{n}$ , every ratio $p_{x_{i}} / q_{x_{i}}$ is positive. By [F3], $L_{n} (x^{n}) = \log \prod_{i} (p_{x_{i}} / q_{x_{i}})$ . Applying [F4] and [F5] gives $\exp (L_{n} (x^{n})) = P^{n} (x^{n}) / Q^{n} (x^{n})$ and hence $Q^{n} (x^{n}) = P^{n} (x^{n}) \exp (- L_{n} (x^{n}))$ .

2.1F1F2F6givenalgebra∎

The values $ℓ (x)$ on the finite set $supp P$ form a bounded finite-valued random variable. Put $Y_{i} : = ℓ (X_{i}) - D (P ∥ Q)$ ; [F2] and the finite-sum expectation formula [F6] give $E [Y_{i}] = 0$ . Let $σ^{2} = E [Y_{i}^{2}] < \infty$ , which is independent of $i$ since all $X_{i}$ have law $P$ . For $i \neq j$ , expanding the expectation on the product law $P^{n}$ using [F6] gives $E [Y_{i} Y_{j}] = {(\sum_{x} p_{x} (ℓ (x) - D (P ∥ Q)))}^{2} \prod_{k \neq i, j} (\sum_{x} p_{x}) = 0,$ where the square is zero by [F2] and the remaining factors equal one by [F1]. Expanding $E [(n^{- 1} \sum_{i} Y_{i})^{2}]$ therefore gives $σ^{2} / n$ . For every $δ > 0$ , the pointwise inequality $δ^{2} 1_{{∣ n^{- 1} \sum_{i} Y_{i} ∣ \geq δ}} \leq (n^{- 1} \sum_{i} Y_{i})^{2}$ and [F6] imply $P^{n} (∣ L_{n} / n - D (P ∥ Q) ∣ \geq δ) \leq σ^{2} / (n δ^{2}) \to 0$ , since the expectation of an indicator is the probability of its event.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

Finite data processing for f-divergences

Statement

Let $P, Q$ be probability vectors on a finite nonempty alphabet $X$ , let $K$ be a stochastic kernel from $X$ to a finite nonempty alphabet $Y$ , and let $f$ be a convex generator as in Finite f-divergence with support conventions. Then $D_{f} (P K ∥ Q K) \leq D_{f} (P ∥ Q),$ with both divergences interpreted using the zero and singular-support conventions of that definition.

Facts & Assumptions

Given: The vectors $P, Q$ , the kernel $K$ , and the convex generator $f$ in the Statement.

[F1]

Finite probability vectors: $P$ and $Q$ have nonnegative coordinates summing to one.

[F2]

Finite stochastic kernels: $K (y ∣ x) \geq 0$ , $\sum_{y} K (y ∣ x) = 1$ , and $(P K)_{y} = \sum_{x} p_{x} K (y ∣ x)$ , with the same formula for $Q K$ .

[F3]

Finite f-divergence with support conventions: $D_{f} (P ∥ Q)$ is the sum of the closed perspective terms for each coordinate, including $p_{x} f_{\infty}$ when $q_{x} = 0 < p_{x}$ .

[F4]

The closed convex perspective is subadditive: the closed perspective is $Π_{f} (a, b) = b f (a / b)$ for $b > 0$ , with the stated boundary values; it is positively homogeneous and its value at a coordinatewise sum is at most the sum of the values.

Proof

1.1F1F2F3F4givenalgebra

For each $y \in Y$ and $x \in X$ , set $a_{x, y} = p_{x} K (y ∣ x)$ and $b_{x, y} = q_{x} K (y ∣ x)$ . By [F2], $(P K)_{y} = \sum_{x} a_{x, y}$ and $(Q K)_{y} = \sum_{x} b_{x, y}$ . Applying [F4] at each $y$ gives $Π_{f} ((P K)_{y}, (Q K)_{y}) \leq \sum_{x} Π_{f} (p_{x} K (y ∣ x), q_{x} K (y ∣ x))$ . Summing this finite family of inequalities over $y$ is valid for extended real terms because no term is $- \infty$ .

2.1F2F3step 1.1algebra∎

For any $λ > 0$ , the definition of $Π_{f}$ gives $Π_{f} (λ a, λ b) = λ Π_{f} (a, b)$ , including $a = 0$ or $b = 0$ ; when $λ = 0$ , both sides are interpreted as zero. Thus, for each $x$ , the row-sum condition in [F2] yields $\sum_{y} Π_{f} (p_{x} K (y ∣ x), q_{x} K (y ∣ x)) = \sum_{y} K (y ∣ x) Π_{f} (p_{x}, q_{x}) = Π_{f} (p_{x}, q_{x})$ . Substituting these identities into step 1.1 and summing over the finite alphabet $X$ proves $D_{f} (P K ∥ Q K) \leq D_{f} (P ∥ Q)$ by [F3].

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

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.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

Finite data processing for Rényi divergence

Statement

Let $P, Q$ be probability vectors on a finite nonempty alphabet $X$ and let $K$ be a stochastic kernel from $X$ to a finite nonempty alphabet $Y$ . For every $α \in (0, \infty) ∖ {1}$ , $D_{α} (P K ∥ Q K) \leq D_{α} (P ∥ Q),$ with Rényi divergence as defined in Finite Rényi divergence.

Facts & Assumptions

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

[F1]

Finite Rényi divergence: for $α \neq 1$ , $D_{α} (P ∥ Q) = \log S_{α} (P, Q) / (α - 1)$ ; a positive $P$ -mass at a zero $Q$ -coordinate makes $S_{α} = + \infty$ when $α > 1$ , while for $0 < α < 1$ it contributes zero.

[F2]

Finite f-divergence with support conventions: a convex generator $f$ defines the closed-perspective sum, with singular term $f_{\infty} \sum_{q_{x} = 0} p_{x}$ .

[F3]

Finite stochastic kernels: $P K$ and $Q K$ are the output laws under the same row-stochastic kernel.

[F4]

Finite data processing for f-divergences: $D_{f} (P K ∥ Q K) \leq D_{f} (P ∥ Q)$ for every convex generator with its stated boundary convention.

[F5]

The finite Rényi generators are convex with stated boundary values: for $α > 1$ , $t^{α} - 1$ is convex with recession value $+ \infty$ ; for $0 < α < 1$ , $1 - t^{α}$ is convex with recession value $0$ .

Proof

1.1F1F2F3F5givenalgebra

Suppose $α > 1$ . If $P ≪̸ Q$ , [F1] gives $D_{α} (P ∥ Q) = + \infty$ , so the claimed inequality holds. If $P ≪ Q$ , then $P K ≪ Q K$ : whenever $(Q K)_{y} = 0$ , nonnegativity of the summands gives $q_{x} K (y ∣ x) = 0$ for every $x$ , and $p_{x} > 0$ implies $q_{x} > 0$ and hence $K (y ∣ x) = 0$ . For $f (t) = t^{α} - 1$ , convexity holds, $f_{\infty} = + \infty$ by [F5], and direct substitution into [F2] gives $D_{f} (P ∥ Q) = S_{α} (P, Q) - 1$ and the same identity for $P K, Q K$ .

1.2F1F2F3F5givenalgebra

Suppose $0 < α < 1$ and take $g (t) = 1 - t^{α}$ . By [F5] it is convex, $g (1) = 0$ , $g (0) = 1$ , and $g_{\infty} = 0$ . Substitution into [F2] gives $D_{g} (P ∥ Q) = 1 - S_{α} (P, Q)$ , including when $P$ has mass outside $supp Q$ ; likewise $D_{g} (P K ∥ Q K) = 1 - S_{α} (P K, Q K)$ .

2.1F1F4step 1.1algebra

By [F4], $S_{α} (P K, Q K) - 1 \leq S_{α} (P, Q) - 1$ . The logarithm is increasing and $α - 1 > 0$ , so dividing the logarithms by $α - 1$ preserves the inequality and proves the result for $α > 1$ .

3.1F1F4step 1.2algebra∎

By [F4], $S_{α} (P K, Q K) \geq S_{α} (P, Q)$ . If the input affinity is zero, [F1] gives $D_{α} (P ∥ Q) = + \infty$ and the conclusion follows. Otherwise both affinities are positive; applying the increasing logarithm and then dividing by $α - 1 < 0$ reverses the inequality. This proves the claim for $0 < α < 1$ .

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

The finite Rényi divergence limit is KL

Statement

For probability vectors $P, Q$ on a finite nonempty alphabet, $\lim_{α \to 1} D_{α} (P ∥ Q) = D (P ∥ Q)$ as a two-sided extended-real limit.

Facts & Assumptions

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

[F1]

Finite probability vectors: $P, Q$ have nonnegative coordinates summing to one, and $P ≪ Q$ means $p_{x} > 0$ only where $q_{x} > 0$ .

[F2]

Finite Kullback–Leibler divergence: $D (P ∥ Q)$ uses $p_{x} \log (p_{x} / q_{x})$ on positive $p_{x}$ , and equals $+ \infty$ if $P ≪̸ Q$ .

[F3]

Finite Rényi divergence: for $α \neq 1$ the affinity is $S_{α} (P, Q) = \sum_{q_{x} > 0} p_{x}^{α} q_{x}^{1 - α}$ , with the specified singular-support conventions.

[F4]

Real powers for positive bases, with the zero-base positive-exponent convention and Continuity and derivatives of positive-base real powers: for fixed $r > 0$ , $h \mapsto r^{h}$ is differentiable with derivative $r^{h} \log r$ .

[F5]

Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ : derivatives commute with finite sums.

[F6]

The chain rule, in one line from Carathéodory: if $g$ is differentiable at $c$ and $f$ is differentiable at $g (c)$ , then $f \circ g$ is differentiable at $c$ with $(f \circ g)^{'} (c) = f^{'} (g (c)) g^{'} (c)$ and The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: the derivative of $\log S (h)$ at $S (h) = 1$ is $S^{'} (h)$ .

Proof

1.1F1F2F3F4F5F6givenconstructalgebra

Suppose $P ≪ Q$ . On the finite set $supp P$ , every $p_{x}, q_{x}$ is positive. Put $r_{x} = p_{x} / q_{x}$ and define $S (h) : = \sum_{p_{x} > 0} p_{x} r_{x}^{h}$ for every real $h$ . Then $S (h) > 0$ , $S (0) = 1$ , and $S (h) = S_{1 + h} (P, Q)$ for $0 < ∣ h ∣ < 1$ by [F3]. By [F4] and [F5], $S^{'} (0) = \sum_{p_{x} > 0} p_{x} \log r_{x} = D (P ∥ Q)$ . The chain rule [F6] gives $(\log S)^{'} (0) = D (P ∥ Q)$ . Since $\log S (0) = 0$ , the definition of this derivative proves the two-sided limit.

1.2F1F3givenalgebra

Suppose $P ≪̸ Q$ . Let $s : = \sum_{x : q_{x} > 0} p_{x} < 1$ . For $0 < α < 1$ , the finite sum in [F3] tends to $s$ as $α ↑ 1$ , because each term with $q_{x} > 0$ tends to $p_{x}$ . If $s = 0$ , that sum is identically zero and $D_{α} = + \infty$ . If $s > 0$ , then $\log S_{α} \to \log s < 0$ while $α - 1 \to 0$ through negative values, so $D_{α} \to + \infty$ from below order one.

2.1F2F3step 1.2algebra∎

For every $α > 1$ , the positive $P$ -mass at a zero $Q$ -coordinate makes $S_{α} = + \infty$ , hence $D_{α} = + \infty$ by [F3]. Also $D (P ∥ Q) = + \infty$ by [F2]. The left and right limits therefore both equal the stated extended value.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passOpen item page →

KL is the iid type-II testing exponent

Statement

Let $P, Q$ be probability vectors on a finite nonempty alphabet $X$ . For $n \geq 1$ , write $P^{n}, Q^{n}$ for the product vectors on $X^{n}$ , with $P^{n} (x_{1}, \dots, x_{n}) = \prod_{i = 1}^{n} p_{x_{i}}$ and similarly for $Q^{n}$ . For every fixed $ϵ \in (0, 1)$ , with $β_{ϵ}$ oriented as in Finite type-II testing function with explicit orientation, $\lim_{n \to \infty} - \frac{1}{n} \log β_{ϵ} (P^{n}, Q^{n}) = D (P ∥ Q),$ where $- \log 0 : = + \infty$ .

Facts & Assumptions

Given: $P, Q$ as in the Statement and a fixed $ϵ \in (0, 1)$ .

[F1]

Finite probability vectors: $P, Q$ are probability vectors on the same finite alphabet.

[F2]

Finite Kullback–Leibler divergence: $D (P ∥ Q) = + \infty$ if $P ≪̸ Q$ .

[F3]

Finite type-II testing function with explicit orientation: $β_{ϵ} (P, Q)$ is the infimum alternative acceptance probability $E_{Q} [1 - ϕ]$ over randomized rejection functions $ϕ : X \to [0, 1]$ satisfying $E_{P} ϕ \leq ϵ$ .

[F4]

Finite iid log-likelihood averages concentrate: when $P ≪ Q$ , the empirical log-likelihood ratio $L_{n} / n$ converges in probability under $P^{n}$ to $D (P ∥ Q)$ , and on the support $Q^{n} = P^{n} \exp (- L_{n})$ .

Proof

1.1F1F2F3givenconstructalgebra

First suppose $P ≪̸ Q$ . The set $S : = {x : p_{x} > 0 = q_{x}}$ has $r : = P (S) > 0$ . For each $n$ , let $A_{n} \subseteq X^{n}$ be the event that at least one coordinate lies in $S$ , and define a test $ϕ_{n}$ to reject only on $A_{n}^{c}$ . Then $E_{P^{n}} ϕ_{n} = P^{n} (A_{n}^{c}) = (1 - r)^{n} \to 0$ , while $E_{Q^{n}} [1 - ϕ_{n}] = Q^{n} (A_{n}) = 0$ . For every fixed $ϵ > 0$ the test is feasible for all sufficiently large $n$ , so $β_{ϵ} (P^{n}, Q^{n}) = 0$ there and the exponent is $+ \infty = D (P ∥ Q)$ .

1.2F1F3F4givenconstructalgebra

Now suppose $P ≪ Q$ , put $D = D (P ∥ Q)$ , and fix $δ > 0$ . On $supp (P)^{n}$ write $L_{n} (x_{1}, \dots, x_{n}) = \sum_{i = 1}^{n} \log (p_{x_{i}} / q_{x_{i}})$ . Define $A_{n} = {x \in supp (P)^{n} : L_{n} (x) \geq n (D - δ)}$ and reject outside $A_{n}$ . By [F4], $P^{n} (A_{n}) \to 1$ , so this test has type-I error at most $ϵ$ for all sufficiently large $n$ . For each $x \in A_{n}$ , $Q^{n} (x) = P^{n} (x) e^{- L_{n} (x)} \leq P^{n} (x) \exp (- n (D - δ))$ ; summing gives $β_{ϵ} (P^{n}, Q^{n}) \leq Q^{n} (A_{n}) \leq \exp (- n (D - δ))$ .

2.1F1F3F4step 1.2givenalgebra

Let $ψ : X^{n} \to [0, 1]$ be the acceptance probability of any test feasible for $β_{ϵ} (P^{n}, Q^{n})$ , so $E_{P^{n}} ψ \geq 1 - ϵ$ . Set $B_{n} = {x \in supp (P)^{n} : L_{n} (x) \leq n (D + δ)}$ . By [F4], $P^{n} (B_{n}^{c}) \to 0$ . Since the $Q^{n}$ expectation includes all terms on $supp (P)^{n}$ , its nonnegative terms give $E_{Q^{n}} ψ \geq E_{P^{n}} [ψ e^{- L_{n}} 1_{B_{n}}] \geq \exp (- n (D + δ)) (1 - ϵ - P^{n} (B_{n}^{c}))$ . This holds for every feasible test, hence also for the infimum $β_{ϵ} (P^{n}, Q^{n})$ . For all sufficiently large $n$ the last factor is positive.

3.1step 1.1step 1.2step 2.1algebra∎

Steps 1.2 and 2.1 imply $D - δ \leq {lim inf}_{n} - \frac{1}{n} \log β_{ϵ} (P^{n}, Q^{n}) \leq {lim sup}_{n} - \frac{1}{n} \log β_{ϵ} (P^{n}, Q^{n}) \leq D + δ$ , because $- \frac{1}{n} \log (1 - ϵ - P^{n} (B_{n}^{c})) \to 0$ . Since $δ > 0$ was arbitrary, the limit equals $D$ . Together with step 1.1 this proves the extended-real statement.

5 · Examples, counterexamples and false statements

None yet.

F-Divergences, Rényi Information, and Hypothesis Testing

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Finite probability vectors

Definition

Boundary limits of a normalized finite convex generator exist

Statement

Facts & Assumptions

Proof

The finite KL generator has the required convex boundary extension

Statement

Facts & Assumptions

Proof

The finite Rényi generators are convex with stated boundary values

Statement

Facts & Assumptions

Proof

Finite f-divergence with support conventions

Definition

Finite type-II testing function with explicit orientation

Definition

Remarks

Finite stochastic kernels

Definition

Finite Kullback–Leibler divergence

Definition

The closed convex perspective is subadditive

Statement

Facts & Assumptions

Proof

Finite Rényi divergence

Definition

Finite iid log-likelihood averages concentrate

Statement

Facts & Assumptions

Proof

Finite data processing for f-divergences

Statement

Facts & Assumptions

Proof

Finite data processing for Kullback–Leibler divergence

Statement

Facts & Assumptions

Proof

Finite data processing for Rényi divergence

Statement

Facts & Assumptions

Proof

The finite Rényi divergence limit is KL

Statement

Facts & Assumptions

Proof

KL is the iid type-II testing exponent

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources