Deckungszeit und spektrale Lücke für reversible zufällige Spaziergänge

Ich suche nach einem Satz, der ungefähr so ​​lautet: Wenn die Bedeckungszeit einer reversiblen Markov-Kette klein ist, ist die spektrale Lücke groß. Hier bedeutet die spektrale Lücke $1-|\lambda_2|$Das heißt, wir ignorieren den kleinsten Eigenwert der Kette.

$O(n \log n)$$1-\max(|\lambda_2|, |\lambda_n|)$$n^{-1}$

Intuitiv erscheint es sehr plausibel, dass die Mischzeit kurz sein sollte, wenn Sie alle Eckpunkte eines Diagramms schnell abdecken können. Insbesondere wenn Sie alle Eckpunkte eines Graphen in Zeit abdecken können , sollten Sie sicherlich in der Lage sein, eine spektrale Lücke von beispielsweise auszuschließen .$n^2$$n^{-1000}$

Ein mögliches Hindernis, das die Implikation zwischen kleiner Abdeckungszeit und großer spektraler Lücke aufheben würde, ist die Zweiteiligkeit: In einem zweigeteilten Graphen können Sie eine kleine Abdeckungszeit mit einem Eigenwert von . In meiner Frage umgehe ich dieses Problem, indem ich den kleinsten Eigenwert ignoriere.$-1$

Grob gesagt ist die Mischzeit die schlechteste Schlagzeit der Hälfte der Eckpunkte. Die Deckungszeit ist eine Stoppzeit, wenn ALLE Teilmengen von Eckpunkten getroffen werden. Mit anderen Worten ist es immer größer als die Mischzeit. In Ihrem Beispiel kann man also keine Mischzeit und keine Deckzeit . $n^{1000}$$n^2$

$\pi$