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

CC BY-SA 4.0
2022-06-22T02:05:48.717Z
Actually, the expected time to reach the terminal state in this simple Markov chain is asymptotic to $2^{k+1}$ by Wald's lemma.
Yuval Peres
CC BY-SA 4.0
2022-06-22T08:58:33.180Z
Thanks, fixed it.
domotorp
CC BY-SA 4.0
2021-03-01T21:45:15.187Z
2022-06-22T08:57:46.603Z
2022-06-22T08:57:46.603Z
domotorp
<p>For simplicity, all DFAs will be using the binary alphabet <span class="math-container">$\{0,1\}$</span>. Let <span class="math-container">$M$</span> be a synchronizable DFA. We let <span class="math-container">$p(M,n)$</span> be the probability that a random <span class="math-container">$x\in \{0,1\}^n$</span> will synchronize <span class="math-container">$M$</span>.</p>
<p>We define <span class="math-container">$P(k,n)$</span> to be the minimum of <span class="math-container">$p(M,n)$</span> taken over all DFAs <span class="math-container">$M$</span> having <span class="math-container">$k$</span> states. I want to know asymptotic bounds for <span class="math-container">$f$</span> such that <span class="math-container">$P(k,f(k)) \to 1$</span> exponentially fast (so there is  <span class="math-container">$c &lt;1$</span> such that <span class="math-container">$P(k,f(k))&gt;1-c^k$</span> asymptotically). I know how to prove that <span class="math-container">$f(k) = k^42^{k^2}$</span> suffices. For any two states in a DFA, there will exist a string with length at most <span class="math-container">$k^2$</span> which synchs the two states, thus the probality that <span class="math-container">$k^2 2^{k^2}$</span> random bits will not synchronize a new pair of states is at most <span class="math-container">$1/e$</span>. The rest quickly follows.</p>
<p>Can this upper bound be improved? What kind of lower bounds are possible?</p>

<graph-theory><automata-theory><dfa><random-walks>
Random Cerny Conjecture
Zach Hunter
# Random Cerny Conjecture

(Asked by: username_0 on 2021-03-01)

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?

**Tags:** graph-theory, automata-theory, dfa, random-walks


---

## 1 answers

### Answer by username_1 on 2021-03-01. Score: 5

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

> **Comments:**
> **username_2**: Actually, the expected time to reach the terminal state in this simple Markov chain is asymptotic to $2^{k+1}$ by Wald's lemma.  
> **username_1**: Thanks, fixed it.  

---

