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](https://cs.stackexchange.com/questions/42917/average-vs-worst-case-hitting-time) 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)$?



Average and max. hitting time to a specific vertex
**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.


