Characterizing normality via automata and random matrix products
For researchers in algorithmic randomness and automata theory, this provides a novel characterization of normality using probabilistic automata, extending a foundational result from 1972.
The paper extends the classical result linking normality of sequences to deterministic automata by proving an analogous characterization using probabilistic automata: a sequence is normal iff the expected capital of any probabilistic automaton-based gambling strategy converges exponentially fast to a finite value. This is derived from a more general result on the convergence of products of non-negative matrices, and the problem of classifying such matrix families is shown to be decidable.
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.