🔢 mathematics

Pareto-type finite-block optimality for source codes: a constrained Markov example

This paper demonstrates that the reversible Dalai-Leonardi code for a specific four-symbol constrained Markov source is not Pareto-optimal regarding finite-block average length, as a newly constructed canonical injective code achieves a strictly lower expected block length for all block sizes $n \ge 2$ .

Original authors: Stefano Della Fiore

Published 2026-05-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Stefano Della Fiore

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a post office, but with a very specific rule: you can only send letters that follow a certain pattern. Maybe your town only allows letters that start with "A" or "B" and have specific rules about what letter can follow them. This is what the paper calls a "constrained source."

In the world of data compression (sending information efficiently), the goal is usually to turn these letters into the shortest possible strings of 0s and 1s (binary code).

The Old Way vs. The New Idea

For a long time, scientists had a standard way to measure how good a code was. They looked at the average length of the code for a huge number of letters. If you sent 1,000 letters, they would check the average size. If the average was low, the code was considered "good."

However, this paper asks a different, more nuanced question: What if we look at every single step?

Imagine two delivery drivers, Driver D (the old, established driver) and Driver S (the new, experimental driver).

Driver D has a route that takes exactly 1.5 minutes per letter on average.
Driver S is trying to be smarter.

The paper asks: Is Driver D the absolute best we can do? Or is there a Driver S who is never slower than Driver D, but is faster at some specific points?

In math terms, this is called Pareto optimality. If Driver S is never slower and sometimes faster, Driver D is no longer the "best" choice.

The Experiment: A Four-Letter Town

The author, Stefano Della Fiore, sets up a test case using a "town" with four letters: A, B, C, and D.

The Rules:
- If you have an A, the next letter must be A or C.
- If you have a B, the next letter must be B or D.
- If you have a C or D, the next letter can be anything (A, B, C, or D).

