Tempo de cobertura e intervalo espectral para passeios aleatórios reversíveis

9

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.1 1-|λ2|

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} .O(nregistron)1 1-max(|λ2|,|λn|)n-1 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 n2 , certamente poderá descartar uma lacuna espectral de, digamos, n-1000 ?

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 -1 1 . Na minha pergunta, estou ignorando esse problema ignorando o menor valor próprio.

Robinson
fonte

Respostas:

4

Grosso modo, o tempo de mixagem é o pior dos tempos da metade dos vértices. O tempo de cobertura é um tempo de parada quando TODOS os subconjuntos de vértices são atingidos. Em outras palavras, é sempre maior que o tempo de mistura. Assim é o seu exemplo: não se pode ter o tempo de mistura e o tempo de cobertura . n1000n2

Tornar essa intuição precisa exige um pouco de cuidado, pois precisamos relacionar os tempos de mistura com a diferença de autovalor, tomar não metade dos vértices, mas metade da distribuição estacionária , etc. Nada disso é difícil. Comece com este artigo de Lovasz e Winkler, que fornece a versão acima do tempo de mistura e a relaciona ao tempo de mistura mais padrão na variação total. π

Igor Pak
fonte