Pergunta técnica sobre passeios aleatórios

9

(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 G for bipartido? Eu estou interessado especificamente no tempo de bater hi,j , onde existe uma aresta entre i e j no G . Digamos que o gráfico bipartido G tenha m arestas. Podemos adicionar um auto-loop a um vértice arbitrário no gráfico para tornar o gráfico resultante G não bipartido; aplicando o teorema fundamental das cadeias de Markov a G obtemos então que hi,j<2m+1 em G, E isto é claramente também um limite superior para em L .hi,jG

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?hi,j<2mG

user686
fonte

Respostas:

5

Essa resposta provou ser diferente do que o interlocutor estava realmente interessado. Deixando-a aqui para que outros não repitam o mesmo erro.

Na maioria dos casos, pode-se justificar formalmente a noção intuitiva de que "auto-loops podem apenas desacelerar a caminhada" por um argumento de acoplamento. Nesse caso, por exemplo, pode-se acoplar a caminhada com auto-loops (vamos chamá-lo de ) e aquele sem auto-loops (vamos chamá-lo de B ), para que A tome os mesmos passos que B , mas com atraso no tempo. Isso pode, por exemplo, ser feito da seguinte maneira: Suponha que B comece em u = x 0 e passe por x i : i = 1 , 2 , , kABABBu=x0xi:i=1,2,,k. Agora, implementamos seguinte maneira: A também passa pelos mesmos vértices que B , exceto pelo vértice x i , que espera pelo tempo geométrico ( p i ) em que p i é a probabilidade do auto-loop em x i . Observe que esta é uma implementação correta de A (todas as probabilidades de transição estão corretas) e a forma do acoplamento garante que A nunca atinja nenhum vértice antes de B , ou seja, nós acoplamos H A t e H B tAABxipipixiAABHtAHtB (os tempos de acerto aleatórios nos dois passeios), de modo que com probabilidade 1 . Assim, a desigualdade para o tempo esperado de acerto segue.HtAHtB1

Piyush
fonte
Desculpe, mas acho que isso não responde à minha pergunta. Concordo que em G é o limite superior por h i , j em G ' , que por sua vez é o limite superior por 2 m + 1 . Mas gostaria de obter a mais forte que ligada h i , j em L é superior delimitada por 2 m . (OK, percebo que o " + 1 " não é grande coisa, mas, por outro lado, vi a reivindicação feita sem o " + 1hi,jGhi,jG2m+1hi,jG2m+1+1"E assim eu me pergunto se é tecnicamente precisa).
user686
@ user686 Você pode compartilhar a referência?
Tyson Williams
2

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 .)ijGh(i,j)ijh(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.ij

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 jijC(i,j)=h(i,j)+h(j,i)=2mR(i,j)R(i,j)ij1ijestã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)<2mijGh(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)ij

Piyush
fonte
Obrigado; se o resultado que você indicou também vale para gráficos bipartidos (vou verificar a referência que você forneceu), isso realmente responde à minha pergunta!
user686
0

@ 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+12mjiGGsamejH(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+1mhi,jΘ(m2)

PS: Atualizei minha resposta anterior, pois parece que não estava abordando sua principal preocupação.

Piyush
fonte
Por outro lado, 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 ) representa a resistência efectiva entre i e j em L , e é, no máximo, 1 . Isso mostra que hijC(i,j)=h(i,j)+h(j,i)=2mR(i,j)R(i,j)ijG1 em que i e j são adjacentes em L , uma vez que tanto h ( i , j ) e h ( j , i ) são estritamente positivo. h(i,j)<2mijGh(i,j)h(j,i)
Piyush 12/10
É bom (e às vezes melhor) manter a resposta mesmo quando ela estiver incorreta ou não responder à pergunta, para que outras pessoas não cometerão o mesmo erro; basta adicionar uma linha no início da resposta, explicando por que ela está incorreta ou não. Responda à pergunta. :)
Kaveh
@ Kaveh: Obrigado, sou novo aqui. Minha resposta anterior não estava incorreta, mas não respondeu o que o user686 considerou a questão importante.
Piyush
@ Piiyush: basta adicionar uma linha em negrito ao topo para ficar claro que não está respondendo à pergunta.
Kaveh