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.
Lossless Wyner-Ziv endpoint is the Slepian-Wolf rate
Example
Let be any finite IID source pair, let , and use Hamming distortion . At , the Wyner-Ziv rate equals , the same conditional rate as one-encoder lossless compression with decoder side information .
Facts & Assumptions
Given: A finite IID pair , Hamming distortion, and target .
Finite-alphabet memoryless Wyner-Ziv theorem: the operational rate equals the minimum finite for with expected distortion at most zero.
Finite-IID k-source Slepian–Wolf rate region: for two finite IID sources, achievable lossless rates satisfy , , and , and these inequalities are sufficient.
Finite conditional entropy: conditional entropy is the finite weighted entropy of the conditional laws on positive-mass conditioning values.
Finite entropy and mutual-information chain rules: and for finite variables.
Finite distributions, entropy, divergence, and stochastic matrices: a point-mass probability vector has entropy zero under .
Finite fixed-length multiterminal lossless code: separate finite-length encoders send indices to a common decoder, and achievable rates allow vanishing block-error probability.
Verification
Any feasible test channel has nonnegative Hamming distortion with expectation zero, so almost surely. Every positive-mass conditional law of given is therefore a point mass; [F4] and [F7] give , and [F2] gives . The admissible choice , has zero distortion and the same objective, so the Wyner-Ziv minimum is exactly .
In the two-source Slepian-Wolf region of [F3], the subset requires . The rate pair satisfies the other two inequalities because follows from [F5] and the first identity in [F6], while is the second identity in [F6]. These are the operational rates of the fixed-length code convention in [F8], so the minimum X-encoder rate with the Y-encoder sending its lossless sequence is , matching step 1.1.
Depends on
- Finite conditional entropy
- Finite-alphabet IID multisource
- Finite distributions, entropy, divergence, and stochastic matrices
- Finite-alphabet lossy source coding with decoder-only side information
- Finite fixed-length multiterminal lossless code
- Single-letter and block distortion
- Finite-alphabet memoryless Wyner-Ziv theorem
- Finite conditional mutual information identities and equality
- Finite entropy and mutual-information chain rules
- Finite KL divergence is nonnegative with equality exactly at equal laws
- Finite-IID k-source Slepian–Wolf rate region
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
31 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
- Aaron D. Wyner and Jacob Ziv, The Rate-Distortion Function for Source Coding with Side Information at the Decoder (standard reference, not scraped)
- Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, second edition (standard reference, not scraped)