On the Probability of Being Synchronizable

摘要

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 rate is exactly 1 - Θ(1) as conjectured by Cameron for the most interesting binary alphabet case.