4
$\begingroup$

Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can $$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to $$ H_{\rm ave} = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n H_{ij}.$$ For all the examples I can think of, these two quantities are of roughly the same order of magnitude.

To make this into a formal question, define $$\phi(n) = \max_{\mbox{undirected graphs with } n \mbox{ nodes }} \frac{H_{\rm max}}{H_{\rm ave}}.$$ How fast does $\phi(n)$ grow with $n$?

$\endgroup$
2
$\begingroup$

The quantity $\phi(n)$ grows like $\Theta(n)$.

For the lower bound, consider the following graph: a clique on $m$ vertices connected to a path of length $k = C\log m$ for an appropriate $C$ (so $n = m + k \approx m$), in which each vertex of the path is also connected to the first vertex of the path (the one incident to the clique). The maximal hitting time is some large number $M = \exp(k)$. The hitting time of two vertices in the clique is around $m \ll M$. The hitting time of a vertex on the path and any other vertex is at most $M$. So the average hitting time is at most roughly $m + \frac{2kn}{n^2} M = O(kM/n)$. In fact, the hitting time of a vertex at distance $t$ from the clique is roughly $\exp(t)$ (for $t \gg \log m$), and if we take this into account then we get an average hitting time of roughly $m + \sum_{t=1}^k \frac{2n}{n^2} \exp(t) = O(M/n)$. This shows that $\phi(n) = \Omega(n)$.

For the upper bound, let $H_{ij}$ be the maximum hitting time. The triangle inequality shows that for each $k$, either $H_{ik} \geq H_{ij}/2$ or $H_{kj} \geq H_{ij}/2$. So at least $n/2$ of the hitting times are at least $H_{ij}$, showing that the average hitting time is at least $H_{ij}/n$. This shows that $\phi(n) = O(n)$.

$\endgroup$
  • $\begingroup$ Could you explain why the maximal hitting time is around $3^k m$? $\endgroup$ – Pramod T. May 24 '15 at 6:52
  • $\begingroup$ This particular number could be wrong, but the maximal hitting time should be large. I got $3^km$ since in order to get to the end of the path, you must go towards the end of the path $k$ times in a row. Each time you go to the clique you take time $m$ to try again. This doesn't quite give $3^km$, but the exact number isn't important as long as it's much larger than $m$ (and exponential in $k$). $\endgroup$ – Yuval Filmus May 24 '15 at 13:59

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.