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.



Bounding the success time of a coupon collector like problem
I think $n^4$ steps are sufficient: wait for (1,2) [ $n^2$ steps ]; then wait for (2,3); then (3,4); ... You're summing $n^2$ geometric random variables with parameter $1/\binom{n}{2}\approx 1/n^2$, so the expected time for success this way is $\Theta(n^4)$. Might you do better if you choose a different sequence? I don't think so - for any fixed sequence $i\_1,\ldots,i\_n$, the probability of getting done in half the expected time is by large deviations estimates $O(e^{-\gamma n^2})$. Since there are $n!$ orders, the probability that there is any sequence that will get you done in half the expected time is $o(1)$


