pith. sign in

arxiv: 2604.17443 · v1 · submitted 2026-04-19 · 💻 cs.IT · math.IT

About Optimal Prefix Codes over Countably Infinite Alphabets: Probabilistic Intervals for the Codeword Lengths Assignment

Hongyang Liu , Wei Yan This is my paper

Pith reviewed 2026-05-10 05:40 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords optimal prefix codescountably infinite alphabetcodeword lengthsprobability intervalsKraft inequalityanti-uniform sourcesdiscrete memoryless sources
0
0 comments X

The pith

For any k, an interval for the largest probability p1 forces the optimal prefix code to assign length exactly k to that symbol.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that over countably infinite alphabets the optimal code length for the most probable symbol is fixed once its probability p1 enters one of a sequence of specific intervals, one interval for each possible length k. This holds for binary prefix codes satisfying the Kraft inequality when probabilities decrease monotonically and sum to one. The result lets designers determine the best length for the first symbol from only a range on p1 rather than the full distribution. It also supplies a simpler test, needing less information than prior work on anti-uniform sources, to decide whether a given distribution has optimal lengths exactly equal to the index i for every symbol i.

Core claim

For any positive integer k, there exists a corresponding probability interval such that if the largest symbol probability p1 falls in this interval, the optimal code length for the symbol equals k. Furthermore, for infinite sources, we provide a criterion to determine probability distributions whose optimal code length assignment follows the pattern l_best_i = i, for i >= 1. Compared with the existing conclusion for anti-uniform sources, the proposed criterion requires less information for verification.

What carries the argument

The sequence of probability intervals for p1 that map to each optimal length k, obtained by enforcing the Kraft inequality on the remaining probabilities.

If this is right

  • Knowing only which interval contains p1 determines the optimal length for the largest-probability symbol.
  • Distributions exist for which the optimal lengths are exactly the natural numbers in order, and these can be recognized with a simpler check than earlier anti-uniform criteria.
  • The intervals separate the possible values of p1 into regions each tied to a unique optimal length for the first symbol.
  • Optimal coding decisions for the first symbol become local to a range on its probability alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The stepwise interval structure may let adaptive coders switch lengths for the most common symbol as its estimated probability drifts across boundaries.
  • Similar interval arguments could be applied to the lengths of the second or third most probable symbols once the first length is fixed.
  • The criterion for consecutive lengths might extend to sources whose probabilities decay at specific rates, such as geometric or Zipf-like tails.

Load-bearing premise

Symbol probabilities are monotonically non-increasing and sum to one.

What would settle it

A concrete non-increasing probability distribution with p1 inside the interval claimed for length k, yet whose shortest expected-length prefix code uses a different length for the first symbol.

Figures

Figures reproduced from arXiv: 2604.17443 by Hongyang Liu, Wei Yan.

