Estou procurando um teorema que diga algo assim: se o tempo de cobertura de uma cadeia reversível de Markov é pequeno, então o intervalo espectral é grande. Aqui, o intervalo espectral significa, ou seja, ignoramos o menor autovalor da cadeia.
O único resultado que pude encontrar nessa direção é de Bounds on the Cover Time , Broder e Karlin, FOCS 88. Supõe-se que a matriz de transição da cadeia seja duplamente estocástica (mas não necessariamente reversível) e aperiódica; grosso modo, o artigo mostra que, sob essas suposições, se o tempo de cobertura for , então será pelo menos n ^ {- 1} .
Intuitivamente, parece muito plausível que, se você puder cobrir todos os vértices de um gráfico rapidamente, o tempo de mistura seja pequeno. Em particular, se você puder cobrir todos os vértices de um gráfico em , certamente poderá descartar uma lacuna espectral de, digamos, ?
Um possível obstáculo que interromperia a implicação entre o tempo de cobertura pequeno e o grande intervalo espectral é a bipartidade: em um gráfico bipartido, você pode ter um tempo de cobertura pequeno com um valor próprio de . Na minha pergunta, estou ignorando esse problema ignorando o menor valor próprio.
fonte