# 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$? May 24, 2015 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$). May 24, 2015 at 13:59
• I don't understand where the exponential hitting time comes from. It cannot be the case for large $C$, as hitting time between two nodes at distance $k$ is always at most $kn^2$ by the commute time formula. Note that when you add edges connecting every vertex to the vertex adjacent to the clique, these edges can be used in both directions. I do agree with the conclusion, and the lower bound can be simplified by just having a single edge outside the clique. Jul 21, 2022 at 3:54
This is an addendum to the answer by Yuval Filmus. Indeed $$\phi(n)=\Theta(n)$$, and the upper bound is explained in that answer. I don't understand the argument for the lower bound given there, but a simpler graph will yield the required bound. Let $$G$$ consist of a clique of $$n-1$$ vertices, where one of them, say $$x$$, is connected to one additional vertex called $$y$$. Let $$f(v):= E_v \tau_y=H(v,y)$$ denote the expected hitting time from $$v$$ to $$y$$. Then, by conditioning on the first step and using symmetry, $$\forall v\notin\{x,y\}, \quad f(v)=1+\frac1{n-2} f(x) +\frac{n-3}{n-2} f(v)$$ and $$f(x)=1+\frac{n-2}{n-1} f(v) \,.$$ Solving these linear equations gives $$f(v)=(n-1)^2$$ and $$f(x)=n^2-3n+3$$. On the other hand, only $$n-1$$ of the $$n(n-1)$$ mean hitting times are of order $$n^2$$, (namely when the target is $$y$$). The mean hitting time of every target vertex in the clique is less than $$2n$$, so $$H_{\rm ave}=O(n)$$.