A lower bound for probabilistic algorithms for finite state machines (Q579936)

\textit{R. Freivalds} [Lect. Notes Comput. Sci. 118, 33-45 (1981; Zbl 0486.68045)] recently reported a construction of a 2-way probabilistic finite automaton M that recognizes the set \(\{a^ mb^ m:m\geq 1\}\) with arbitrarily small probability of error. This result implies that probabilistic machines of this type are more powerful than their deterministic, nondeterministic, and alternating counterparts. Freivalds' construction has a negative feature: the automaton M runs in \(\Omega (2^{n/2}n)\) expected time in the worst case on inputs of length n. We show that it is impossible to do significantly better. Specifically, no 2-way probabilistic finite automaton that runs in exp(o(n)) expected time recognizes \(\{a^ mb^ m:m\geq 1\}\) with probability of error bounded away from \(1/2\). In passing we derive results on the densities of regular sets, the fine structure of Freivalds' construction, and the behavior of random walks controlled by Markov chains.