# Average and max. hitting time to a specific vertex [closed]

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

• – D.W.
Jul 21, 2022 at 3:57
• I’m voting to close this question because it was cross-posted.
– D.W.
Jul 21, 2022 at 3:57

The same question was asked at https://mathoverflow.net/questions/426969/average-and-max-hitting-time-to-a-specific-vertex

and for convenience, I reproduce the answer I just wrote there. Perhaps one of these copies will be removed eventually.

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. Then $$H(u,S)$$ in $$G$$ is 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.

• Thanks for the answer! Sorry for the double post, I posted the question also on Mathoverflow, but did not know it was not allowed. Jul 21, 2022 at 9:58