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.

On the meeting of random walks on random DFA

Federico Sau
2023-01-01

Abstract

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.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304414923001898-main.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 1.83 MB
Formato Adobe PDF
1.83 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
1-s2.0-S0304414923001898-main-Post_print.pdf

embargo fino al {0}

Tipologia: Bozza finale post-referaggio (post-print)
Licenza: Creative commons
Dimensione 2.5 MB
Formato Adobe PDF
2.5 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/3066459
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact