Consider the complete graph on $n$ vertices. Each step, one chooses one of the $\binom{n}{2}$ edges iid uniformly at random. Say a sequence of choice is successful if there is some permutation of the vertices $[n]$, $i_1,i_2, \ldots, i_n$, such taht the sequence contains a subsequence of the following form: $(i_1,i_2),(i_2,i_3), \ldots (i_{n-1},i_n)$ repeated $n$ times. So $\Theta(n^4 \log n)$ steps are certainly sufficient for the random sequence to be successful. Can one reduce it to $\mathcal{O}(n^3 \log n)$?

edit: Thanks to Gerhard for clearing ambiguity of the original statement.