# Average vs Worst-Case Hitting Time

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

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)$.
• Could you explain why the maximal hitting time is around $3^k m$? – Pramod T. May 24 '15 at 6:52
• 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$). – Yuval Filmus May 24 '15 at 13:59