<p>No.</p>

<p>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)$.</p>

<p>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)$.</p>

CC BY-SA 3.0
2015-09-07T23:04:20.553Z
2015-09-07T23:04:20.553Z
Holden Lee
<p>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.</p>

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

<p>(i) the simple random walk on it has constant spectral gap?</p>

<p>(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$?</p>

<p>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$. </p>

<p>Do there exist positive constants $\alpha, \beta, c$ such that:</p>

<p>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$. </p>

<p>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$?</p>

<p>I suspect that this is not possible.</p>

CC BY-SA 3.0
2015-09-04T07:29:58.200Z
Should the graph be connected?  Otherwise $\pi$ is not well defined.
Stig Hemmer
CC BY-SA 3.0
2015-09-04T07:58:23.427Z
Connectivity follows from the bound on $\lambda_2(P)$.
Michael G
CC BY-SA 3.0
2015-09-07T23:05:02.507Z
What is the something that you're playing with?
Holden Lee
<graph-theory><pr.probability>
About a random walk with constant spectral gap
Michael G
# About a random walk with constant spectral gap

(Asked by: username_0 on 2015-08-31)

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.

**Tags:** graph-theory, pr.probability

> **Comments:**
> **username_1**: Should the graph be connected?  Otherwise $\pi$ is not well defined.  
> **username_0**: Connectivity follows from the bound on $\lambda_2(P)$.  
> **username_2**: What is the something that you're playing with?  

---

## 1 answers

### Answer by username_2 on 2015-09-07. Score: 1

No.

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


---

