# Random Cerny Conjecture

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?

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, 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, 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}$$.
• Actually, the expected time to reach the terminal state in this simple Markov chain is asymptotic to $2^{k+1}$ by Wald's lemma. Jun 22, 2022 at 2:05