Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
If $n\rightarrow \infty$ and $\mu=\mu(n)\rightarrow \infty$ as $n\rightarrow \infty$ and $\omega=\omega(n)\rightarrow \infty$ as $n\rightarrow \infty$ , then can we say, by rescaling that $\lim_{n\rightarrow \infty}\frac{m(\omega\mu)}{\omega\mu} = \frac{1}{\mu}$ and thus $m(\omega\mu)\sim \omega$? Intuitively this would make sense, but seems a little too easy
Shai, thanks for this very nice answer. I am not familiar with renewal theory (my user name is somewhat ironic), but if for my purposes I am happy to let K→∞, then m(K)∼K/μ and so $E(Y_\tau)\sim (1+K/\mu)\mu= O(K)$ when $K>\mu$. This would solve the related problem that I posted here mathoverflow.net/questions/50137/… when we allow the cover time C (which is equivalent to K here) to go to ∞, which of course, is the case for for all graphs as their size goes to $\infty$.
The problem is that it doesn't seem to be true that the final round of blanketing actually has an expectation $O(C)$. What we are talking about is a series of jumps on the number line until we cross $K=C/\delta$, and we want to know what in the final jump, the value $t-K=O(C)$. However, as can be seen from the second counter example in the link to my previous question - this is not necessarily the case.
