Average and max. hitting time to a specific vertex

Question

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

Answer 1

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.