Short Synchronizing Words for Random Automata

Guillaume Chapuy, Guillem Perarnau

We prove that a uniformly random automaton with $n$ states on a 2-letter alphabet has a synchronizing word of length $O(n^{1/2}\log n)$ with high probability (w.h.p.). That is to s…