# About a random walk with constant spectral gap

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.

• Should the graph be connected? Otherwise $\pi$ is not well defined. Sep 4, 2015 at 7:29
• Connectivity follows from the bound on $\lambda_2(P)$. Sep 4, 2015 at 7:58
• What is the something that you're playing with? Sep 7, 2015 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)$.