This creates a specific set of "allowed" words. The author takes a famous code created by Dalai and Leonardi (let's call it the Dalai-Leonardi Code) which was known to be very efficient for this town. It took exactly 1.5 bits (a unit of information) per letter on average.

The New Strategy: "Shortlex" Ordering

The author creates a new code, let's call it the Shortlex Code. Here is how it works, using a simple analogy:

Imagine you have a giant list of all the allowed words in this town. You want to assign them unique binary codes (like 0, 1, 00, 01, 10, etc.).

Sort by "Cost": First, you sort the words by how "surprising" they are. A word that is very common gets a low cost; a rare word gets a high cost.
Sort by Length: If two words have the same cost, you put the shorter one first.
Sort by Alphabet: If they are still tied, you put them in alphabetical order.
Assign Codes: You then hand out the binary codes in order: the first word gets "0", the second gets "1", the third gets "00", and so on.

This is the Shortlex Code. It's a very logical, "canonical" way to do things.

The Big Discovery

The author runs the numbers and finds something surprising:

For a single letter (n=1): The new code is exactly as good as the old one. They tie.
For two or more letters (n≥2): The new code is strictly better. It saves space.

The paper proves that for any block of letters larger than one, the new code is always shorter on average than the famous Dalai-Leonardi code.

The "One-Bit" Magic

Why does this happen? The paper uses some heavy math to explain, but the core idea is a "gap" in the system.

Think of the binary codes as seats in a theater.

The old code (Dalai-Leonardi) fills the seats in a way that leaves a few empty seats that could have been used to save space, but it didn't know how to use them efficiently for small groups.
The new code (Shortlex) is like a smart usher who realizes that for every group of words with a certain "cost," exactly half of them can be squeezed into a slightly smaller seat (saving 1 bit), and the other half take the normal seat.

Because the new code is smart enough to grab that "smaller seat" for at least half the time (and actually more than half the time for groups of 2 or more), it saves a tiny bit of space every single time.

The Result: A Tiny but Real Win

The paper calculates exactly how much space is saved.

The old code takes $1.5 \times n$ bits for $n$ letters.
The new code takes slightly less: $1.5 \times n$ minus a tiny fraction that gets smaller as $n$ gets bigger (specifically, it saves about $1/\sqrt{n}$ bits).

The Conclusion:
The famous Dalai-Leonardi code, which was thought to be a gold standard for this specific type of constrained source, is not the absolute best possible. The new "Shortlex" code beats it at every step after the very first one.

Why This Matters (According to the Paper)

The paper doesn't claim this will fix your Wi-Fi or compress your photos tomorrow. Instead, it makes a theoretical point:

In the world of data compression, we often look at "average" performance over the long run.
This paper shows that if you look at every single step (finite-block optimality), you can find codes that are strictly better than the ones we thought were optimal.
It proves that for constrained sources (where data follows specific rules), there is a hidden "Pareto" advantage to be found by looking at the details of how we order our codes.

In short: The old champion wasn't actually unbeatable; a new challenger found a way to be faster at every single race, except the very first one.

Technical Summary: Pareto-type Finite-Block Optimality for Source Codes

Problem Statement
This paper investigates the notion of finite-block optimality for injective source codes under source constraints. While classical source coding theory (e.g., Shannon, Kraft, McMillan) focuses on asymptotic entropy bounds and source-independent unique decodability, this work addresses the scenario where the source generates a constrained language (a subset of all possible strings). In such settings, a code need only be uniquely decodable on the set of admissible strings generated by the source, rather than on all possible binary concatenations.

The central question is whether a given reversible (injective) code is Pareto-optimal with respect to the sequence of expected block lengths. Specifically, given two injective codes $C$ and $\tilde{C}$ for the same constrained source, does one dominate the other such that $E[|C(X_1^n)|] \le E[|\tilde{C}(X_1^n)|]$ for all block lengths $n \ge 1$ , with strict inequality for at least one $n$ ? The paper uses the four-symbol constrained Markov source introduced by Dalai and Leonardi as a test case. Their existing reversible code achieves an expected length of exactly $3n/2$ for block length $n$ , while the block entropy is $3n/2 + 1/2$ . The authors ask if this benchmark is Pareto-optimal or if a superior injective code exists.

Methodology
The authors construct a canonical injective binary mapping $C: \mathcal{A} \to \{0, 1\}^+$ on the set of admissible strings $\mathcal{A}$ . The construction proceeds as follows:

Ordering: Admissible strings are ordered by increasing information cost $K(u) = -\log_2 P(X_1^m = u)$ , followed by string length, and finally lexicographic order.
Assignment: Strings are mapped to nonempty binary strings in shortlex order (ordered first by length, then lexicographically).

The analysis relies on a combinatorial enumeration of admissible strings by information cost. Key structural properties of the specific Markov source are utilized:

Dyadic Probabilities: All admissible block probabilities are powers of 2, making the information cost $K(u)$ an integer.
Cost Recurrence: The number of admissible strings $S_k$ with cost $k$ satisfies a linear recurrence $S_k = S_{k-1} + 2S_{k-2}$ .
Shortlex Gap Identity: A critical combinatorial identity is proven showing that for any cost class $k$ , the number of admissible strings with cost $< k$ leaves exactly half of the available binary strings of length $k-1$ unused. Consequently, within any cost class $k$ , exactly half of the strings receive a code length of $k-1$ and half receive length $k$ .

The probabilistic analysis treats the information cost of a block of length $n$ as a random variable $K_n$ derived from a binomial statistic. The authors define a "saving indicator" $I_n$ which is 1 if the code length is $K_n - 1$ and 0 otherwise. The expected length is expressed as $E[|C(X_1^n)|] = E[K_n] - P(I_n = 1)$ .

Key Contributions and Results

Uniform Improvement: The paper proves that for the Dalai–Leonardi source, the canonical code $C$ satisfies:
$E[|C(X_1^n)|] \le \frac{3}{2}n$
for all $n \ge 1$ , with equality holding only at $n=1$ . For all $n \ge 2$ , the inequality is strict. This demonstrates that the Dalai–Leonardi code is not Pareto-optimal; the proposed canonical code never performs worse and performs strictly better for every block length $n \ge 2$ .
Asymptotic Gain: The authors derive a quantitative asymptotic bound on the improvement. For any fixed constant $c < \frac{\sqrt{2}}{18\sqrt{\pi}}$ , there exists an $n_0$ such that for all $n \ge n_0$ :
$E[|C(X_1^n)|] \le \frac{3}{2}n - \frac{c}{\sqrt{n}}$
This establishes a finite-block gain of order $O(n^{-1/2})$ over the Dalai–Leonardi benchmark.
Probabilistic Mechanism: The proof establishes that the probability of achieving the shorter code length ( $K_n - 1$ ) is strictly greater than $1/2$ for all $n \ge 2$ . Specifically, $P(I_n = 1) \ge 1/2$ , with strict inequality for $n \ge 2$ . This "one-bit saving" occurs with probability at least $1/2$ at every block length, driven by the specific distribution of admissible strings across cost classes and the shortlex ordering.

Significance
The paper claims to provide a concrete, fully analyzable example demonstrating that source constraints can create finite-block gains that are invisible if one relies solely on entropy or source-independent unique decodability. By shifting the baseline requirement from "source-independent unique decodability" to "injectivity on the admissible language," the work reveals that reversible constructions can be refined to achieve Pareto improvements in finite-block average length. The example is described as simple yet sufficient to exhibit the natural finite-block Pareto comparison required for injective source coding under constraints. The results suggest that the standard reversible codes for constrained sources may not be optimal in a finite-block sense, even when they appear optimal in terms of entropy.