The existence of a graph with certain strange-looking properties will imply a counterexample to something I am playing with. I'm stuck on figuring out whether such a graph can exist and so I thought I'd post it here as question.

Specifically, for any integer $n$, is it always possible to construct an undirected graph on $n$ nodes such that:

(i) the simple random walk on it has constant spectral gap?

(ii) there exist two vertices $i,j$ such that the stationary distribution at both of them is lower bounded by a constant and the hitting time from $i$ to $j$ is at least linear in $n$?

More formally, the question is as follows. Given an undirected graph $G$, the simple random walk is the Markov chain which transitions to a uniformly random out-neighbor at each step. Let $P$ be its probability transition matrix and $\pi$ be its stationary distribution, i.e, $\pi^T P = \pi^T$.

Do there exist positive constants $\alpha, \beta, c$ such that:

i) For each $n$, there exists an undirected graph on $n$ vertices for which the corresponding matrix $P$ satisfies $\lambda_2(P) \leq 1-\alpha$.

ii) In the same graph, there exist nodes $i,j$ such that $\pi_i \geq \beta$, $\pi_j \geq \beta$ and the hitting time from $i$ to $j$ is at least $cn$?

I suspect that this is not possible.

  • $\begingroup$ Should the graph be connected? Otherwise $\pi$ is not well defined. $\endgroup$ – Stig Hemmer Sep 4 '15 at 7:29
  • $\begingroup$ Connectivity follows from the bound on $\lambda_2(P)$. $\endgroup$ – Michael G Sep 4 '15 at 7:58
  • $\begingroup$ What is the something that you're playing with? $\endgroup$ – Holden Lee Sep 7 '15 at 23:05


First we have the standard bound for how close the distribution is to stationary after $t$ steps. Letting $v$ be the initial distribution, we have (I write my matrices on the left) $||(P^tv)_i-(P^t\pi)_i||\le ||P^tv-P^t\pi||_1\le \sqrt n ||P^t(v-\pi)||_2\le \sqrt n \lambda_2^n\sqrt n=n\lambda_2^t$ which is $\le \epsilon$ for $t=\log_{1/\lambda_2}(n/\epsilon)$.

Assume (i) and (ii) hold. So starting from $i$ (or any probability distribution), there is a $\ge \beta - \epsilon$ chance that it hits $j$ on the $\log_{1/\lambda_2}(n/\epsilon)=O_{\lambda_2,\epsilon}(\log n)$th step. If it hasn't hit, there is another $\beta - \epsilon$ chance it will hit in the next so many steps. The expected hitting time is at most $\sum_{m=1}^{\infty}(1-\beta+\epsilon)^{m-1}(\beta-\epsilon) mO_{\lambda_2,\epsilon}(\log n)=O_{\lambda_2,\epsilon,\beta}(\log n)$.


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.