On the meeting of random walks on random DFA

We consider two random walks evolving synchronously on a random out-regular graph of n vertices with bounded out-degree r >= 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 (2017) in the context of computational learning, the connection with which is discussed.(c) 2023 Elsevier B.V. All rights reserved.