Random Cerny Conjecture
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&lt;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&lt;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 $k2^k$.