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.
Strict asymptotic separation need not give zero finite-block error
Statement refuted
For every finite IID source and finite DMC, if , then every finite blocklength ratio admits a deterministic joint code with zero block error.
Facts & Assumptions
Given: A uniform binary IID source, a BSC with crossover probability , channel blocklength , and a deterministic joint code as in Finite-alphabet point-to-point joint source-channel codes.
Every word has source probability .
In this verification, and , with .
Finite discrete memoryless channels: for the BSC with crossover probability , each coordinate transition probability is either or , so every output word has positive probability under every input word.
Finite distributions, entropy, divergence, and stochastic matrices and Finite KL divergence is nonnegative with equality exactly at equal laws: for binary , , with equality at .
Lossless separation for finite IID sources and finite DMCs: a strict entropy-capacity gap ensures reliable transmission by a sequence of codes, asymptotically.
Counterexample
The source entropy is . For a BSC with crossover and input , the output parameter is , and [F3] gives . By [F4], the maximum is at , so .
Fix any , any deterministic encoder , and decoder . Choose any output word and then a source word , which exists because . By [A1] and [F1], . On this event the decoder is wrong, so the block-error probability is positive for every finite code.
Hence , since . The asymptotic threshold is strict, so [F5] gives a reliable code sequence at ratio six.
The strict asymptotic threshold in step 2.1 therefore cannot imply a zero-error code at each finite blocklength ratio. This refutes the statement while leaving the asymptotic separation conclusion intact.
Depends on
- Finite-alphabet point-to-point joint source-channel codes
- Lossless separation for finite IID sources and finite DMCs
- Finite discrete memoryless channels
- Single-letter information capacity of a finite DMC
- Operational capacity formula for a finite DMC
- Finite entropy and mutual-information chain rules
- Finite conditional entropy
- Finite mutual information
- Finite distributions, entropy, divergence, and stochastic matrices
- Finite KL divergence is nonnegative with equality exactly at equal laws
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
33 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)