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ą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, następnie wynosi co najmniej .
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, ?
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ą.
źródło