For simplicity, all DFAs will be using the binary alphabet $\{0,1\}$. Let $M$ be a synchronizable DFA. We let $p(M,n)$ be the probability that a random $x\in \{0,1\}^n$ will synchronize $M$.

We define $P(k,n)$ to be the minimum of $p(M,n)$ taken over all DFAs $M$ having $k$ states. I want to know asymptotic bounds for $f$ such that $P(k,f(k)) \to 1$ exponentially fast (so there is $c <1$ such that $P(k,f(k))>1-c^k$ asymptotically). I know how to prove that $f(k) = k^42^{k^2}$ suffices. For any two states in a DFA, there will exist a string with length at most $k^2$ which synchs the two states, thus the probality that $k^2 2^{k^2}$ random bits will not synchronize a new pair of states is at most $1/e$. The rest quickly follows.

Can this upper bound be improved? What kind of lower bounds are possible?


1 Answer 1


I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any pair of states.

An exponential lower bound on $f$ can be given as follows.
Take a DFA whose states are $v_1,\ldots,v_k$ and the transition function is such that reading a 1 we go ahead by one until we reach the end, i.e., $\delta_1(v_i)=v_{i+1}$ for $i<k$, while $\delta_1(v_k)=v_k$, but if we read a 0 before the end we have to start all over again, i.e., $\delta_0(v_i)=v_1$ for $i<k$, while $\delta_0(v_k)=v_k$.
If the initial states are $v_1$ and $v_k$, then the question is how fast we reach the terminal state in this simple Markov-chain; in expectation this is about $2^{k+1}$.

  • $\begingroup$ Actually, the expected time to reach the terminal state in this simple Markov chain is asymptotic to $2^{k+1}$ by Wald's lemma. $\endgroup$ Commented Jun 22, 2022 at 2:05
  • $\begingroup$ Thanks, fixed it. $\endgroup$
    – domotorp
    Commented Jun 22, 2022 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.