Я ищу теорему, которая говорит что-то вроде этого: если время накрытия обратимой цепи Маркова мало, то спектральная щель велика. Здесь спектральная щель означаетто есть мы игнорируем наименьшее собственное значение цепочки.
Единственный результат, который мне удалось найти в этом направлении, это « Границы времени покрытия» , Бродер и Карлин, FOCS 88. Там предполагается, что переходная матрица цепочки является вдвойне стохастической (но не обязательно обратимой) и апериодической; грубо говоря, в статье показано, что при этих предположениях, если время покрытия равно , то не меньше n ^ {- 1} .
Интуитивно кажется очень правдоподобным, что если вы можете быстро охватить все вершины графа, тогда время смешивания должно быть небольшим. В частности, если вы можете охватить все вершины графа за времени, наверняка вы сможете исключить спектральный разрыв, скажем, ?
Одним из возможных препятствий, которые могут нарушить связь между малым временем покрытия и большим спектральным разрывом, является двудольность: на двудольном графике вы можете иметь небольшое время покрытия с собственным значением . В моем вопросе я обхожу эту проблему, игнорируя наименьшее собственное значение.
источник