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.

Improve this question
$\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
    Commented Oct 18, 2011 at 22:18
  • $\begingroup$ I cleared up the statement a bit. Hope it makes more sense now. $\endgroup$
    – John Jiang
    Commented Oct 18, 2011 at 22:43

1 Answer 1

Reset to default
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)$

Improve this answer
$\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
    Commented Oct 18, 2011 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
    Commented Oct 18, 2011 at 23:57
  • $\begingroup$ That's true too. I was thinking about the wrong analogy. Thx! $\endgroup$
    – John Jiang
    Commented Oct 19, 2011 at 0:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .