Expected acceptance counts for finite automata with almost uniform input. (English) Zbl 1019.68053

Pippenger, Nicholas

Bose, Prosenjit (ed.) et al., Algorithms and computation. 13th international symposium, ISAAC 2002, Vancouver, BC, Canada, November 21-23, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2518, 636-646 (2002).

Summary: If a sequence of independent unbiased random bits is fed into a finite automaton, it is straightforward to calculate the expected number of acceptances among the first \(n\) prefixes of the sequence. This paper deals with the situation in which the random bits are neither independent nor unbiased, but are nearly so. We show that, under suitable assumptions concerning the automaton, if the the difference between the entropy of the first \(n\) bits and \(n\) converges to a constant exponentially fast, then the change in the expected number of acceptances also converges to a constant exponentially fast. We illustrate this result with a variety of examples in which numbers following the reciprocal distribution, which governs the significands of floating-point numbers, are recoded in the execution of various multiplication algorithms.
For the entire collection see [Zbl 1007.00050].

MSC:

68Q45	Formal languages and automata
68Q05	Models of computation (Turing machines, etc.) (MSC2010)