A Lower Bound for Probabilistic Algorithms for Finite State Machines

We derive results on the densities of regular sets, the fine structure of Frievald's construction and the behavior of random walks controlled by Markov chains.