On the probability to be synchronizable
Mikhail V. Berlinkov · arXiv (Cornell University) · 2013
We prove that a random automaton with $n$ states and any fixed non-singleton alphabet is synchronizing with high probability. Moreover, we also prove that the convergence speed is exactly $1-\Theta(\frac{1}{n})$ as conjectured by Cameron \cite{CamConj} for the most interesting 2-letter alphabet case.