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 discrete memoryless channels

Definition

A finite discrete memoryless channel (DMC) is the channel sequence Channel sequences with fixed finite nonempty input and output alphabets $X, Y$ (with every subset measurable) and one stochastic kernel $W (y ∣ x)$ from $X$ to $Y$ (Finite stochastic kernels). At every blocklength $n \geq 1$ its input and output alphabets are $X^{n}, Y^{n}$ . For a block word $a^{n} \in A^{n}$ , regarded as a function on ${0, \dots, n - 1}$ , use the one-based coordinate labels $a_{i} : = a^{n} (i - 1)$ for $1 \leq i \leq n$ . With these labels, its block kernel is $W^{n} (y^{n} ∣ x^{n}) : = \prod_{i = 1}^{n} W (y_{i} ∣ x_{i}) .$ Thus the same single-use transition law is applied independently at each coordinate, conditional on the input word. This page imposes no feedback or input-cost constraint.

Depends on

Used by

Small expected average code error need not control maximal error Counterexample
Strict asymptotic separation need not give zero finite-block error Counterexample
Average and maximal error of a fixed-length code Definition
Average-error and maximal-error DMC capacities Definition
Causal feedback codes for a finite cost-constrained DMC Definition
Finite discrete memoryless wiretap channel and code model Definition
Finite DMC information density Definition
Finite DMC with a nonnegative input cost and feasible budget Definition
Finite-alphabet point-to-point joint source-channel codes Definition
Fixed-length codes for a finite DMC Definition
Fixed-length finite DMC code with perfect causal output feedback 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 finite-alphabet source-channel rate budget Example
Capacity of the binary erasure channel Example
Capacity of the binary symmetric channel Example
Exact beta value for a one-use BSC meta-converse test Example
Exact evaluation of a one-use BSC dependence-testing bound 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
Finite DMC information capacity is attained Lemma
Finite DMC resolvability by random codebooks Lemma
Finite-channel mutual information is concave in the input law Lemma
Gallager and expurgated input-law maxima are attained Lemma
Globally optimized constant-composition and Gallager functions agree Lemma
IID DMC information density converges to mutual information Lemma
Information-density concentration for a fixed finite DMC input law Lemma
Strictly feasible DMC input laws achieve every lower mutual-information rate Lemma
The capacity-achieving output law is unique Lemma
The DMC product laws are stochastic kernels Lemma
The n-letter mutual information of a DMC is at most nC Lemma
Uniform concentration around the capacity output divergence bound Lemma
Average-cost capacity formula for a finite DMC Theorem
Finite-DMC dependence-testing achievability bound Theorem
Finite-DMC hypothesis-testing meta-converse Theorem
Gallager expurgated exponent lower bound Theorem
Gallager random-coding exponent lower bound Theorem
Lossless separation for finite IID sources and finite DMCs Theorem
Lossy separation for finite IID sources and finite DMCs Theorem

…and 7 more results.

Dependency tree · two levels

4 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 19 §19.1 (standard reference, not scraped)
Robert Gallager, Principles of Digital Communication I, Chapter 8 §8.7.1, MIT OpenCourseWare (standard reference, not scraped)