# Average and max. hitting time to a specific vertex

Consider simple random walks that stop when reaching a given node $$x$$ in an undirected, unweighted and connected graph on $$n$$ nodes. Let

• $$H(i,x)$$ denote the (expected) hitting time from $$i$$ to $$x$$, with $$H(x,x)=0$$.
• $$H_{\max} = \max_{i \in V} H(i,x)$$ and $$H_{\text{avg}} = \frac{1}{n}\sum_{i \in V} H(i,x)$$.

I am interested in the (asymptotic) largest possible ratio of $$\frac{H_{\max}}{H_{\text{avg}}}$$ in function of $$n$$. Similar to this question, but now considering the single-source variant w.r.t a specified node.

The worst example I was able to construct has ratio $$\Omega(n^{3/4})$$: Consider an $$n$$-star graph with center node $$x$$, attach to $$x$$ a lollipop graph of $$2n^{1/4}$$ vertices (i.e., a path of length $$n^{1/4}$$, attached with a clique of size $$n^{1/4}$$). So $$H_{\max} \approx n^{3/4}$$, and $$H_{\text{avg}} \approx \frac{n\cdot 1 +n^{1/4}\cdot n^{3/4}}{n} \in O(1),$$

since the average hitting time (over all the lollipop vertices) to $$x$$ is cubic in the size of the lollipop graph.

Are there any worse examples where $$\frac{H_{\max}}{H_{\text{avg}}}$$ is larger, perhaps even $$\Omega(n)$$?

• Nice question! It seems that the Barnes-Feige Theorem on exploration time is relevant. Jul 21 at 1:26
• – D.W.
Jul 21 at 3:57
• Sorry for the cross-post! Jul 21 at 10:04

Notation: Let $$G=(V,E)$$ be an undirected simple graph of $$n$$ nodes. If $$\tau_x$$ is the (random) time it takes the walk to reach the node $$x$$, then write $$H(v,x)=E_v(\tau_x)$$. Denote $$H_{\max}(x):=\max_{u \in V} H(u,x)$$ and $$H_{\rm avg}(x) =\frac1n\sum_{v \in V} H(v,x)$$.

Claim: $$H_{\max}(x) \le 2n^{3/4} H_{\rm avg}(x)$$ for all $$x$$.

Proof: Given $$M>0$$, define $$S=\{v \in V: H(v,x) \le M H_{\rm avg}(x) \},$$ where clearly $$n H_{\rm avg}(x) \ge \sum_{v \in S^c} H(v,x) \ge |S^c|\cdot M H_{\rm avg}(x) \,,$$ so $$|S^c| \le n/M.$$

Given a starting node $$u \in V$$, denote by $$\tau_{S}$$ the first time the random walk from $$u$$ visits $$S$$, and let $$H(u,S):=E_u[\tau_{S}]$$ be its expectation (which is $$0$$ if $$u \in S$$, the interesting case will be $$u \in S^c$$.)

Consider the graph $$G^*$$ on $$|S^c|+1$$ nodes, obtained from $$G$$ by contracting all nodes in $$S$$ to a single supernode $$s$$. To ensure $$G^*$$ is a simple graph, if $$w\in S^c$$ has several edges connecting it to $$S$$, we only keep one of these edges in $$G^*$$ connecting $$w$$ to $$s$$. Then for every $$w \in S^c$$ we have $$P_G(w,S) \ge P_{G^*}(w,s)$$. Thus we can couple the walks in $$G$$ and $$G^*$$ so that $$H(u,S)$$ in $$G$$ is at most the expected hitting time $$H^*(u,s)$$ in $$G^*$$ from $$u$$ to $$s$$, which is well known to be at most $$|S^c|^3$$. See, e.g., [1] for the slightly weaker bound $$(|S^c|+1)^3$$. In fact, one can multiply this upper bound by $$4/27+o(1)$$, see [2], but we will not worry about optimizing the constants. A related stronger result on exploration time is in [3].

Then the strong Markov property at time $$\tau_S$$ implies that $$H(u,x) \le H(u,S)+\max_{v \in S} H(v,x) \le (n/M)^3+M \cdot H_{\rm avg}(x)$$ $$\le \Bigl((n/M)^3+M\Bigr) \cdot H_{\rm avg}(x) \,. \tag{1}$$ (We may assume that $$H_{\rm avg}(x) \ge 1$$, otherwise $$G$$ is a star.)

To minimize the right hand side of $$(1)$$, without optimizing the constants, choose $$M=n^{3/4}$$. We conclude that $$\max_{u \in V} H(u,x) \le 2n^{3/4} \cdot H_{\rm avg}(x) \,. \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \Box$$

[1] https://www.yuval-peres-books.com/markov-chains-and-mixing-times/
https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf Proposition 10.16 page 134.

[2] Brightwell, Graham, and Peter Winkler. "Maximum hitting time for random walks on graphs." Random Structures & Algorithms 1, no. 3 (1990): 263-276.

[3] Barnes, Greg, and Uriel Feige. "Short random walks on graphs." In Proceedings of the Twenty-Fifth annual ACM symposium on Theory of computing, pp. 728-737. 1993. See Theorem 1.

• Great answer! Thanks a lot! Jul 21 at 10:00
• Just one question. The statement '$H(u,S)$ in $G$ is the expected hitting time $H^*(u,s)$ in $G^*$ from $u$ to $s$' is only correct when you take into account the number of edges that u has to S, if I am correct? That means that $G^*$ will be a multigraph, and I am not sure if this changes anything in the correctness of the proof. Jul 21 at 10:54
• @fawadria Good point. In this case the extra edges only help the walker reach $S$ faster. I am adding this to the answer. Jul 21 at 16:41
• @fawadria If we do not care about constants, then instead of contracting $G$, we can use Theorem 1 of the wonderful paper by Barnes-Feige [3], that ensures the expected time for the walk to encounter $k$ distinct vertices is $O(k^3)$. Jul 21 at 18:32
• Indeed. However, the Barnes-Feige theorem is deeper than the coupling argument I included in the answer. When I first heard of their theorem, I spent a whole day trying to prove it myself, and failed. The proof is quite ingenious! Jul 21 at 20:48