3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Your success condition seems ambiguous to me. Fix distinct vertices v and w, and call a sequence a Hamilton vw-envelope if it is a sequence of edges which contains a subsequence which is a Hamilton path from v to w. My guess is that you want to fix v and w and that you want a sequence which is a concatenation of n different Hamiltonian vw envelopes. Alternately, you might fix the path in advance and hope for it to repeat n times. Or do you mean something else? Gerhard "Ask Me About System Design" Paseman , 2011.10.18 $\endgroup$ – Gerhard Paseman Oct 18 '11 at 22:18
  • $\begingroup$ I cleared up the statement a bit. Hope it makes more sense now. $\endgroup$ – John Jiang Oct 18 '11 at 22:43
2
$\begingroup$

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)$

$\endgroup$
3
  • $\begingroup$ Thanks! The reason I said $n^4 \log n$ is because I was thinking about success with high probability (I think you need the log factor otherwise coupon collector won't work right?). But your first moment calculation definitely answers my question. $\endgroup$ – John Jiang Oct 18 '11 at 23:49
  • $\begingroup$ I think the $\log n$ is not needed. You're not actually doing coupon collector: waiting till you've seen every item in some collection. Instead the argument I have in mind is: fix an order; now each step of your success takes a geometric random variable with expectation $\approx n^2$ time. Since you're summing $n^2$ of these variables, the probability that it takes longer than twice the mean is outrageously small (again by LD estimates). This means you see any chosen order (in fact every order by an argument like before) in $\Theta(n^4)$ steps. $\endgroup$ – Anthony Quas Oct 18 '11 at 23:57
  • $\begingroup$ That's true too. I was thinking about the wrong analogy. Thx! $\endgroup$ – John Jiang Oct 19 '11 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.