TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Fano’s packing bound with a reference-distribution KL bound

Statement

Assume AC. Let $M \geq 2$ be finite, let $P_{1}, \dots, P_{M}$ be sample laws on one measurable space, and let $t_{1}, \dots, t_{M}$ lie in a metric space $(T, ρ)$ with its Borel sigma-algebra. Suppose $ρ (t_{j}, t_{l}) \geq Δ > 0$ whenever $j \neq l$ . Let $J$ be uniform on $[M] = {1, \dots, M}$ , with conditional observation law $P_{j}$ given $J = j$ . For any probability reference law $Q$ , define $K_{Q} : = \frac{1}{M} \sum_{j = 1}^{M} D (P_{j} ∥ Q) \in [0, + \infty] .$ For every randomized estimator kernel from the observation to $T$ , with squared metric loss $ρ (a, t_{j})^{2}$ , its uniform average risk and its maximum risk are each at least $\frac{Δ^{2}}{4} (1 - \frac{K_{Q} + \log 2}{\log M}) .$ The minimax risk over all randomized estimators obeys this bound as well. When $K_{Q} = + \infty$ , the displayed lower bound is interpreted as $- \infty$ and is vacuous. Logarithms are natural.

Facts & Assumptions

Given: AC; a finite uniform hypothesis experiment, pairwise separated targets, a probability reference law $Q$ , and an arbitrary estimator kernel.

[A1]

The Axiom of Choice: AC supplies the Radon–Nikodym derivatives in the directional KL definition.

[F1]

Mutual information for a finite uniform hypothesis experiment: for the uniform index, $\overset{ˉ}{P} = M^{- 1} \sum_{j} P_{j}$ is a probability measure, $P_{j} ≪ \overset{ˉ}{P}$ , the densities $p_{j} = d P_{j} / d \overset{ˉ}{P}$ satisfy $0 \leq p_{j} / M \leq 1$ and $\sum_{j} p_{j} / M = 1$ almost everywhere, and $I (J; X) = M^{- 1} \sum_{j} D (P_{j} ∥ \overset{ˉ}{P})$ .

[F2]

Kullback–Leibler divergence, The Radon-Nikodym derivative as an almost-everywhere equivalence class, and Likelihood-ratio change of measure: when $P ≪ Q$ , $D (P ∥ Q) = \int (d P / d Q) \log (d P / d Q) d Q$ with $0 \log 0 = 0$ ; otherwise it is $+ \infty$ . The negative part of $u \log u$ is pointwise bounded by $1 / e$ , so its integral under any probability reference law is at most $1 / e$ . Densities can be integrated against their reference laws to recover the original measures.

[F3]

