nucleation

LIT-1238: Successive refinement of information

1 min read

Properties6
StatusActive — read 2026-10-20 (NOTE-988) in full; worth reading for the exact condition under which optimal descriptions at two distortions are compatible, a Markov chain X → X̂₂ → X̂₁ between some pair of optimal test channels (THEORY-751), and for Gerrish's three-letter source, where the finer optimum drops a reproduction letter the coarser one uses and refinement fails. Read it knowing that Theorem 2 is proved for finite alphabets only and rests on cited multiple-descriptions theorems, that the condition is about stochastic test channels for long blocks and not about nesting of partitions (its own Fig. 1 shows single-shot Gaussian quantizers failing to nest), that the region conditions in (34)/(36) are printed reversed and (37) is misprinted, and that the remark after Theorem 3 holds only for p < √2 − 1.
Version3
Tagsinformation-theory
SupportsCLAIM-387 — Optimal deterministic information-bottleneck partitions at two budgets need not be nested: with X uniform on four states and binary Y with P(Y=1|x) = (0, 0, 1/8, 3/8), the optimum is {0,1,2 | 3} for 6.91 < β < 9.26 and {0,1 | 2,3} for 9.26 < β < 16.06, two partitions neither of which refines the other
Cited as “paper” byNOTE-988 — Equitz and Cover — Successive refinement of information
Cited as “source” byTHEORY-751 — For a memoryless source with finite alphabets and a per-letter distortion, a description at rate R(D₁) can be refined to distortion D₂ < D₁ at total rate R(D₂) iff some pair of rate–distortion-optimal test channels forms a Markov chain X → X̂₂ → X̂₁; the condition holds for every discrete source under Hamming distortion and fails for some three-letter sources under absolute error

Graph View

Equitz, W. H. R. & Cover, T. M. (1991). Successive refinement of information. IEEE Transactions on Information Theory 37(2): 269–275. doi:10.1109/18.75242.

Read in full in NOTE-988. The finite-alphabet characterization and the examples are filed as THEORY-751.

Why this is here

A2’s highest-priority bridge: when optimal compressed representations at different budgets nest, rather than reorganize into incompatible solutions. It is the classical answer for rate–distortion, which QUESTION-220 asks to carry to the information bottleneck.

Backlinks