Reference normalizations of Effort-To-Compress across length, alphabet size, and composition

Abstract

Comparing finite symbolic complexity requires an explicit reference. Effort-To-Compress (ETC) counts the recursive pair substitutions needed to reduce a symbolic sequence to a constant. Its conventional normalization with L - 1 leaves systematic dependence on sequence length L and alphabet size k, confounding comparisons across datasets. We derive certified lower bounds for ETC and show that, for L [≥] k [≥] 2, the ceiling L - 1 is attainable if and only if L [≤] k2 + k + 1. For fixed k [≥] 2, the global ensemble mean and maximum ETC grow as {Theta}k(L/ logk L) as L [->] {infty}. These support two normalized ETC coordinates. Global-ensemble normalized ETC (nETC) maps a certified lower bound to zero and the uniform ensemble mean at the same L and k to one. Composition-conditioned normalized ETC (cETC) uses corresponding references restricted to the observed symbol composition. In Potts chains, nETC substantially reduced dependence on length and alphabet size. cETC further reduced differences associated with unequal symbol frequencies, while retaining sensitivity to temporal dependence. In human chromosome 22, the exploratory predictor nETC - cETC outperformed LZ76 in distinguishing CpG islands and long interspersed nuclear elements from genomic background with AUROC of 0.947 and 0.848. Matched references therefore enable interpretable comparisons of symbolic complexity across sequence lengths, alphabet sizes, and compositions.