6
$\begingroup$

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

$\endgroup$
3

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Great answer! Thanks a lot! $\endgroup$
    – fawadria
    Jul 21 at 10:00
  • $\begingroup$ 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. $\endgroup$
    – fawadria
    Jul 21 at 10:54
  • 1
    $\begingroup$ @fawadria Good point. In this case the extra edges only help the walker reach $S$ faster. I am adding this to the answer. $\endgroup$ Jul 21 at 16:41
  • 1
    $\begingroup$ @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)$. $\endgroup$ Jul 21 at 18:32
  • 1
    $\begingroup$ 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! $\endgroup$ Jul 21 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.