Время покрытия и спектральный разрыв для обратимых случайных блужданий

9

Я ищу теорему, которая говорит что-то вроде этого: если время накрытия обратимой цепи Маркова мало, то спектральная щель велика. Здесь спектральная щель означаетто есть мы игнорируем наименьшее собственное значение цепочки.1-|λ2|

Единственный результат, который мне удалось найти в этом направлении, это « Границы времени покрытия» , Бродер и Карлин, FOCS 88. Там предполагается, что переходная матрица цепочки является вдвойне стохастической (но не обязательно обратимой) и апериодической; грубо говоря, в статье показано, что при этих предположениях, если время покрытия равно , то не меньше n ^ {- 1} .О(NжурналN)1-Максимум(|λ2|,|λN|)N-1

Интуитивно кажется очень правдоподобным, что если вы можете быстро охватить все вершины графа, тогда время смешивания должно быть небольшим. В частности, если вы можете охватить все вершины графа за N2 времени, наверняка вы сможете исключить спектральный разрыв, скажем, N-1000 ?

Одним из возможных препятствий, которые могут нарушить связь между малым временем покрытия и большим спектральным разрывом, является двудольность: на двудольном графике вы можете иметь небольшое время покрытия с собственным значением . В моем вопросе я обхожу эту проблему, игнорируя наименьшее собственное значение.-1

Robinson
источник

Ответы:

4

Грубо говоря, время смешивания - это время попадания в половину вершин в худшем случае. Время покрытия - это время остановки, когда ВСЕ подмножества вершин поражены. Другими словами, оно всегда больше, чем время смешивания. Таким образом, в вашем примере нельзя смешивать время и время покрытия . N1000N2

Чтобы сделать эту интуицию точной, нужно немного позаботиться, так как нам нужно связать время смешивания с промежутком собственных значений, взять не половину вершин, а половину стационарного распределения и т. Д. Ничего из этого не сложно. Начните с этой статьи Ловаша и Винклера, которая дает приведенную выше версию времени смешивания и соотносит ее с более стандартным временем смешивания в общей вариации. π

Игорь Пак
источник