Agafonov's theorem for probabilistic selectors

Ulysse Léchine (1, 2) , Thomas Seiller (3, 1) , Jakob Grue Simonsen (4, 5)

1 LIPN - Laboratoire d'Informatique de Paris-Nord
2 Université Sorbonne Paris Nord
3 CNRS - Centre National de la Recherche Scientifique
4 DIKU - Department of Computer Science [Copenhagen]
5 UCPH - University of Copenhagen = Københavns Universitet

A normal sequence over {0,1} is an infinite sequence for which every word of length k appears with frequency 2^{−k}. Agafonov’s eponymous theorem states that selection by a finite state selector preserves normality, i.e. if α is a normal sequence and A is a finite state selector, then the subsequence A(α) is either finite or a normal sequence. In this work, we address the following question: does this result hold when considering probabilistic selectors? We provide a partial positive answer, in the case where the probabilities involved are rational. More formally, we prove that given a normal sequence α and a rational probabilistic selector P, the selected subsequence P(α) will be a normal sequence with probability 1.

Mots clés: Normal Sequences; Probabilistic Automata; Agafonov's Theorem

Domaines: Théorie et langage formel [cs.FL]; Mathématique discrète [cs.DM]; Probabilités [math.PR]

Ulysse Léchine, Thomas Seiller, Jakob Grue Simonsen. Agafonov's theorem for probabilistic selectors. 2024. ⟨hal-04563952⟩