  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.