Figure 1
Figure 1. Figure 1: The change of probability distribution during the first [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The change of probability distribution during the last [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Counterexample 2 the corresponding coding tree is as shown in the [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Counterexample 3 the corresponding coding tree is as shown in the [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
read the original abstract

For the discrete memoryless sources with a countably infinite alphabet, we prove that for any positive integer $k$, there exists a corresponding probability interval such that if the largest symbol probability $p_{1}$ falls in this interval, the optimal code length for the symbol equals $k$. Furthermore, for infinite sources, we provide a criterion to determine probability distributions whose optimal code length assignment follows the pattern $l^{best}_{i}=i$, for $i\ge 1$. Compared with the existing conclusion for anti-uniform sources, the proposed criterion requires less information for verification.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for any positive integer k there exists a non-empty interval for the largest symbol probability p1 (with the remaining probabilities renormalized to sum to 1 while preserving monotonicity) such that the optimal binary prefix code assigns length exactly k to the first symbol. It further supplies a necessary-and-sufficient criterion, expressed via a finite set of inequalities derived from the Kraft inequality and the optimality conditions, that identifies all monotonically non-increasing distributions for which the optimal lengths are exactly l_i = i for every i ≥ 1; the criterion is claimed to require strictly less information than the existing characterization for anti-uniform sources.

Significance. If the derivations are correct, the work supplies concrete, verifiable intervals and a simplified test for a canonical length assignment in the countable-alphabet setting. These results rest on standard extensions of the Kraft inequality and the usual necessary-and-sufficient optimality conditions for prefix codes; they therefore constitute a modest but useful addition to the literature on infinite-alphabet coding, offering practical tools that avoid exhaustive knowledge of the entire probability vector.

minor comments (2)
  1. [Theorem 1] In the statement of the interval-existence result, the precise dependence of the interval endpoints on the tail probabilities should be made explicit (e.g., by writing the lower and upper bounds as functions of the renormalized tail sum).
  2. [Section 4] The comparison paragraph that asserts the new criterion “requires less information” would benefit from a one-sentence reminder of the information demanded by the anti-uniform-source test (e.g., the full sequence of cumulative sums).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation to accept the manuscript. The referee's summary accurately captures the main contributions regarding probability intervals for optimal code lengths and the low-information criterion for the length assignment l_i = i.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained from standard inequalities

full rationale

The paper proves existence of probability intervals for optimal code lengths and a criterion for the length pattern l_i = i using direct extensions of the Kraft inequality, monotonicity of probabilities, and necessary/sufficient optimality conditions. These steps rely on continuity arguments over renormalized tails and inequality verification, without fitted parameters, self-definitional reductions, or load-bearing self-citations. Comparisons to anti-uniform source results reference external prior literature rather than the authors' own unverified claims. The derivation chain remains independent of its target conclusions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on standard coding-theory assumptions rather than new free parameters or invented entities.

axioms (2)
  • domain assumption Probabilities are positive, sum to 1, and satisfy p1 >= p2 >= p3 >= ...
    Standard ordering assumption for optimal prefix coding of discrete memoryless sources.
  • standard math Any prefix code satisfies the Kraft inequality sum 2^{-l_i} <= 1
    Fundamental existence condition invoked for all prefix-code length assignments.

pith-pipeline@v0.9.0 · 5389 in / 1422 out tokens · 56302 ms · 2026-05-10T05:40:33.939163+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    D. A. Huffman,A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE, vol. 40, no. 9, pp. 1098–1101, Sep. 1952

    work page 1952

  2. [2]

    Golomb,Run-length encodings (Corresp.), IEEE Transactions on Information Theory, vol

    S. Golomb,Run-length encodings (Corresp.), IEEE Transactions on Information Theory, vol. 12, no. 3, pp. 399–401, Jul. 1966

    work page 1966

  3. [3]

    Gallager and D

    R. Gallager and D. van V oorhis,Optimal source codes for geometrically distributed integer alphabets (Corresp.), IEEE Transactions on Informa- tion Theory, vol. 21, no. 2, pp. 228–230, Mar. 1975

    work page 1975

  4. [4]

    Humblet,Optimal source coding for a class of integer alphabets (Corresp.), IEEE Transactions on Information Theory, vol

    P. Humblet,Optimal source coding for a class of integer alphabets (Corresp.), IEEE Transactions on Information Theory, vol. 24, no. 1, pp. 110–112, Jan. 1978

    work page 1978

  5. [5]

    Abrahams,Huffman-type codes for infinite source distributions, Jour- nal of the Franklin Institute, vol

    J. Abrahams,Huffman-type codes for infinite source distributions, Jour- nal of the Franklin Institute, vol. 331, no. 3, pp. 265–271, 1994

    work page 1994

  6. [6]

    A. Kato, T. S. Han, and H. Nagaoka,Huffman coding with an infinite alphabet, IEEE Transactions on Information Theory, vol. 42, no. 3, pp. 977–984, May 1996

    work page 1996

  7. [7]

    Linder, V

    T. Linder, V . Tarokh, and K. Zeger,Existence of optimal prefix codes for infinite source alphabets, IEEE Transactions on Information Theory, vol. 43, no. 6, pp. 2026–2028, Nov. 1997

    work page 2026

  8. [8]

    Chow and M

    T. Chow and M. Golin,Convergence and construction of minimal-cost infinite trees, Proceedings of the 1998 IEEE International Symposium on Information Theory, p. 227, 1998

    work page 1998

  9. [9]

    Golin,Algorithms for Infinite Huffman-Codes, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’04), 2003

    M. Golin,Algorithms for Infinite Huffman-Codes, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’04), 2003

    work page 2003

  10. [10]

    Esmaeili, A

    M. Esmaeili, A. Kokhbod, and T. A. Gulliver,Representation of an- tiuniform and partially antiuniform Huffman codes, Proceedings of the IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), pp. 197–200, 2005

    work page 2005

  11. [11]

    Esmaeili and A

    M. Esmaeili and A. Kakhbod,On information theory parameters of infi- nite anti-uniform sources, IET Communications, vol. 1, no. 5, pp. 1039– 1041, 2007

    work page 2007

  12. [12]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,Introduction to Algorithms,4th ed., MIT Press, Cambridge, Massachusetts, USA, 2022, ch. 16

    work page 2022