pith. sign in

arxiv: 1906.10857 · v1 · pith:OE2FS4MZnew · submitted 2019-06-26 · 💻 cs.IT · math.IT

Guessing Individual Sequences: Generating Randomized Guesses Using Finite-State Machines

Neri Merhav This is my paper

Pith reviewed 2026-05-25 15:31 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords guessingfinite-state machinesindividual sequencesLempel-Ziv compressibilityLZ78 algorithmrandomized guessesside information
0
0 comments X

The pith

The finite-state guessing exponent of any sequence equals its Lempel-Ziv compressibility.

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

The paper studies the problem of guessing an unknown individual sequence by generating randomized guesses from a finite-state machine driven by random bits. It defines the finite-state guessing exponent as the asymptotic normalized log of the smallest achievable moment of the number of guesses needed until success. The central result shows that this exponent equals the finite-state compressibility of the sequence as introduced by Lempel and Ziv. The same exponent is achieved asymptotically by feeding random bits into a modified version of the LZ78 decoder. The relation continues to hold when the guessing machine also receives a side-information sequence.

Core claim

For any individual sequence x^n the finite-state guessing exponent equals the finite-state compressibility of x^n. This exponent is achieved by the decoder of a suitably modified LZ78 algorithm that is driven by a stream of purely random bits. The same statement holds when the machine is also given a side-information sequence y^n.

What carries the argument

Finite-state guessing exponent, defined as the asymptotic normalized logarithm of the minimum moment of the number of guesses until success, shown to equal the Lempel-Ziv finite-state compressibility.

If this is right

  • Guessing performance for any individual sequence is governed by its Lempel-Ziv compressibility.
  • The modified LZ78 decoder fed random bits attains the optimal guessing exponent for every sequence.
  • The equality between guessing exponent and compressibility extends to the presence of a side-information sequence.
  • Finite-state machines suffice to achieve the optimal individual-sequence guessing rate.

Where Pith is reading between the lines

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

  • The result supplies a direct operational meaning to Lempel-Ziv compressibility in a guessing setting.
  • It indicates that existing compression algorithms can be reused, with only minor modification, for randomized guessing tasks.
  • The framework may be testable by comparing empirical guessing moments against computed compressibility rates on long periodic or Markovian sequences.

Load-bearing premise

Guessing is performed by a finite-state machine that produces randomized guesses sequentially from a stream of purely random bits.

What would settle it

A concrete individual sequence for which the guessing exponent realized by the modified LZ78 decoder differs from the sequence's Lempel-Ziv compressibility would refute the claimed equality.

Figures

Figures reproduced from arXiv: 1906.10857 by Neri Merhav.

Figure 1
Figure 1. Figure 1: State transition diagram of the variable–to–variable length mapping (8). edges are associated with the output “b”, and ∆(B) = 2 new bits are read for the next round of the mapping (8): if the first bit is ‘0’, then we are back to state A, otherwise, we pass to state C or state F, to map ‘10’ or ‘11’, respectively, and we proceed similarly as before. 3 Converse Theorem 3.1 Preliminaries Before presenting th… view at source ↗
read the original abstract

Motivated by earlier results on universal randomized guessing, we consider an individual-sequence approach to the guessing problem: in this setting, the goal is to guess a secret, individual (deterministic) vector $x^n=(x_1,\ldots,x_n)$, by using a finite-state machine that sequentially generates randomized guesses from a stream of purely random bits. We define the finite-state guessing exponent as the asymptotic normalized logarithm of the minimum achievable moment of the number of randomized guesses, generated by any finite-state machine, until $x^n$ is guessed successfully. We show that the finite-state guessing exponent of any sequence is intimately related to its finite-state compressibility (due to Lempel and Ziv), and it is asymptotically achieved by the decoder of (a certain modified version of) the 1978 Lempel-Ziv data compression algorithm (a.k.a. the LZ78 algorithm), fed by purely random bits. The results are also extended to the case where the guessing machine has access to a side information sequence, $y^n=(y_1,\ldots,y_n)$, which is also an individual sequence.

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 / 3 minor

Summary. The manuscript formulates the guessing problem for an arbitrary individual sequence x^n using a finite-state machine that consumes a stream of i.i.d. fair random bits and produces successive guesses until x^n is hit. The finite-state guessing exponent is defined as the lim sup (1/n) log of the smallest achievable E[G^rho] (rho>0) over all finite-state guessing machines. The central claim is that this exponent equals the Lempel-Ziv finite-state compressibility rate of x^n for every sequence and is asymptotically attained by the decoder of a suitably modified LZ78 algorithm driven by random bits. The result is extended to the case with an individual side-information sequence y^n.

Significance. If the claimed equality holds, the work supplies a parameter-free, sequence-by-sequence link between the guessing exponent under finite-state randomization and the classical LZ compressibility measure. The constructive achievability result via a modified LZ78 decoder is a concrete strength: the same sequential parsing that achieves optimal compression also yields optimal guessing when the dictionary is driven by random bits. This extends earlier probabilistic guessing results to the individual-sequence setting without introducing fitted parameters or additional assumptions on state cardinality.

