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 Answers 2

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$
4
  • $\begingroup$ Could you explain why the maximal hitting time is around $3^k m$? $\endgroup$
    – Pramod T.
    May 24, 2015 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$ May 24, 2015 at 13:59
  • $\begingroup$ 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. $\endgroup$ Jul 21, 2022 at 3:54
  • $\begingroup$ Probably a mistake on my side. $\endgroup$ Jul 21, 2022 at 5:10
3
$\begingroup$

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)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.