On the meeting of random walks on random DFA

DOI10.1016/j.spa.2023.104225arXiv2204.02827OpenAlexW4387081915MaRDI QIDQ6144443

Federico Sau, Matteo Quattropani

Publication date: 29 January 2024

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.02827

zbMATH Keywords

random walksmeeting timesfirst visit time lemmarandom deterministic finite automaton

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Continuous-time Markov processes on discrete state spaces (60J27) Random walks on graphs (05C81)

Cites Work

• Unnamed Item
• Unnamed Item
• Mean field conditions for coalescing random walks
• Diameter and stationary distribution of random \(r\)-out digraphs
• Markov chains with almost exponential hitting times
• Cutoff at the ``entropic time for sparse Markov chains
• Coalescing random walks and voter model consensus times on the torus in \({\mathbb{Z}}^ d\)
• Mixing time trichotomy in regenerating dynamic digraphs
• Stationary distribution and cover time of sparse directed configuration models
• From coalescing random walks on a torus to Kingman's coalescent
• Random walk on sparse random digraphs
• Multiple Random Walks in Random Regular Graphs
• The cover time of sparse random graphs
• The cover time of the giant component of a random graph
• A note on the number of queries needed to identify regular languages
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• A probabilistic proof of Cooper and Frieze's "First Visit Time Lemma"
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• The Cerny Conjecture Holds with High Probability
• On coalescence time in graphs: When is coalescing as fast as meeting?: Extended Abstract
• The Cover Time of Random Regular Graphs
• On the coalescence time of reversible random walks
• Coalescing Random Walks and Voting on Connected Graphs
• A logical calculus of the ideas immanent in nervous activity
• Mixing time of PageRank surfers on sparse random digraphs
• Rankings in directed configuration models with heavy tailed in-degrees