Random-DFA synchronization-time mean-field conjecture

Let $\tau_{\rm sync}$ denote the synchronization time of the random DFA, and retain the notation in which $\mathbf Q$ is the uniform distribution on words of the relevant length. Random-DFA synchronization-time conjecture.

$$\frac{\mathbf E_{\mathbf Q}[\tau_{\rm sync}]}{n}\overset{\mathbb P}{\longrightarrow}2.$$

Therefore, for every $\varepsilon>0$, there exists $c=c_\varepsilon>0$ such that, with high probability,

$$\mathbf Q(\tau_{\rm sync}>cn)\le\varepsilon.$$

The conjecture expresses the expected mean-field behavior suggested by the analogous coalescing-walk model: synchronization should occur on the linear time scale, with asymptotic mean $2n$.