arxiv: 2604.12457 · v1 · submitted 2026-04-14 · 💻 cs.FL

Recognition: unknown

Characterizing normality via automata and random matrix products

Laurent Bienvenu (CNRS , LaBRI) , Santiago Cifuentes (ICC , UBA) , Hugo Gimbert (CNRS

Authors on Pith no claims yet

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

classification 💻 cs.FL

keywords normalityprobabilistic automatamatrix productsmartingalesconvergencedecidabilitysequences

0 comments

The pith

A sequence is normal precisely when every probabilistic finite automaton gambler sees its expected capital converge exponentially to a finite limit.

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

The paper proves that an infinite sequence over a fixed alphabet is normal if and only if the expected capital of any gambler using a probabilistic finite automaton converges exponentially fast to a finite value. This characterization extends the classical result for deterministic automata by Schnorr and Stimm. The proof relies on a more general statement about the exponential convergence of norms of products of non-negative matrices corresponding to the sequence symbols. The result also establishes that for any family of such matrices there are three possible asymptotic behaviors for the product norms, and that recognizing which behavior a given family exhibits is decidable.

Core claim

A sequence X is normal if and only if for any gambling strategy implementable with a probabilistic finite automaton the expected value of the gambler's capital converges exponentially fast to a finite value when playing against X. Equivalently, for any family of non-negative matrices {M_a | a in A}, the norm ||v M_{X[1]} ... M_{X[n]}|| converges exponentially fast to a finite value for any non-negative starting vector v. Moreover, any such matrix product sequence falls into one of three distinctive behaviors, and the problem of determining which case holds is decidable.

What carries the argument

The norm convergence of iterated products of non-negative matrices derived from probabilistic automata transitions, which must stabilize exponentially for normal sequences.

Load-bearing premise

That convergence of capital expectations for probabilistic automaton strategies fully captures the property of normality without missing or overcounting betting behaviors.

What would settle it

Construct a non-normal sequence for which some probabilistic finite automaton has expected capital that fails to converge exponentially to a finite value.

Figures

Figures reproduced from arXiv: 2604.12457 by Hugo Gimbert (CNRS, LaBRI), Laurent Bienvenu (CNRS, Santiago Cifuentes (ICC, UBA).

**Figure 2.** Figure 2: On the left, a (deterministic) automaton that belo [PITH_FULL_IMAGE:figures/full_fig_p029_2.png] view at source ↗

**Figure 3.** Figure 3: Automaton that belongs to Case 2. The transitions a [PITH_FULL_IMAGE:figures/full_fig_p031_3.png] view at source ↗

**Figure 4.** Figure 4: Sketch of the proof of Claim 10. The dashed arrows indicate the evolution of the vector v according to z1 and z2. The solid arrows indicate which previous results we use to bound the increase of the norm. IH denotes the inductive hypothesis. where the second inequality follows again by properties of the Live function, the third one by Eqs. (11) and (12) and the last one by considering α = min{αC, αD} and… view at source ↗

read the original abstract

For a fixed alphabet A, an infinite sequence X is said to be normal if every word w over A appears in X with the same frequency as any other word of the same length. A classical result relates normality to finite automata as follows: a sequence X is normal if and only if all gambling strategies implementable with finite deterministic automata lose all their capital when trying to predict the next bit of X after seing the ones before. More precisely, Schnorr and Stimm (1972) proved that the capital goes exponentially fast to zero unless the automaton represents the gambler that never bets, in which case the capital remains constant. In this paper we show that an analogous result holds when considering probabilistic automata: a sequence X is normal if and only if for any gambling strategy implementable with probabilistic finite automaton it holds that the expected value of the capital of the gambler converges exponentially fast to a finite value when playing against X. To obtain this result, we show a more general statement related to the convergence of martingales given by finite sets of non-negative matrices {M a } a$\in$A . In particular, we show that X is normal if and only if ||vM X[1] . . . M X[n] || converges exponentially fast to a finite value for any non-negative starting vector v. Moreover, we distinguish three distinctive behaviours that this sequence can attain, and prove that the problem of recognizing, given a family of matrices, to which case it belongs, is decidable.

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.

Desk Editor's Note private letter to a colleague

This extends Schnorr-Stimm to probabilistic automata by showing normality is equivalent to exponential convergence of expected capital (or matrix-product norms) and adds decidability for the three possible asymptotic regimes.

read the letter

The main takeaway is that normality of a sequence X is equivalent to every probabilistic finite-automaton betting strategy having expected capital that converges exponentially fast to a finite limit, and that this is captured exactly by the norm of iterated non-negative matrix products ||v M_{X[1]} ... M_{X[n]}|| doing the same for any starting v. They also split the possible behaviors of such products into three cases (decay to zero, convergence to a positive constant, or unbounded growth) and show each case is decidable given the matrix family. This is the natural probabilistic lift of the 1972 deterministic result, and the matrix formulation makes the equivalence clean because every PFA strategy translates directly into a finite set of non-negative transition matrices whose products track the expected capital exactly. The martingale property holds under the uniform measure as long as the per-symbol factors average to one, so the quantification over all strategies is faithful. The decidability part is the clearest addition; it turns an analytic statement into something algorithmic. The paper does this without introducing extra parameters or circular definitions, and the stress-test confirms there is no gap between the matrix condition and the full set of implementable PFA strategies. One minor limitation is that the exponential rate is per automaton rather than uniform across all of them, but that is already implicit in the classical deterministic case and does not weaken the iff. The proofs appear to rest on standard facts about non-negative matrix products and their growth rates, which keeps the argument grounded. This work is aimed at people in algorithmic randomness and computability who already know the Schnorr-Stimm theorem and want the probabilistic version plus a decision procedure. It is narrow but technically precise, so it deserves a serious referee rather than a desk reject.

Referee Report

0 major / 3 minor

Summary. The manuscript extends the Schnorr-Stimm theorem by showing that an infinite sequence X over a finite alphabet is normal if and only if, for every gambling strategy realizable by a probabilistic finite automaton, the expected capital converges exponentially fast to a finite limit. Equivalently, X is normal if and only if ||v M_{X[1]} ⋯ M_{X[n]}|| converges exponentially fast to a finite value for every family of non-negative matrices {M_a} and every non-negative initial vector v. The paper distinguishes three asymptotic regimes for such products and proves that, given a matrix family, deciding which regime holds is decidable.

Significance. If the central equivalences hold, the work supplies a clean matrix-product characterization of normality that faithfully encodes all probabilistic finite-automaton strategies via non-negative linear updates, thereby generalizing the deterministic-automaton case while preserving the martingale property under the uniform measure. The accompanying decidability result for the three regimes is a concrete algorithmic contribution that may be useful for classifying families of non-negative matrices with respect to their growth along normal sequences.

minor comments (3)

Abstract and introduction: the three asymptotic regimes are referred to but never enumerated; an explicit list (decay to zero, convergence to a positive finite limit, unbounded growth) should appear in the first paragraph that introduces the matrix-product statement.
Notation: the norm symbol ||·|| is used without an immediate definition in the abstract and early sections; the paper should state which matrix norm is employed (e.g., the 1-norm or max-norm) and verify that the claimed exponential convergence is independent of the choice among equivalent norms.
The decidability claim for the classification problem is stated in the abstract; the manuscript should include a brief complexity remark (e.g., whether the procedure is polynomial-time) or at least a pointer to the section containing the algorithm.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our manuscript, which correctly captures the extension of the Schnorr-Stimm theorem to probabilistic finite automata, the equivalent matrix-product characterization of normality, and the decidability result for the three asymptotic regimes. We are pleased that the referee views these contributions as significant and recommends only minor revision.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper establishes an equivalence between normality (uniform word frequencies) and exponential convergence of matrix-product norms for non-negative matrices arising from probabilistic finite automata. This is obtained by explicitly encoding any PFA gambling strategy as a linear capital update whose expectation is the product v M_{X[1]} … M_{X[n]}, then distinguishing the three asymptotic regimes (decay, finite limit, unbounded growth) via martingale arguments. The classical deterministic-automaton result of Schnorr-Stimm is cited as external background; the extension to the probabilistic case is proved directly from the matrix representation without fitting parameters to the target property, without self-citation load-bearing the central claim, and without renaming a known empirical pattern. The matrix condition is shown to capture exactly the set of implementable strategies, so the iff statement does not collapse to a tautology or a fitted input.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on standard properties of non-negative matrices, norms, and martingale convergence; no free parameters or new entities are introduced.

axioms (2)

standard math Non-negative matrices induce submultiplicative norms and the product norm converges or diverges in one of three regimes.
Invoked to classify the possible limit behaviors of the iterated product.
domain assumption Probabilistic automata correspond to families of non-negative matrices whose action on capital vectors yields martingales.
Links the gambling interpretation to the matrix formulation.

pith-pipeline@v0.9.0 · 5585 in / 1409 out tokens · 37467 ms · 2026-05-10T14:08:48.247789+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

20 extracted references

[1]

Normal sequences and ﬁni te automata

Valerii Nikolaevich Agafonov. Normal sequences and ﬁni te automata. In Doklady Akademii Nauk , volume 179, pages 255–256. Russian Academy of Sciences, 19 68
[2]

The Probabilistic Method, 4th Edition

Noga Alon and Joel Spencer. The Probabilistic Method, 4th Edition . Wiley, 2016

2016
[3]

Computational Complexity: A Modern Approach

Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach . Cambridge University Press, 2009

2009
[4]

An example of a computable absolutely normal number

Ver´ onica Becher and Santiago Figueira. An example of a computable absolutely normal number. Theoretical Computer Science , 270(1-2):947–958, 2002

2002
[5]

The Ag afonov and Schnorr- Stimm theorems for probabilistic automata

Laurent Bienvenu, Hugo Gimbert, and Subin Pulari. The Ag afonov and Schnorr- Stimm theorems for probabilistic automata. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025), volume 360 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 16:1–16:15, 2025

2025
[6]

Probabilistic vs deter- ministic gamblers

Laurent Bienvenu, Valentino Delle Rose, and Tomasz Stei fer. Probabilistic vs deter- ministic gamblers. In 39th International Symposium on Theoretical Aspects of Com- puter Science, STACS 2022 , volume 219 of LIPIcs, pages 11:1–11:13. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2022

2022
[7]

Extensions of Jentzsch’s theorem

Garrett Birkhoﬀ. Extensions of Jentzsch’s theorem. Transactions of the American Mathematical Society, 85(1):219–227, 1957. 38

1957
[8]

Probabilistic algorithmic rand omness

Sam Buss and Mia Minnes. Probabilistic algorithmic rand omness. The Journal of Symbolic Logic, 78(2):579–601, 2013

2013
[9]

Some algebraic and geometric computations i n PSPACE

John Canny. Some algebraic and geometric computations i n PSPACE. In Proceedings of the twentieth annual ACM symposium on Theory of computing , pages 460–467, 1988

1988
[10]

The construction of decimals nor mal in the scale of ten

David G Champernowne. The construction of decimals nor mal in the scale of ten. Journal of the London Mathematical Society , 1(4):254–260, 1933

1933
[11]

Note on normal number s

Arthur H Copeland and Paul Erd¨ os. Note on normal number s. Bull. Amer. Math. Soc., 52(10):857–860, 1946

1946
[12]

Algorithmic randomness and complexity

Rodney Downey and Denis Hirschfeldt. Algorithmic randomness and complexity . The- ory and Applications of Computability. Springer, 2010

2010
[13]

Les probabilit´ es d´ enombrables et leurs appl ications arithm´ etiques

M ´Emile Borel. Les probabilit´ es d´ enombrables et leurs appl ications arithm´ etiques. Rendiconti del Circolo Matematico di Palermo (1884-1940) , 27(1):247–271, 1909

1940
[14]

Horn and Charles R

Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge University Press, 2012

2012
[15]

Agafonov’s theorem for probabilistic selectors

Ulysse L´ echine, Thomas Seiller, and Jakob Grue Simons en. Agafonov’s theorem for probabilistic selectors. In 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024 , volume 306 of LIPIcs, pages 67:1–67:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024

2024
[16]

Markov chains and mixing times , volume 107

David A Levin and Yuval Peres. Markov chains and mixing times , volume 107. Amer- ican Mathematical Society, 2017

2017
[17]

An introduction to Kolmogorov complexity and its appli- cations

Ming Li and Paul Vit´ anyi. An introduction to Kolmogorov complexity and its appli- cations. Texts in Computer Science. Springer-Verlag, New York, 3rd edition, 2008

2008
[18]

Computability and randomness

Andr´ e Nies. Computability and randomness . Oxford Logic Guides. Oxford University Press, 2009

2009
[19]

Endliche Autom aten und Zufallsfolgen

Claus-Peter Schnorr and Hermann Stimm. Endliche Autom aten und Zufallsfolgen. Acta Informatica, 1(4):345–359, 1972

1972
[20]

Kolmogorov Com- plexity and Algorithmic Randomness , volume 220 of Mathematical Surveys and Mono- graphs

Alexander Shen, Vladimir Uspensky, and Nikolai Veresh chagin. Kolmogorov Com- plexity and Algorithmic Randomness , volume 220 of Mathematical Surveys and Mono- graphs. American Mathematical Society, 2017. 39

2017