Ergodicity of Random Walks on Random DFA

2013/11/26 by Borja Balle, Balle, Borja
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.DM #cs.FL

paper · pdf · doi:10.48550/arxiv.1311.6830

arxiv created 2013/11/26 · arxiv updated 2013/11/28

Abstract

Given a DFA we consider the random walk that starts at the initial state and at each time step moves to a new state by taking a random transition from the current state. This paper shows that for typical DFA this random walk induces an ergodic Markov chain. The notion of typical DFA is formalized by showing that ergodicity holds with high probability when a DFA is sampled uniformly at random from the set of all automata with a fixed number of states. We also show the same result applies to DFA obtained by minimizing typical DFA.

Related

• Ergodic properties of some Markov chains models in random environments
• Strict irreducibility of Markov chains and ergodicity of skew products
• Total Variation Discrepancy of Deterministic Random Walks for Ergodic Markov Chains
• Limit theorems for random walks in dynamic random environment
• Deterministically driven random walks in a random environment on Z