论文标题
在随机DFA的随机散步会议上
On the meeting of random walks on random DFA
论文作者
论文摘要
我们考虑两次随机步行在带有有限的外部$ r \ ge 2 $的$ n $顶点的随机外图上同步演变，也称为随机确定性有限自动机（DFA）。我们表明，对于图表的产生，两次步行的会议时间很高，在其起始位置上均匀地在速率$ $（1+O（1））N^{ - 1} $的几何随机变量随机统治。此外，我们证明这种上限通常是紧密的，即，当两个步行的位置随机选择时，它也是下限。我们的工作从Fish和Reyzin最近在计算学习的背景下的猜想（与之的联系）中汲取灵感。
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.
