Tiempo de cobertura y espacio espectral para caminatas aleatorias reversibles

Estoy buscando un teorema que diga algo como esto: si el tiempo de cobertura de una cadena de Markov reversible es pequeño, entonces la brecha espectral es grande. Aquí la brecha espectral significa, es decir, ignoramos el valor propio más pequeño de la cadena.$1-|\lambda_2|$

El único resultado que pude encontrar en esta dirección es de Bounds on the Cover Time , Broder y Karlin, FOCS 88. Allí se supone que la matriz de transición de la cadena es doblemente estocástica (pero no necesariamente reversible) y aperiódica; en términos generales, el documento muestra que, bajo estos supuestos, si el tiempo de cobertura es , entonces es al menos n ^ {- 1} .$O(n \log n)$$1-\max(|\lambda_2|, |\lambda_n|)$$n^{-1}$

Intuitivamente, parece muy plausible que si puedes cubrir todos los vértices de un gráfico rápidamente, el tiempo de mezcla debería ser pequeño. En particular, si puede cubrir todos los vértices de un gráfico en $n^2$ tiempo, seguramente debería ser capaz de descartar una brecha espectral de, digamos, $n^{-1000}$ .

Un posible obstáculo que rompería la implicación entre un tiempo de cobertura pequeño y un gran espacio espectral es la bipartita: en un gráfico bipartito, puede tener un tiempo de cobertura pequeño con un valor propio de $-1$ . En mi pregunta, estoy evitando este problema al ignorar el valor propio más pequeño.

Hablando en términos generales, el tiempo de mezcla es el peor momento de golpe de la mitad de los vértices. El tiempo de cobertura es un tiempo de detención cuando TODOS los subconjuntos de vértices son golpeados. En otras palabras, siempre es mayor que el tiempo de mezcla. Por lo tanto, este es su ejemplo: uno no puede tener el tiempo de mezcla y el tiempo de cobertura . $n^{1000}$$n^2$

Hacer que esta intuición sea precisa requiere un poco de cuidado, ya que necesitamos relacionar los tiempos de mezcla con el espacio de valor propio, tomar no la mitad de los vértices sino la mitad de la distribución estacionaria , etc. Nada de esto es difícil. Comience con este documento de Lovasz y Winkler, que proporciona la versión anterior del tiempo de mezcla y la relaciona con un tiempo de mezcla más estándar en variación total. $\pi$