2026-08-16T03:02:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25097 2026-02-09T08:06:08Z ddc:004 open_access

The Agafonov and Schnorr-Stimm Theorems for Probabilistic Automata Bienvenu, Laurent Gimbert, Hugo Pulari, Subin Normality Agafonov theorem probabilistic automata 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 of Agafonov (1966) relates normality to finite automata as follows: a sequence X is normal if and only if any subsequence of X selected by a finite automaton is itself normal. Another theorem of Schnorr and Stimm (1972) gives an alternative characterization: a sequence X is normal if and only if no gambler can win large amounts of money by betting on the sequence X using a strategy that can be described by a finite automaton. Both of these theorems are established in the setting of deterministic finite automata. This raises the question as to whether they can be extended to the setting of probabilistic finite automata. In the case of the Agafonov theorem, a partial positive answer was given by Léchine et al. (MFCS 2024) in a restricted case of probabilistic automata with rational transition probabilities. In this paper, we settle the full conjecture by proving that both the Agafonov and the Schnorr-Stimm theorems hold true for arbitrary probabilistic automata. Specifically, we show that a sequence X is normal if and only if any probabilistic automaton selects a normal subsequence of X with probability 1 and also show that a sequence X is normal if and only if any probabilistic finite-state gambler fails to win on X with probability 1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laurent Bienvenu and Hugo Gimbert and Subin Pulari 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.16 urn:nbn:de:0030-drops-250978 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode