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.

Discrete Memoryless Channel Capacity — Examples

1 · Prerequisites

2 · Summary

These calculations apply the finite-DMC capacity formula to binary symmetric and binary erasure channels. They use natural logarithms and include the deterministic, fully erased, and fully noisy endpoints.

Average and maximal error can differ for a finite code. For one use of the BEC with erasure probability $ϵ$ , send messages $1, 2$ as $0, 1$ and decode $0, 1, ⋆$ as $1, 2, 1$ , respectively, where $⋆$ denotes erasure. The two message error probabilities are $0$ and $ϵ$ , so the uniform-message average error is $ϵ / 2$ while the maximal error is $ϵ$ (Average and maximal error of a fixed-length code, Capacity of the binary erasure channel). In general, average error is at most maximal error; the expurgation lemma retains at least half the messages with maximal error at most twice the original average error (Expurgation converts small average error to small maximal error). These finite-code criteria nevertheless give the same asymptotic capacity: the A-page theorem proves $C_{a v} (W) = C_{\max} (W) = C (W)$ for every finite DMC without a cost constraint (Operational capacity formula for a finite DMC).

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Capacity of the binary symmetric channel

Example

The binary symmetric channel has input and output alphabets ${0, 1}$ ; independently at each use, the output is the input bit flipped with probability $p \in [0, 1]$ . Write $h (p) : = - p \ln p - (1 - p) \ln (1 - p), 0 \ln 0 : = 0.$ The channel capacity is $\ln 2 - h (p)$ nats per use, attained by a uniform input.

Facts & Assumptions

Given: The binary symmetric channel with crossover probability $p \in [0, 1]$ .

[F1]

Finite discrete memoryless channels: the row $W (\cdot ∣ x)$ assigns probability $1 - p$ to $x$ and $p$ to $1 - x$ .

[F2]

Operational capacity formula for a finite DMC: capacity is the maximum of finite mutual information over input laws.

[F3]

Finite entropy and mutual-information chain rules: $I (X; Y) = H (Y) - H (Y ∣ X)$ .

[F4]

Finite conditional entropy and Finite distributions, entropy, divergence, and stochastic matrices: conditional entropy is the finite weighted average of conditional pmf entropies, with $0 \ln 0 = 0$ .

[F5]

Finite KL divergence is nonnegative with equality exactly at equal laws: for a binary law $Q = Bern (q)$ , $D (Q ∥ Bern (1 / 2)) = \ln 2 - h (q) \geq 0$ , with equality exactly when $q = 1 / 2$ .

Verification

Given: An input bit $X$ with $P (X = 1) = r \in [0, 1]$ and the specified channel.

1.1F1F3F4givenalgebra

The output law is Bernoulli with parameter $q = p + r (1 - 2 p)$ . Each row has entropy $h (p)$ , so [F3] and [F4] give $I (X; Y) = h (q) - h (p)$ .

2.1F2F5step 1.1algebracases∎

By [F5], $0 \leq D (Bern (q) ∥ Bern (1 / 2)) = \ln 2 - h (q)$ , so $I (X; Y) \leq \ln 2 - h (p)$ . Taking $r = 1 / 2$ gives $q = 1 / 2$ and equality. Therefore [F2] gives capacity $\ln 2 - h (p)$ . If $p = 0$ or $p = 1$ , $h (p) = 0$ and the channel is a deterministic bijection; if $p = 1 / 2$ , every row is the same and the capacity is zero.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Capacity of the binary erasure channel

Example

The binary erasure channel outputs the input bit with probability $1 - ϵ$ and the erasure symbol $e$ with probability $ϵ$ , independently at each use. For $ϵ \in [0, 1]$ , its capacity is $(1 - ϵ) \ln 2$ nats per use, attained by a uniform input.

Facts & Assumptions

Given: A binary erasure channel with erasure probability $ϵ \in [0, 1]$ and input law $P (X = 1) = r$ .

[F1]

Finite discrete memoryless channels: conditional on $X = x$ , the output is $x$ with probability $1 - ϵ$ and $e$ with probability $ϵ$ .

[F2]

Operational capacity formula for a finite DMC: capacity is the maximum of finite mutual information over input laws.

[F3]

Finite entropy and mutual-information chain rules: $I (X; Y) = H (X) - H (X ∣ Y)$ .

[F4]

Finite conditional entropy and Finite distributions, entropy, divergence, and stochastic matrices: conditional entropy averages the entropy of each positive-mass conditional law; zero coordinates contribute $0 \ln 0 = 0$ .

[F5]

Finite KL divergence is nonnegative with equality exactly at equal laws: for a binary law $Bern (r)$ , $D (Bern (r) ∥ Bern (1 / 2)) = \ln 2 - h (r) \geq 0$ , with equality at $r = 1 / 2$ .

Verification

Given: $X \sim Bern (r)$ and the independent erasure mechanism.

1.1F1F3F4givencases

On the events $Y = 0$ and $Y = 1$ , $X$ is known exactly. The erasure indicator is independent of $X$ because [F1] gives the same conditional erasure probability $ϵ$ for both input symbols. Hence on $Y = e$ the conditional law of $X$ remains $Bern (r)$ . By [F4], $H (X ∣ Y) = ϵ h (r)$ , and [F3] gives $I (X; Y) = (1 - ϵ) h (r)$ .

2.1F2F5step 1.1algebracases∎

By [F5], $h (r) \leq \ln 2$ , with equality at $r = 1 / 2$ . Therefore the maximum mutual information is $(1 - ϵ) \ln 2$ by [F2]. At $ϵ = 0$ the channel is noiseless and has capacity $\ln 2$ ; at $ϵ = 1$ its output is constant and the capacity is $0$ .

Discrete Memoryless Channel Capacity — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Capacity of the binary symmetric channel

Example

Facts & Assumptions

Verification

Capacity of the binary erasure channel

Example

Facts & Assumptions

Verification

Sources