Timeline for Computing the pseudo-spectral gap
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 24, 2020 at 15:44 | comment | added | Kweku A | Also I don't think you can much improve that bound. Consider a `nearly periodic random walk': $j \to j+1 \mod n$ deterministically for $j\neq 0$, pausing at 0 with probability 1/2. The spectral gap is I think of order $1/n$ where $n$ is the number of elements in the state space (the characteristic polynomial is $(\lambda-1)(1+\lambda + ... + \lambda^{n-2} +2\lambda^{n-1})/2$; roots of the second factor are roughly 1/n perturbed from roots of unity) but $(P^*)^n P^n$ is roughly a matrix of 1s so has spectral gap $~1$. So you need to calculate up the $n$th term if you want precision $1/(2n)$. | |
| Jan 24, 2020 at 15:08 | comment | added | Kweku A | Old question I know but I found it interesting now. Your solution works with only the precision as an input, since if you calculate for $k\leq 1/\epsilon$ you get something within the right precision | |
| Jan 23, 2018 at 17:50 | comment | added | Aryeh Kontorovich | @LiorSilberman good point! Still, one might hope for a bound on $k$ that depends only on the desired precision $\epsilon$, and not on properties of $P$. After all, in "my solution", small $\delta$ requires large $k$... | |
| Jan 23, 2018 at 15:42 | comment | added | Lior Silberman | I meant that your remark was the solution,, not mine. | |
| Jan 23, 2018 at 15:38 | comment | added | Lior Silberman | This remark solves the problem (with no time bound): let $\delta$ be the value for $k=1$. Then it's enough to compute for $k\leq 1/\delta$. | |
| Jan 22, 2018 at 22:27 | history | answered | Aryeh Kontorovich | CC BY-SA 3.0 |