Walks on random graphs has been a subject of extensive research over the past two decades.While the theory is well-established for undirected graphs, the directed case is much less understood.Unfortunately, networks that arise in applications are often inherently directed (e.g. World Wide Web,citation network, ...). In recent years, novel techniques have emerged to tackle the complexities in thedirected setting. In this talk we will survey some of the most prominent results in the area concerning randomand non-random walks. We will delve into the mixing properties of the random walks and their (random)stationary measures, providing algorithmic insights. Additionally, we will explore the use of randomdigraphs as a model for random Deterministic Finite Automata (DFA), obtaining a probabilistic version ofČerný's conjecture concerning automata synchronization.
The results presented are based on joint work with Xing Shi Cai, Pietro Caputo and Matteo Quattropaniand with Guillaume Chapuy.