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 distributions, entropy, divergence, and stochastic matrices

Definition

For a finite nonempty set identified with $[k] = {1, \dots, k}$ , a probability vector is $p = (p_{i})_{i = 1}^{k}$ with $p_{i} \geq 0$ and $\sum_{i} p_{i} = 1$ ; it is the outcome-weight vector of a finite probability space (Finite probability spaces, outcome weights, events, and event probabilities). Its Shannon entropy in natural units is $H (p) : = - \sum_{i = 1}^{k} p_{i} \ln p_{i},$ with $0 \ln 0 : = 0$ . For probability vectors $p, q$ on the same set $[k]$ , the relative entropy is $D (p ∥ q) : = \sum_{i : p_{i} > 0} p_{i} \ln (p_{i} / q_{i}),$ with value $+ \infty$ if $p_{i} > 0 = q_{i}$ for some $i$ . A matrix $A \in [0, 1]^{N \times m}$ is row-stochastic when each row sums to one. For a probability row vector $p$ on $[m]$ and a row vector $X \in [0, 1]^{m}$ , the dot product $p X^{T} = \sum_{i = 1}^{m} p_{i} X_{i}$ is the acceptance probability under distribution $p$ .

These definitions use finite sets only; entropy is between $0$ and $\ln k$ , as proved where needed below.

Depends on

Finite probability spaces, outcome weights, events, and event probabilities

Used by

Fano bound for erasure and out-of-alphabet estimates Corollary
A balanced binary type class is not exactly exponential in entropy Counterexample
Finite KL divergence is directional and may be infinite Counterexample
Strict asymptotic separation need not give zero finite-block error Counterexample
Base-two entropy of a finite source Definition
Deterministic fixed-length binary block code and block error Definition
Deterministic Gács–Körner common part and Wyner common information Definition
Empirical types, n-types, and type classes Definition
Finite conditional entropy Definition
Finite conditional mutual information Definition
Finite discrete sources and product blocks Definition
Finite mutual information Definition
Finite product mass on words Definition
Finite strongly typical sets with support restriction Definition
Finite-alphabet conditional entropy given an observation Definition
Finite-alphabet IID multisource Definition
Finite-alphabet IID source Definition
Finite-block information and entropy in bits Definition
Information density and typical sets for a finite source Definition
Jointly typical blocks for a finite IID multisource Definition
Self-information and surprisal variance for a finite law Definition
Zero-cost information capacity of a countable-input finite-output DMC Definition
A degraded binary erasure wiretap channel Example
A finite Bernoulli large-deviation tail Example
A finite deterministic copy has mutual information equal to entropy Example
A finite information-bottleneck privacy model Example
A finite-alphabet source-channel rate budget Example
A perfectly dependent Bernoulli source has zero block information rate Example
Berger-Tung inner bound contains the Slepian-Wolf region Example
Bernoulli information density and exact typical-set counts Example
Binary entropy and its extremizers Example
Binary symmetric source: Slepian–Wolf corners and common part Example
Binary type classes at length ten Example
Capacity of the binary erasure channel Example
Capacity of the binary symmetric channel Example
Changing a conditional kernel on a null fiber leaves information unchanged Example
Coarsening the conditioning variable can increase conditional mutual information Example
Cost-constrained capacity of a binary identity channel with feedback Example
Independent and deterministic finite information Example
Lossless Wyner-Ziv endpoint is the Slepian-Wolf rate Example

…and 51 more results.

Dependency tree · two levels

5 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

Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)
John Watrous, The Theory of Quantum Information (standard reference, not scraped)