A lower bound for probabilistic algorithms for finite state machines

摘要

Freivalds recently reported a construction of a 2-way probabilistic finite automaton M that recognizes the set {ambm: m ⩾ 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 Ω(2n2n) 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 {ambm: m ⩾ 1} with probability of error bounded away from 12. 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.