A Block Hierarchy for Rate-Distortion and Dispersion of Binary Markov Sources
Abstract
The finite-length rate penalty for compressing a binary Markov source under Hamming distortion remains open in general.
To study this penalty, we use memoryless sources that draw independent $K$-symbol blocks from the Markov law.
We determine the rate and tilted-information variance per symbol at every distortion for positively correlated two-symbol blocks of arbitrary stationary bias and for symmetric three- and four-symbol blocks.
For a symmetric chain with flip probability $0<p<1/2$, we prove that the normalized variance converges to a positive limit at every interior distortion where the Markov rate-distortion function is differentiable.
At positive distortions up to Gray's critical distortion, this limit equals the source varentropy rate and yields a second-order coding converse for a single Markov path.
We conjecture that the limit is the operational dispersion of the Markov source.
Matching achievability remains open.