ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

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.

A finite-alphabet source-channel rate budget

Example

Take an IID Bernoulli source with $P_{S} (1) = 1 / 4$ and a binary symmetric channel with crossover probability $1 / 4$ . Use five channel symbols per source symbol. Both the source entropy and the channel capacity are in nats; this example computes the strict asymptotic lossless separation margin exactly.

Facts & Assumptions

Given: A finite IID source, a finite DMC, and the formulas for finite mutual information and entropy.

[A1]

$S_{i}$ are IID Bernoulli $(1 / 4)$ , and $W$ is the BSC with input and output alphabets ${0, 1}$ and crossover probability $1 / 4$ .

[A2]

Write $h (q) : = - q \ln q - (1 - q) \ln (1 - q)$ for the entropy in nats of a Bernoulli $(q)$ variable, with $0 \ln 0 : = 0$ .

[F1]

Finite discrete memoryless channels: the BSC is a finite DMC; Single-letter information capacity of a finite DMC defines $C (W) = \sup_{P_{X}} I (X; Y)$ in nats per use.

[F2]

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

[F3]

Finite distributions, entropy, divergence, and stochastic matrices: the entropy of a binary probability vector $(q, 1 - q)$ is $- q \ln q - (1 - q) \ln (1 - q)$ , with $0 \ln 0 = 0$ .

[F4]

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

[F5]

Operational capacity formula for a finite DMC: the operational DMC capacity equals the single-letter information capacity $C (W)$ .

[F6]

Lossless separation for finite IID sources and finite DMCs: if source entropy in nats is strictly below $ρ C (W)$ , reliable transmission is achievable asymptotically.

Verification

1.1A1A2F2F3givenalgebra

For an input $X \sim Bern (r)$ , the BSC output is Bernoulli with parameter $q = 1 / 4 + r / 2$ , while $H (Y ∣ X) = h (1 / 4)$ . By [F2], [F3], and the notation in [A2], $I (X; Y) = h (q) - h (1 / 4)$ .

2.1A1A2F1F4F5step 1.1algebra

By [F4], $h (q) \leq \ln 2$ , with equality at $q = 1 / 2$ , which is attained by $r = 1 / 2$ . Hence [F5] gives $C (W) = \ln 2 - h (1 / 4) = \frac{3}{4} \ln 3 - \ln 2$ , with $C (W)$ interpreted as in [F1]. The source entropy is $H (P_{S}) = h (1 / 4) = 2 \ln 2 - \frac{3}{4} \ln 3$ .

3.1A1F6step 2.1algebra∎

At $ρ = 5$ , the gap is $5 C (W) - H (P_{S}) = \frac{9}{2} \ln 3 - 7 \ln 2 > 0$ , because $3^{9} = 19683 > 16384 = 2^{14}$ and the natural logarithm is increasing. Therefore the strict hypothesis of [F6] holds, so asymptotically reliable lossless transmission is achievable at this ratio.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

32 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, MIT OpenCourseWare 6.441 Information Theory, Chapter 20: Advanced Channel Coding and Source-Channel Separation (standard reference, not scraped)
Robert M. Gray, Entropy and Information Theory, author-hosted full text (standard reference, not scraped)