DefinitionDefinition: Literature-sourcedProof: Not applicablePipeline-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.

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.

Used by

Finite DMC information density Definition
Finite DMC with a nonnegative input cost and feasible budget Definition
Finite f-divergence with support conventions Definition
Finite Kullback–Leibler divergence Definition
Finite Rényi divergence Definition
Finite stochastic kernels Definition
Finite type-II testing function with explicit orientation Definition
Gallager, random-coding, expurgated, and sphere-packing functions Definition
One-letter Gallager and expurgated exponent functions Definition
Single-letter information capacity of a finite DMC Definition
A binary Neyman–Pearson boundary randomization Example
Binary f-, KL-, and Rényi divergences Example
Capacity of the binary erasure channel Example
Capacity of the binary symmetric channel Example
Disjoint supports and singular divergence values Example
An average-cost DMC block input has mutual information at most n C_I(Gamma) Lemma
Capacity-achieving output laws bound every row divergence Lemma
Constrained DMC information capacity is attained, nondecreasing, and concave Lemma
Finite DMC information capacity is attained Lemma
Finite iid log-likelihood averages concentrate Lemma
Finite Pinsker inequality in Euclidean norm Lemma
Gallager and expurgated input-law maxima are attained Lemma
IID DMC information density converges to mutual information Lemma
The n-letter mutual information of a DMC is at most nC Lemma
Uniform concentration around the capacity output divergence bound Lemma
Finite data processing for f-divergences Theorem
Finite data processing for Kullback–Leibler divergence Theorem
Finite data processing for Rényi divergence Theorem
Finite-DMC dependence-testing achievability bound Theorem
Finite-DMC hypothesis-testing meta-converse Theorem
KL is the iid type-II testing exponent Theorem
Random coding achieves every rate below finite DMC capacity Theorem
The finite Rényi divergence limit is KL Theorem

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Yury Polyanskiy and Yihong Wu, Information Theory: From Coding to Learning, Chapter 1, §1.2 (standard reference, not scraped)
Tim van Erven and Peter Harremoës, Rényi Divergence and Kullback-Leibler Divergence, §I-A (standard reference, not scraped)