minor comments (3)
  1. [Abstract] The abstract states that the guessing exponent 'is intimately related' to LZ compressibility; the introduction or Section II should state the precise equality (guessing exponent = LZ rate) at the first opportunity.
  2. [Introduction] Notation for the moment order rho, the normalization factor 1/n, and the precise definition of the finite-state machine (input alphabet, output mapping, state transition) should be fixed before the main theorem statements.
  3. The description of the 'modified version' of LZ78 should include an explicit statement of which component (dictionary construction, parsing rule, or output mapping) is altered to accept random bits.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the insightful summary of our contributions, and the recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper defines the finite-state guessing exponent for individual sequences and relates it to the established Lempel-Ziv finite-state compressibility via standard relations between sequential parsing, dictionary growth, and moment-generating functions on the number of trials. Both the converse (FS machines cannot beat the LZ rate) and direct part (achievability via modified LZ78 decoder) follow from these external, pre-existing arguments without any reduction to fitted parameters, self-definitional loops, or load-bearing self-citations. The side-information case uses the same joint parsing approach. The derivation is self-contained against the external LZ benchmark and does not rename or smuggle in results via author citations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review based on abstract only; no explicit free parameters, invented entities, or non-standard axioms are described. The work references standard finite-state machine definitions and Lempel-Ziv compressibility as background.

axioms (1)
  • standard math Standard definitions and asymptotic properties of finite-state machines and normalized logarithmic exponents from information theory and automata theory
    The abstract invokes these as the foundation for defining the guessing exponent and relating it to compressibility.

pith-pipeline@v0.9.0 · 5718 in / 1147 out tokens · 46875 ms · 2026-05-25T15:31:23.384882+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

14 extracted references · 14 canonical work pages

  1. [1]

    An inequality on guessing and its applicatio n to sequential decoding,

    E. Arikan, “An inequality on guessing and its applicatio n to sequential decoding,” IEEE Trans. Inform. Theory , vol. IT–42, no. 1, pp. 99–105, January 1996

    work page 1996

  2. [2]

    T. M. Cover and J. A. Thomas, Elements of Information Theory , Second Edition, John Wiley & Sons, Hoboken, New Jersey, U.S.A., 2006

    work page 2006

  3. [3]

    Gambling using a finite–state machine,

    M. Feder, “Gambling using a finite–state machine,” IEEE Trans. on Inform. Theory , vol. 37, no. 5, pp. 1459–1465, September 1991

    work page 1991

  4. [4]

    Universal predictio n of individual sequences,

    M. Feder, N. Merhav, and M. Gutman, “Universal predictio n of individual sequences,” IEEE Trans. Inform. Theory , vol. 38, no. 4, pp. 1258–1270, July 1992

    work page 1992

  5. [5]

    On the complexity of finite sequence s,

    A. Lempel and J. Ziv, “On the complexity of finite sequence s,” IEEE Trans. Inform. Theory , vol. IT–22, no. 1, pp. 75–81, January 1976

    work page 1976

  6. [6]

    Guessing and entropy,

    J. L. Massey, “Guessing and entropy,” Proc. IEEE International Symposium on Information Theory (ISIT ’94) , p. 204, 1994

    work page 1994

  7. [7]

    Universal coding with minimum probability o f code word length overflow,

    N. Merhav, “Universal coding with minimum probability o f code word length overflow,” IEEE Trans. Inform. Theory , vol. 37, no. 3, pp. 556–563, May 1991

    work page 1991

  8. [8]

    Perfectly secure encryption of individual s equences,

    N. Merhav, “Perfectly secure encryption of individual s equences,” IEEE Trans. Inform. The- ory, vol. 59, no. 3, pp. 1302–1310, March 2013

    work page 2013

  9. [9]

    Universal detection of messages via finite–s tate channels,

    N. Merhav, “Universal detection of messages via finite–s tate channels,” IEEE Trans. Inform. Theory, vol. 46, no. 6, pp. 2242–2246, September 2000

    work page 2000

  10. [10]

    Universal randomized guessing with application to asynchronous decentralized brute–force attacks,

    N. Merhav and A. Cohen, “Universal randomized guessing with application to asynchronous decentralized brute–force attacks,” to appear in IEEE Trans. Inform. Theory , 2019

    work page 2019

  11. [11]

    Why botnets work: distributed brute–force attacks need no synchronization,

    S. Salamatian, W. Huleihel, A. Beirami, A. Cohen, and M. Médard, “Why botnets work: distributed brute–force attacks need no synchronization, ” to appear in IEEE Trans. Inform. Forensics and Security , September 2019. 22

    work page 2019

  12. [12]

    Conditional Lempel-Ziv co mplexity and its application to source coding theorem with side information,

    T. Uyematsu and S. Kuzuoka, “Conditional Lempel-Ziv co mplexity and its application to source coding theorem with side information,” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences , vol. 86, no. 10, pp. 2615–2617, October 2003

    work page 2003

  13. [13]

    Universal decoding for finite–state channels,

    J. Ziv, “Universal decoding for finite–state channels, ” IEEE Trans. Inform. Theory , vol. IT– 31, no. 4, pp. 453–460, July 1985

    work page 1985

  14. [14]

    Compression of individual sequen ces via variable-rate coding,

    J. Ziv and A. Lempel, “Compression of individual sequen ces via variable-rate coding,” IEEE Trans. Inform. Theory , vol. IT–24, no. 5, pp. 530–536, September 1978. 23

    work page 1978