On the meeting of random walks on random DFA

Abstract

We consider two random walks evolving synchronously on a random out-regular graph of $n$ vertices with bounded out-degree $r\ge 2$, also known as a random Deterministic Finite Automaton (DFA). We show that, with high probability with respect to the generation of the graph, the meeting time of the two walks is stochastically dominated by a geometric random variable of rate $(1+o(1))n^{-1}$, uniformly over their starting locations. Further, we prove that this upper bound is typically tight, i.e., it is also a lower bound when the locations of the two walks are selected uniformly at random. Our work takes inspiration from a recent conjecture by Fish and Reyzin in the context of computational learning, the connection with which is discussed.

30 pages, 4 figures

References in corpus (1)

• Minimum stationary values of sparse random directed graphs

Cited by in corpus (2)

• Discordant edges for the voter model on regular random graphs
• Mixing trichotomy for random walks on directed stochastic block models