1
$\begingroup$

I'm completely stuck on Problem 4.10 of the Motwani-Raghavan Randomized Algorithms textbook. I don't want an answer, but hints may be helpful here. I understand the general Valiant scheme for the boolean hypercube but am unable to generalize to an arbitrary regular graph:

"Suppose we run Valiant’s scheme on an N-node network in which every node is of degree d; each packet first goes to a random destination chosen uniformly from all the nodes and then on to its final destination. Show that the expected number of steps for the completion of the first phase is $ \Omega\left(\frac{\log N}{d \log \log N} + \frac{\log N}{\log d}\right) $."

I understand that the diameter of any $d$-regular graph is always $O(N/d)$, but am not sure how the analysis would still work in this case as for the hypercube.

I have a feeling that the first term relates to the coupon collector's problem, but am completely unaware of how to get the second term.

Edit: Yuval in the comments essentially has a "workaround" proof that works, but isn't related to the scheme itself, and seems very unintended by the book authors. Is there another solution?

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you copied the expression correctly? Since $d \log\log N = \Omega(\log d)$, the expression is actually the same as $\Omega\left(\frac{\log N}{\log d}\right)$. $\endgroup$
    – Yuval Filmus
    Commented Sep 18, 2016 at 15:57
  • $\begingroup$ The bound $\Omega\left(\frac{\log N}{\log d}\right)$ follows from the fact that there are at most (roughly) $d^t$ nodes at distance at most $t$ from any given node. $\endgroup$
    – Yuval Filmus
    Commented Sep 18, 2016 at 15:57
  • $\begingroup$ @YuvalFilmus Yes I have copied it correctly. $\endgroup$
    – Bob
    Commented Sep 18, 2016 at 17:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.