Random Cerny Conjecture

Question

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?

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}$.