Como se deve simular passeios aleatórios que evitam a auto-evitação?

Existe um método trivial para simular uma caminhada aleatória através de um gráfico, exponenciando uma matriz de adjacência estocástica, mas o problema se torna mais difícil se você solicitar que a caminhada aleatória seja auto-evitável. Em outras palavras, o processo deve percorrer o gráfico usando caminhos, como uma infecção ou algo assim.

Se as probabilidades da aresta são grandes, existe um algoritmo simples de Monte Carlo: em cada tentativa, você simplesmente exclui cada aresta com probabilidade 1 - p e , calcula os componentes conectados do novo gráfico e incrementa uma matriz de contagem por matrizes de 1s para cada componente contatado. Você divide pelo número de tentativas no final.$e$$1-p_e$

Alguém conhece algum algoritmo para fazer esse cálculo quando as probabilidades são muito pequenas?

Se o gráfico não estiver muito conectado, você poderá encontrar alguns conjuntos mínimos de cortes e fazer a exclusão e inclusão contando com eles, mas essa abordagem é duplamente exponencial no tamanho dos conjuntos de cortes. Também existem várias otimizações para casos específicos de alta conectividade, como tratar todos os subgráficos de clique separadamente por meio do cálculo óbvio. Alguma idéia mais geral?

Não tenho certeza se estou interpretando sua pergunta corretamente, mas parece-me que você está perguntando não sobre a simulação de passeios aleatórios que evitam a auto-evitação, mas sobre a enumeração de caminhadas aleatórias que evitam a auto-evitação. Digo isso porque você fala em exponenciar uma matriz de adjacência, que fornecerá uma enumeração (ponderada) de passeios aleatórios.

Não tenho certeza se existe muita literatura sobre a enumeração de passeios que evitam a auto-evitação em gráficos gerais; Acredito que a maior atenção foi focada em passeios que evitam a auto-evitação em treliças no espaço euclidiano, e é nisso que meus comentários abaixo se baseiam. Suspeito que muitas das idéias sejam transferidas para gráficos gerais.

A ferramenta clássica para reduzir o trabalho envolvido na enumeração exata de caminhadas que evitam a auto-evasão é a expansão das rendas. Você deve conseguir localizar facilmente a literatura relevante com essa palavra-chave. Para gráficos altamente conectados, no entanto, meu palpite é que a idéia de expansão de renda não ajudará muito (mas talvez nada ajude muito nesse caso).

Se você estiver satisfeito com a enumeração aproximada , existem algumas opções. Veja o artigo de 2009 de EJJ van Rensburg sobre "Enumeração aproximada de passeios que evitam a auto-evasão" para uma pesquisa. Veja também "Algoritmos de autoteste para caminhadas com auto-evitação" de Randall e Sinclair (2000).