Compressors for words, network flow IDs, or click streams face two facts at once. The set of possible symbols has no fixed size: new words and new flows keep arriving. And each symbol depends on the ones before it. Information theory handles each fact separately. There are guarantees for unbounded alphabets when symbols are independent, and there are guarantees for sources with memory when the alphabet is small and fixed. There is no guarantee for sources that have both properties. Worst-case analysis also makes the combined problem look hopeless: even for independent symbols drawn from a power law whose ranking is unknown, the extra bits a universal code must pay in the worst case grow linearly in the sequence length. Yet everyday context-based compressors handle such data well.
We propose to explain that gap. We will prove a bound on expected redundancy, meaning the extra bits beyond the entropy averaged over a natural random source, rather than the worst case. The source class is first-order Markov chains over a countably infinite alphabet whose symbol frequencies and whose per-context next-symbol distributions both follow power laws. The key step replaces the Poisson trick used for independent sources with the classical "stack of cards" view of a Markov chain. Under that view, the chain becomes a set of independent samples, one sequence per context. Our heuristic calculation predicts that expected redundancy grows as $n^{\max(1/\alpha,1/\beta)}$ up to log factors. Here $\alpha$ is the power-law exponent of how often each symbol occurs, and $\beta$ is the power-law exponent of what follows a given symbol. We will build a sequential coder that attains this rate without knowing $\alpha$ or $\beta$. We will then test whether the prediction tracks measured code lengths on real heavy-tailed streams.
Core Claim
For independent sources, Universal Compression of Power-Law Distributions shows that unordered power-law envelope classes (families where the sorted probabilities are bounded by $c\,i^{-\alpha}$ but the ranking is unknown) have worst-case redundancy $\Omega(n)$ but expected redundancy $\Theta(n^{1/\alpha}\log k)$. The expected rate is driven by the number of distinct symbols observed. That proof rests on Poissonization, the device from Universal Compression of Envelope Classes: Tight Characterization via Poisson Sampling. Poissonization treats the sample size as random, which makes symbol counts independent. It fails once symbols depend on each other. That is why the file's gap analysis finds no counterpart for sources with memory.
Our claim is that the right replacement for independent counts under memory is independence across contexts. A Markov chain can be generated by giving each state its own pre-drawn sequence of next states and reading from it whenever that state is visited. Conditioned on how many times each context $c$ is visited, the redundancy therefore splits into per-context independent problems. Each can be handled with the envelope machinery that already exists. Let $N_c$ be the number of visits to context $c$ in a length-$n$ sequence. Let $R_\beta(m)$ be the expected redundancy of an unordered power-law row with exponent $\beta$ after $m$ samples. Let $R_{\text{new}}(n)$ be the cost of naming contexts at their first appearance. Our target bound is
$$ \bar R_n \;\lesssim\; \mathbb{E}\Big[\sum_{c} R_\beta(N_c)\Big] + R_{\text{new}}(n). $$
To see where the predicted rate comes from, plug in $N_c \approx n\,i_c^{-\alpha}$, where $i_c$ is the rank of context $c$, together with $R_\beta(m)\approx m^{1/\beta}$, which is the independent-source rate from the power-law paper. Summing over the roughly $n^{1/\alpha}$ contexts that are actually visited gives $n^{1/\alpha}$ when $\alpha<\beta$ and $n^{1/\beta}$ when $\alpha>\beta$. In words, the heavier of the two tails sets the rate.
This rate matches the growth of the number of distinct symbol pairs (bigrams) observed. That match suggests a quantity anyone can compute from a given sequence: $D_2(n)\log n$, the distinct-bigram count times $\log n$. It would predict a coder's excess code length, much as Instance-Specific Approximation Ratios for Correlation Clustering and Max-Cut gives data-dependent certificates that explain why heuristics beat worst-case bounds. Worst-case redundancy stays $\Omega(n)$, since the independent class sits inside ours. The content of the result is the average-case rate and its computable certificate.
Research Program
The theory has three parts. The first is the per-context reduction above, made rigorous. The main difficulty is that visit counts $N_c$ are random and correlated, and the contexts visited fewer than about once in $n$ steps are not negligible. We plan to charge those rare contexts to a shared "escape" distribution. Escape costs are then bounded by the pattern-coding regret of Minimax Regret on Patterns Using Kullback-Leibler Divergence Covering. A pattern replaces each symbol by the order of its first appearance, and that paper bounds the regret for coding patterns by $c\,n^{1/3}(\log n)^{4/3}$, with $c=38$ holding for every $n$. We reuse this as a method. That paper explicitly leaves the Markov extension open, and our construction addresses it only in the backoff role.
The second part is a lower bound. On a prior over transition rows built by randomly permuting power-law rows, we will show that $\mathbb{E}[D_2(n)]\log n$ redundancy is unavoidable. This would establish that the exponent $\max(1/\alpha,1/\beta)$ is tight.
The third part is adaptivity to unknown exponents. Universal Compression of Power-Law Distributions assumes $\alpha$ is known. We will estimate $\alpha$ and $\beta$ online from how fast distinct-symbol and distinct-bigram counts grow. We will then bound the extra cost of plug-in estimation.
The algorithm is a sequential arithmetic coder. Each context runs its own adaptive estimator with an escape probability derived from the unordered-envelope analysis, and escapes fall back to a single shared order-0 pattern coder. Its cost per symbol is constant up to hash-table lookups. That contrasts with the $2^{k+1}$-state trellis of An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources and the $n^{O(k^2+k\ell)}$ optimal predictors of Prediction from compression for models with infinite memory, with applications to hidden Markov and renewal processes. We avoid their hardness results by restricting to observable first-order memory rather than hidden states. We state this restriction openly as a limitation.
Baselines
The naive reference is an order-0 coder that ignores memory. It is the unordered-envelope coder implied by Universal Compression of Power-Law Distributions, with pattern coding for new symbols, given the same exponent-estimation procedure as our coder. Our method must beat it by roughly $n$ times the gap between the order-0 entropy and the order-1 conditional entropy. If it does not, the memory modeling is not paying for itself.
The strongest existing sequential method with memory in the file is DECO from Superior Guarantees for Sequential Prediction and Lossless Compression via Alphabet Decomposition. DECO splits a large-alphabet prediction problem into a tree of binary context-tree-weighting predictors and has provably better redundancy than multi-alphabet context tree weighting when the alphabet has 118 or more symbols. It is designed for a finite alphabet. We will therefore run it on a vocabulary truncated at top-$K$ plus an escape token, and sweep $K$ over the same grid we give our own coder's tuning. All methods will use the same token streams and a matched memory budget. No reported result was found on Lacuna for DECO's per-file bit rates on the Calgary Corpus; the paper reports only "best overall performance" on text. We will therefore rerun it rather than quote it. Beating it means lower total bits per token at a matched memory budget. We specifically expect the advantage to grow with $n$ on streams whose vocabulary keeps expanding.
For short blocks, Memory-Assisted Universal Compression of Network Flows reports that a 100-byte packet compresses to 87 bytes with standard compression and 31 bytes with 4MB of shared history. We will not compete with the 31-byte figure, because shared history is a different resource. Instead we will include a memory-assisted variant of our coder to show the two ideas combine.
Two ablations isolate the key ingredients. The first removes the shared escape distribution, so each context codes new symbols independently. This tests whether the rare-context charging drives the rate. The second fixes $\alpha$ and $\beta$ to oracle values versus estimating them online, which measures the cost of adaptivity.
Why not just…?
Why not just truncate to a top-$K$ vocabulary with an unknown-word token and run a standard context model? On a fixed corpus this can be competitive, and our DECO-with-truncation baseline tests exactly that. However, when new symbols keep arriving, the escape token has to encode the identities of all out-of-vocabulary symbols, and a fixed $K$ cannot match a growth rate that changes with $n$. Efficient Representation of Large-Alphabet Probability Distributions also shows how badly log-loss penalizes crude handling of small probabilities. At $K=10^5$ and 8 bits, uniform quantization loses 0.5 bits per entry, versus about $10^{-4}$ for its ArcSinh compander. The experiment that settles this plots excess bits against $n$ for each $K$. We predict every fixed-$K$ curve eventually bends above ours.
Why not just use escape-based context mixing heuristics that practitioners already run? This is a real threat to the algorithm, and we accept it. Our coder is in that family. The contribution is the rate, the lower bound, and the computable certificate that explain why such coders work despite $\Omega(n)$ worst-case redundancy. If a tuned heuristic matches our coder in code length, that supports the theory rather than undermining it. What the heuristic lacks is a prediction of how its excess grows, and we test that prediction directly.
Why not just prove worst-case minimax bounds for the Markov class? Because the answer is already known and uninformative. The independent unordered class is a subclass, so worst-case redundancy is at least $\Omega(n)$ by Universal Compression of Power-Law Distributions. This parallels why expected divergence in Scaling of model approximation errors and expected entropy distances stays at $1-\gamma\approx 0.4228$ while the worst case grows as $\log N$. We depart from that paper's uniform and Dirichlet priors, which it notes do not capture power-law structure.
Why not just assume the source is memoryless? The order-0 baseline measures that cost directly. Results such as Remote Channel Synthesis show that memoryless designs underperform on correlated streams in coordination tasks. Here the loss should appear as a linear-in-$n$ gap in code length.
Proposed Experiments
The first decisive check is on synthetic sources. We will generate Markov chains whose symbol frequencies follow a power law with exponent $\alpha$ and whose rows are randomly permuted power laws with exponent $\beta$, over a grid of $(\alpha,\beta)$ pairs. Because the true source is known, we can measure exact expected redundancy. We will then fit the log-log slope against $n$ from $10^3$ to $10^7$. The theory is falsified if the slopes do not follow $\max(1/\alpha,1/\beta)$, or if the kink does not appear at $\alpha=\beta$. Synthetic Zipf streams with independent symbols, as in the CounterSnake setup, serve as the $\beta\to$ order-0 control. On those, our coder should reduce to the independent-source rate.
The second check uses real streams. These are word-token streams from the Calgary Corpus, Moby Dick word tokens as in Efficient Representation of Large-Alphabet Probability Distributions, the Caida flow-ID and Kosarak click streams from CounterSnake, and a word-level slice of FineWeb for large $n$. On real data the true entropy is unknown. We will therefore measure each coder's code length minus a held-out order-1 cross-entropy reference, computed on a much larger disjoint sample. We will test whether this excess tracks $D_2(n)\log n$ across prefixes and datasets, reporting rank correlation and the fitted proportionality constant.
A positive result needs two things. The certificate must predict excess across datasets better than the order-0 distinct-count predictor. And our coder must beat truncated DECO at large $n$ on at least the open-vocabulary streams. A negative result on real data despite success on synthetic sources would tell us that first-order power-law memory is the wrong average-case model. That would itself be a useful answer to the open question of which average-case distributions realistically model structured data.
References
- Universal compression of power-law distributions.
- Universal Compression of Envelope Classes: Tight Characterization via Poisson Sampling.
- Instance-Specific Approximation Ratios for Correlation Clustering and Max-Cut
- Minimax Regret on Patterns Using Kullback-Leibler Divergence Covering
- An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources
- Prediction from compression for models with infinite memory, with applications to hidden Markov and renewal processes
- Superior Guarantees for Sequential Prediction and Lossless Compression via Alphabet Decomposition
- Memory-assisted universal compression of network flows
- Efficient Representation of Large-Alphabet Probability Distributions
- Scaling of model approximation errors and expected entropy distances
- Remote Channel Synthesis
- CounterSnake: A lossless and generalized compression framework for diverse sketches