The natural logarithm as the inverse of the exponential function, The integral logarithm $L (x) : = \int_{1}^{x} \frac{d t}{t}$ for $x > 0$ , The integral logarithm $L$ is the published natural logarithm, Higher derivatives and the classes $C^{k}$ and $C^{\infty}$ , Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The integral logarithm satisfies $L^{'} (x) = 1 / x$ for $x > 0$ and $L (1) = 0$ , 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$ , 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)$ , 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)$ , and Jensen's integral inequality for a probability measure: $L = \log$ transfers $L^{'} (x) = 1 / x$ to $\log^{'} (x) = 1 / x$ ; products and compositions obey the derivative rules; and Jensen's inequality applies to an integrable convex transform. The function $ψ (u) = u \log u$ for $u > 0$ , extended by $ψ (0) = 0$ , is continuous at zero: for $s \geq 1$ , $0 \leq \log (s) / s \leq 2 / \sqrt{s}$ by $\log s = \int_{1}^{s} d u / u$ and $1 / u \leq 1 / \sqrt{u}$ . Since $ψ^{''} (u) = 1 / u > 0$ for $u > 0$ , the mean value theorem makes it convex on $(0, \infty)$ ; continuity extends convexity to $[0, \infty)$ .

[F4]

Probability measures and probability spaces and The cardinality $∣ A ∣$ of a finite set: finite probability vectors have entropy $H (q) = - \sum_{j} q_{j} \log q_{j}$ , with $0 \log 0 = 0$ .

[F5]

Randomized procedures as probability kernels: the estimator's action probabilities are measurable in the observation and form a probability measure for each observation.

[F6]

Loss functions and risk: a nonnegative loss with a measurable action section at each parameter has risk given by its iterated integral against the sample law and action kernel. Here each section $a \mapsto ρ (a, t_{j})^{2}$ is continuous, hence Borel measurable.

[F7]

Parameter-measurable statistical models as kernels and Bayes risk and minimax risk: give the finite parameter set $[M]$ its power-set sigma-algebra. The model $j \mapsto P_{j}$ is then a probability kernel. The squared metric loss is jointly measurable: the inverse image of any Borel set $B \subseteq [0, \infty]$ is the finite union $⋃_{j = 1}^{M} {j} \times {a : ρ (a, t_{j})^{2} \in B}$ . Thus the uniform average risk is a Bayes risk, and minimax risk is the infimum of maximum risk over procedures.

Proof

1.1A1F1F2F3F4givenalgebra

Since $\overset{ˉ}{P} \geq P_{j} / M$ , each $P_{j} ≪ \overset{ˉ}{P}$ . Choose densities $p_{j} = d P_{j} / d \overset{ˉ}{P}$ and set $π_{j} = p_{j} / M$ . Then $\sum_{j} π_{j} = 1$ $\overset{ˉ}{P}$ -almost everywhere and $0 \leq π_{j} \leq 1$ by [F1]. The mutual-information definition [F1] and KL formula [F2] give $I (J; X) = \int \sum_{j} π_{j} \log (M π_{j}) d \overset{ˉ}{P} = \log M - \int H (π (x)) \overset{ˉ}{P} (d x) .$ All terms are integrable because $u \log u$ is bounded on $[0, 1]$ and the sum is finite.

2.1F1F3F4F5step 1.1algebra

Let $L$ be any randomized decision in $[M]$ based on $X$ , with $q_{l} (x) = P (L = l ∣ X = x)$ given by its probability kernel. Put $w_{l} = \int q_{l} d \overset{ˉ}{P}$ . When $w_{l} > 0$ , the conditional probability vector of $J$ given $L = l$ has entries $η_{l j} = w_{l}^{- 1} \int q_{l} (x) π_{j} (x) \overset{ˉ}{P} (d x)$ . Apply Jensen to $u \mapsto u \log u$ for each coordinate under the probability measure $q_{l} d \overset{ˉ}{P} / w_{l}$ , sum over $j$ , and use $\sum_{j} π_{j} = \sum_{j} η_{l j} = 1$ . The result is $H (η_{l}) \geq w_{l}^{- 1} \int q_{l} (x) H (π (x)) \overset{ˉ}{P} (d x)$ . Multiplication by $w_{l}$ and summation over positive $w_{l}$ yields $H (J ∣ L) : = \sum_{l} w_{l} H (η_{l}) \geq \int H (π (x)) d \overset{ˉ}{P}$ ; zero-probability outputs contribute zero. Hence $\log M - H (J ∣ L) \leq I (J; X)$ by step 1.1.

2.2A1F1F2F3step 1.1algebra

If some $P_{j} ≪̸ Q$ , then $K_{Q} = + \infty$ and the bound is vacuous. Otherwise write $r_{j} = d P_{j} / d Q$ . If the positive part of $r_{j} \log r_{j}$ has infinite integral, then $D (P_{j} ∥ Q) = + \infty$ ; if it is finite, the negative part is finite by [F2] and Jensen [F3] for the convex function $u \log u$ gives $D (P_{j} ∥ Q) = \int r_{j} \log r_{j} d Q \geq 0$ . Thus every divergence is nonnegative; therefore $K_{Q} < \infty$ implies that every term is finite. Set $\overset{ˉ}{r} = M^{- 1} \sum_{j} r_{j} = d \overset{ˉ}{P} / d Q$ . On ${\overset{ˉ}{r} > 0}$ , $r_{j} = M \overset{ˉ}{r} π_{j}$ $Q$ -almost everywhere: by [F2], for every measurable $A$ , $P_{j} (A) = \int_{A} p_{j} d \overset{ˉ}{P} = \int_{A} p_{j} \overset{ˉ}{r} d Q$ , where $p_{j} = d P_{j} / d \overset{ˉ}{P} = M π_{j}$ from step 1.1; uniqueness of the density gives the identity. Hence $r_{j} \log (r_{j} / \overset{ˉ}{r}) = \overset{ˉ}{r} ψ (M π_{j})$ . This is integrable: $M π_{j} \in [0, M]$ , $∣ u \log u ∣ \leq 1 / e$ for $0 \leq u \leq 1$ by [F2], and $0 \leq u \log u \leq M \log M$ for $1 \leq u \leq M$ by monotonicity in [F3], while $\overset{ˉ}{r}$ has integral one. The identity $r_{j} \log r_{j} = r_{j} \log (r_{j} / \overset{ˉ}{r}) + r_{j} \log \overset{ˉ}{r}$ holds on ${\overset{ˉ}{r} > 0}$ ; on ${\overset{ˉ}{r} = 0}$ all $r_{j} = 0$ and every term is set to zero. Jensen and [F3] give $\overset{ˉ}{r} \log \overset{ˉ}{r} \leq M^{- 1} \sum_{j} r_{j} \log r_{j}$ , so its positive part is integrable; its negative part is bounded by [F2]. Integrating the identity and averaging therefore gives $K_{Q} = I (J; X) + D (\overset{ˉ}{P} ∥ Q) .$ Finally Jensen under the probability law $Q$ yields $D (\overset{ˉ}{P} ∥ Q) = \int \overset{ˉ}{r} \log \overset{ˉ}{r} d Q \geq (\int \overset{ˉ}{r} d Q) \log (\int \overset{ˉ}{r} d Q) = 0$ . Therefore $I (J; X) \leq K_{Q}$ .

3.1F3F4step 2.1step 2.2algebra

For the error event $E = {L \neq J}$ , $E$ is determined by $(J, L)$ , so $H (E, J ∣ L) = H (J ∣ L)$ . Expanding the finite conditional entropy sums and factoring $P (E = e, J = j ∣ L = l) = P (E = e ∣ L = l) P (J = j ∣ E = e, L = l)$ gives $H (J ∣ L) = H (E ∣ L) + H (J ∣ E, L) .$ For each conditional law, entropy on at most $N$ points is at most $\log N$ : if its probabilities are $s_{1}, \dots, s_{N}$ , Jensen for $u \log u$ gives $N^{- 1} \sum_{r} (N s_{r}) \log (N s_{r}) \geq 0$ , which rearranges to $- \sum_{r} s_{r} \log s_{r} \leq \log N$ . Thus $H (E ∣ L) \leq \log 2$ ; when $E = 0$ , $J = L$ has entropy zero, and when $E = 1$ , at most $M - 1$ indices remain, so $H (J ∣ E, L) \leq P (E = 1) \log (M - 1) \leq P (E = 1) \log M$ . Combining this with step 2.1 and $I (J; X) \leq K_{Q}$ from step 2.2 proves $P (L \neq J) \geq 1 - \frac{K_{Q} + \log 2}{\log M}$ when $K_{Q} < \infty$ ; for $K_{Q} = \infty$ the bound is vacuous.

4.1F5F6F7step 2.1step 3.1algebra∎

Given an estimator action $A \in T$ , choose $L$ to be the smallest index minimizing $ρ (A, t_{l})$ . This is a measurable finite-valued decision because each distance to a fixed target is continuous and ties are resolved by the fixed index order; composing the map with the estimator kernel gives the randomized decision kernel of step 2.1 by [F5]. If $L \neq J = j$ , nearest choice and the triangle inequality give $Δ \leq ρ (t_{j}, t_{L}) \leq ρ (t_{j}, A) + ρ (A, t_{L}) \leq 2 ρ (A, t_{j})$ , so squared loss is at least $Δ^{2} / 4$ on the error event. Step 3.1 therefore gives the average risk bound. The maximum risk is at least its uniform average; taking the infimum over procedures using [F6] and [F7] gives the minimax conclusion.

Depends on

Used by

Dependency tree · two levels

88 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

Philippe Rigollet and Jan-Christian Hütter, High-Dimensional Statistics: Lecture Notes, Chapter 4, §4.4, Theorem 4.10 (standard reference, not scraped)
John Duchi, Lecture Notes on Statistics and Information Theory, Chapter 8, §§8.4.1–8.4.4 and 8.7 (standard reference, not scraped)