2026/04/14 by Laurent Bienvenu, Santiago Cifuentes, Hugo Gimbert · 1 voice
Computer Science · #Automata theory #Computability, Logic, AI Algorithms #Deterministic finite automaton #Finite set #Finite-state machine #Formal Methods in Verification #Probabilistic logic #Quantum finite automata #Sequence (biology) #Value (mathematics) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2604.12457
openalex publication_date 2026/04/14 · arxiv published 2026/04/14 · arxiv updated 2026/04/14 · openalex created_date 2026/04/16 · openalex updated_date 2026/07/28
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∈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.