Caminhada aleatória e tempo médio de acerto em um gráfico simples e não direcionado

10

Seja um simples gráfico não direcionado em n vértices e m arestas.G=(V,E)nm

Eu estou tentando determinar o tempo de execução esperado de algoritmo de Wilson para a geração de uma árvore geradora aleatória de . Lá, é mostrado O ( τ ) , onde τ é o tempo médio de acerto : τ = v V π ( v ) H ( u , v ) , onde:GO(τ)τ

τ=vVπ(v)H(u,v),
  • é adistribuição estacionária π ( v ) = d ( v )π ,π(v)=d(v)2m
  • é um vértice arbitrário eu
  • é otempo de acerto(tempo deacessoAKA), ou seja, o número esperado de etapas antes davisitação dovértice v , iniciando no vértice u .H(u,v)vu

Qual é o limite superior geral para o tempo médio de acerto? E qual é o pior caso do gráfico que maximiza o tempo médio de acerto?G


Para deixar minha pergunta clara, não preciso de cálculos ou provas detalhadas (embora possam ser úteis para outras pessoas que encontrarem essa pergunta no futuro). Para mim, pessoalmente, uma citação seria suficiente.

Θ(n)Θ(nlogn)

Θ(n2)Θ(n3)O(n2)O(n3)

Existem duas implementações publicamente disponíveis do algoritmo de Wilson que eu conheço. Um está na Biblioteca de Gráficos Boost , enquanto o segundo está na ferramenta de gráficos . A documentação do primeiro não menciona o tempo de execução, enquanto o último afirma:

O(nlogn)

O que não responde à pergunta e, na verdade, parece ser inconsistente com o artigo de Wilson. Mas eu relato isso por precaução, para economizar tempo de alguém com a mesma idéia de consultar a documentação de implementação.

Ω(n3)1nO(n2)

4n3/2723n

arekolek
fonte
2
O(n)O(nlogn)
11
@Tiago Estou feliz em contribuir! Obrigado pelo seu comentário. Você também pode estar interessado em mencionar o tempo esperado na pior das hipóteses (por mais improvável), já que atualizei minha resposta com uma resposta de David Wilson.
arekolek

Respostas:

11

Decidi perguntar ao próprio David Wilson, logo em seguida, recebi uma resposta:

nΘ(n3)n/3n/3H(x,y)xyH(x,y)xyx

Existe até uma prova desse fato no livro mencionado, que é assim:

n=2n1+n2n1vlvLvRvrvLw1wn2vR

n1vL1n1w1n12w1w11n2n12n2

n1=n2=n/3O(n3)

É certo que estou perdido no ponto em que afirmam:

w11n2

(n+1)354

No entanto, comentários sobre a prova informal ainda são bem-vindos.

arekolek
fonte
3

Em um artigo recente , descobrimos um limite superior de mn (sem O grande) no número esperado de "ciclos disparados" pelo algoritmo de Wilson e ele é restrito a constantes. Ele não responde diretamente à questão do tempo de execução dos algoritmos de Wilson, já que o tamanho médio dos ciclos estourados não parece óbvio. Por outro lado, não tenho "reputação" suficiente para deixar um comentário ...

Heng Guo
fonte