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 ...
3
Your question is essentially covered by Cor 9.5 in [1]
which implies that as long as the ratio of self-loops to the original degree is bounded above and below, the mixing time of this modified walk is equivalent (up to constants) to the mixing time of the lazy walk on $G_1$.
[1]
Peres, Yuval, and Perla Sousi. "Mixing times are hitting times of large ...
Only top voted, non community-wiki answers of a minimum length are eligible
