The claim
Let X be uniform on {0, 1, 2, 3}, and let Y be binary with P(Y = 1 | x) = (0, 0, 1/8, 3/8). Over deterministic encoders T = f(X), maximize I(T; Y) − H(T)/β. Since T is a function of X, H(T) = I(X; T), so this is the information bottleneck restricted to partitions of X. Enumerating all fifteen partitions, with β stepped by 0.01:
| β | optimal partition | H(T) | I(T; Y) |
|---|---|---|---|
| < 6.91 | {0,1,2,3} | 0 | 0 |
| 6.91 – 9.26 | {0,1,2 | 3} | 0.811 | 0.1175 |
| 9.26 – 16.06 | {0,1 | 2,3} | 1.000 | 0.1379 |
| > 16.06 | {0,1 | 2 | 3} | 1.500 | 0.1691 |
The second and third optima are incomparable: neither is a function of the other. They also cross: {2} goes with {0, 1} in one and with {3} in the other. So no rooted tree on the four states has both as prunings. The reading reports that consecutive optima failed to nest for 8–36% of random joint distributions with four to six states. That was not re-run here.
What it does not say
- Nothing about stochastic encoders. The unrestricted information bottleneck at finite β generally has stochastic optima (THEORY-743). The reading’s heuristic search found no degrading channel between the stochastic optima of this example at β = 8, 10 and 12, but it certified neither global optimality nor uniqueness. That was settled the same day: with certified unique optima, the stochastic optima at β = 8 and 12 do not nest either (CLAIM-392).
- Nothing about rate–distortion with block coding. Equitz and Cover’s successive refinability is asymptotic. Their own Gaussian example shows single-shot quantizers failing to nest for a source that is refinable (NOTE-988).
- Not that hierarchies of categories cannot nest. Annealed category systems (THEORY-163) may well nest. This shows only that optimality at each budget does not guarantee it.