×

Predictions with automata. (English) Zbl 0777.11028

Symbolic dynamics and its applications, Proc. AMS Conf. in honor of R. L. Adler, New Haven/CT (USA) 1991, Contemp. Math. 135, 111-124 (1992).
[For the entire collection see Zbl 0755.00019.]
One of the approaches for the notion of randomness of infinite sequences is the concept of normality. In this interesting paper the authors introduce the notion of prediction by finite (deterministic) automaton. It is natural to think that a random sequence (\(u_ n)_ n\) taking its value in a set of cardinality \(q\) has the property that, knowing \(u_ 0,\dots,u_{n-1}\), one cannot “predict” the value of \((u_ n)\) with a probability greater than \(1/q\).
The main result of the authors is that an infinite sequence is normal if and only if all the probabilities of “automatic predictions” are equal to \(1/q\) [the case \(q=2\) has been studied with different methods by M. O’Connor, J. Comput. Syst. Sci. 37, 324-336 (1988; Zbl 0667.68064)].
The authors also give a new (and more general) proof of the (intuitive) result announced by V. N. Agafonov in the case of binary sequences [Sov. Math., Dokl. 9, 324-325 (1968); translation from Dokl. Akad. Nauk SSSR 179, 255-256 (1968; Zbl 0242.94040)]; extracting by automata a subsequence from a normal sequence yields a normal sequence [see also T. Kamae and B. Weiss, Isr. J. Math. 21, 101-110 (1975; Zbl 0327.28014)].

MSC:

11K16 Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc.
68Q45 Formal languages and automata
PDFBibTeX XMLCite