HiveBrain v1.2.0
Get Started
← Back to all entries
principleMinor

Average vs Worst-Case Hitting Time

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
casehittingaveragetimeworst

Problem

Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can
$$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to
$$ H_{\rm ave} = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n H_{ij}.$$ For all the examples I can think of, these two quantities are of roughly the same order of magnitude.

To make this into a formal question, define
$$\phi(n) = \max_{\mbox{undirected graphs with } n \mbox{ nodes }} \frac{H_{\rm max}}{H_{\rm ave}}.$$ How fast does $\phi(n)$ grow with $n$?

Solution

This is an addendum to the answer by Yuval Filmus. Indeed $\phi(n)=\Theta(n)$, and the upper bound is explained in that answer. I don't understand the argument for the lower bound given there, but a simpler graph will yield the required bound. Let $G$ consist of a clique of $n-1$ vertices, where one of them, say $x$, is connected to one additional vertex called $y$. Let $f(v):= E_v \tau_y=H(v,y)$ denote the expected hitting time from $v$ to $y$. Then, by conditioning on the first step and using symmetry,
$$ \forall v\notin\{x,y\}, \quad f(v)=1+\frac1{n-2} f(x) +\frac{n-3}{n-2} f(v)$$
and
$$f(x)=1+\frac{n-2}{n-1} f(v) \,.$$
Solving these linear equations gives $f(v)=(n-1)^2$ and $f(x)=n^2-3n+3$.
On the other hand, only $n-1$ of the $n(n-1)$ mean hitting times are of order $n^2$,
(namely when the target is $y$). The mean hitting time of every target vertex in the clique is less than $2n$, so $H_{\rm ave}=O(n)$.

Context

StackExchange Computer Science Q#42917, answer score: 3

Revisions (0)

No revisions yet.