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

9

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-|λ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 wynosiO(nlogn), następnie 1-max(|λ2)|,|λ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, ?n2)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

robinson
źródło

Odpowiedzi:

4

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

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. π

Igor Pak
źródło