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)$?
 A: 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.
