The Agafonov and Schnorr-Stimm theorems for probabilistic automata
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929718829252608 |
|---|---|
| author | Bienvenu, Laurent Gimbert, Hugo Pulari, Subin |
| author_facet | Bienvenu, Laurent Gimbert, Hugo Pulari, Subin |
| contents | 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, this question was positively answered by Léchine et al.\ (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$. We also show that a sequence $X$ is normal if and only if a probabilistic finite-state gambler fails to win on $X$ with probability $1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_12307 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Agafonov and Schnorr-Stimm theorems for probabilistic automata Bienvenu, Laurent Gimbert, Hugo Pulari, Subin Formal Languages and Automata Theory Information Theory 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, this question was positively answered by Léchine et al.\ (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$. We also show that a sequence $X$ is normal if and only if a probabilistic finite-state gambler fails to win on $X$ with probability $1$. |
| title | The Agafonov and Schnorr-Stimm theorems for probabilistic automata |
| topic | Formal Languages and Automata Theory Information Theory |
| url | https://arxiv.org/abs/2502.12307 |