Pokryj czas i lukę spektralną dla odwracalnych losowych spacerów

Szukam twierdzenia, które mówi coś takiego: jeśli czas pokrycia odwracalnego łańcucha Markowa jest mały, to szczelina widmowa jest duża. Tutaj oznacza lukę widmową$1-|\lambda_2|$oznacza to, że ignorujemy najmniejszą wartość własną łańcucha.

Jedyny wynik, jaki udało mi się znaleźć w tym kierunku, to Bounds on the Cover Time , Broder i Karlin, FOCS 88. Zakłada się, że macierz przejściowa łańcucha jest podwójnie stochastyczna (ale niekoniecznie odwracalna) i aperiodyczna; z grubsza mówiąc, dokument pokazuje, że przy tych założeniach, jeśli czas pokrycia wynosi$O(n \log n)$, następnie $1-\max(|\lambda_2|, |\lambda_n|)$wynosi co najmniej .$n^{-1}$

Intuicyjnie wydaje się bardzo prawdopodobne, że jeśli można szybko pokryć wszystkie wierzchołki wykresu, czas mieszania powinien być krótki. W szczególności, jeśli możesz pokryć wszystkie wierzchołki wykresu w czasie , na pewno powinieneś być w stanie wykluczyć lukę spektralną, powiedzmy, ?$n^2$$n^{-1000}$

Jedną możliwą przeszkodą, która złamałaby implikację między małym czasem pokrycia a dużą luką widmową, jest dwudzielność: na grafie dwustronnym możesz mieć mały czas pokrycia o wartości własnej . W swoim pytaniu omijam ten problem, ignorując najmniejszą wartość własną.$-1$

Z grubsza rzecz biorąc, czas mieszania jest najgorszym przypadkiem uderzenia połowy wierzchołków. Czas przykrycia to czas zatrzymania, gdy trafione zostaną WSZYSTKIE podzbiory wierzchołków. Innymi słowy, zawsze jest dłuższy niż czas mieszania. Tak więc w twoim przykładzie nie można mieć czasu mieszania i czasu pokrycia . $n^{1000}$$n^2$

Doprecyzowanie tej intuicji wymaga nieco staranności, ponieważ musimy powiązać czasy mieszania z luką wartości własnej, nie zajmować połowy wierzchołków, ale połowę rozkładu stacjonarnego itp. Nie jest to trudne. Zacznij od tego artykułu autorstwa Lovasz i Winkler, który podaje powyższą wersję czasu mieszania i wiąże go z bardziej standardowym czasem mieszania w całkowitej zmienności. $\pi$