(Minha pergunta original ainda não foi respondida. Adicionei mais esclarecimentos.)
Ao analisar passeios aleatórios (em gráficos não direcionados), visualizando o passeio aleatório como uma cadeia de Markov, exigimos que o gráfico seja não bipartido, para que o teorema fundamental das cadeias de Markov se aplique.
O que acontece se o gráfico for bipartido? Eu estou interessado especificamente no tempo de bater , onde existe uma aresta entre e no . Digamos que o gráfico bipartido tenha arestas. Podemos adicionar um auto-loop a um vértice arbitrário no gráfico para tornar o gráfico resultante não bipartido; aplicando o teorema fundamental das cadeias de Markov a obtemos então que em , E isto é claramente também um limite superior para em L .
Pergunta: É verdade que a afirmação mais forte aplica a G ? (Isso já foi afirmado nas análises do algoritmo de caminhada aleatória para 2SAT.) Ou será que realmente precisamos passar por essa etapa extra de adicionar o auto-loop?
fonte
Eu tinha postado isso como um comentário antes, e acredito que responde afirmativamente à pergunta modificada de user686 (quando e j são conectados por uma aresta de um gráfico G (independentemente de ser bipartido ou não), h ( i , j ) , o tempo de acerto esperado de i a j satisfaz h ( i , j ) < 2 m .)i j G h(i,j) i j h(i,j)<2m
Gostaria também de salientar que, em sua versão não editada original, a questão não afirmou que e j são adjacentes, por isso, enquanto as respostas anteriores são relevantes para a questão original, eles não são relevantes para a nova versão editada.i j
Se e j são adjacentes, o tempo de deslocamento C ( i , j ) = h ( i , j ) + h ( j , i ) = 2 m R ( i , j ) , onde R ( i , j ) é o efetivo resistência entre i e j em L, e é no máximo de 1 (uma vez que i e ji j C(i,j)=h(i,j)+h(j,i)=2mR(i,j) R(i,j) i j 1 i j estão conectados por uma borda). Isso mostra que quando i e j são adjacentes em G , uma vez que h ( i , j ) e h ( j , i ) são estritamente positivos.h(i,j)<2m i j G h(i,j) h(j,i)
A identidade de é válido para vértices arbitrárias i e j . Uma prova aparece, por exemplo, no livro de Lyons e Peres.C(i,j)=2mR(i,j) i j
fonte
@ user686 Desculpe, pela minha resposta anterior: não sabia que você estava preocupado com vs 2 m . No entanto, nesse caso, não acho que a afirmação feita lá seja verdadeira se você adicionar um auto loop apenas em j . Passeios aleatórios a partir de i , no caso de ambos G ' e e L pode ser acoplada de modo a que estes tomem as s um m e passos nos mesmos tempos, até que eles atinjam j . Isso significa que H ( i , j ) G = H ( i ,2m+1 2m j i G′ G same j H(i,j)G=H(i,j)G′ , e os tempos esperados de acerto, portanto, devem ser iguais.
Além disso, como o limite não está correto em geral (em um caminho de m nós, h i , j pode ser tão grande quanto Θ ( m 2 ) ), seu gráfico é especial?hi,j<2m+1 m hi,j Θ(m2)
PS: Atualizei minha resposta anterior, pois parece que não estava abordando sua principal preocupação.
fonte