Passeio aleatório apagado por loop - Loop-erased random walk

Em matemática , o passeio aleatório apagado por loop é um modelo para um caminho aleatório simples com aplicações importantes em combinatória e, em física , na teoria quântica de campos . Ele está intimamente conectado à árvore de abrangência uniforme , um modelo para uma árvore aleatória . Veja também passeio aleatório para um tratamento mais geral deste tópico.

Definição

Suponha L é um gráfico e é algum caminho de comprimento N em G . Em outras palavras, são vértices de G tais que e são conectados por uma aresta. Em seguida, o apagamento de loop de é um novo caminho simples criado ao apagar todos os loops de em ordem cronológica. Formalmente, definimos índices indutivamente usando ${\ displaystyle \ gamma}$${\ displaystyle \ gamma (1), \ dots, \ gamma (n)}$${\ displaystyle \ gamma (i)}$${\ displaystyle \ gamma (i + 1)}$${\ displaystyle \ gamma}$${\ displaystyle \ gamma}$${\ displaystyle i_ {j}}$

${\ displaystyle i_ {1} = 1 \,}$

${\ displaystyle i_ {j + 1} = \ max \ {i: \ gamma (i) = \ gamma (i_ {j}) \} + 1 \,}$

onde "max" aqui significa até o comprimento do caminho . A indução pára quando para alguns temos . Suponha que isso aconteça em J, ou seja, é o último . Então, o apagamento de loop de , denotado por, é um caminho simples de comprimento J definido por ${\ displaystyle \ gamma}$${\ displaystyle i_ {j}}$${\ displaystyle \ gamma (i_ {j}) = \ gamma (n)}$${\ displaystyle i_ {J}}$${\ displaystyle i_ {j}}$${\ displaystyle \ gamma}$${\ displaystyle \ mathrm {LE} (\ gamma)}$

${\ displaystyle \ mathrm {LE} (\ gamma) (j) = \ gamma (i_ {j}). \,}$

Agora seja G algum gráfico, seja v um vértice de G e seja R um passeio aleatório em G começando de v . Deixe- T haver algum tempo de parada para R . Em seguida, o passeio aleatório apagado por loop até que o tempo T seja LE ( R ([1, T ])). Em outras palavras, pegue R do início até T  - esse é um caminho (aleatório) - apague todos os loops em ordem cronológica como acima - você obterá um caminho simples aleatório.

O tempo de parada T pode ser fixo, ou seja, pode-se executar n passos e então apagar o loop. No entanto, geralmente é mais natural considerar T como o tempo de rebatida em algum conjunto. Por exemplo, seja G o gráfico Z ² e seja R um passeio aleatório a partir do ponto (0,0). Seja T o momento em que R atinge pela primeira vez o círculo de raio 100 (queremos dizer aqui, é claro, um círculo discretizado ). LE ( R ) é chamado de passeio aleatório apagado por loop começando em (0,0) e parado no círculo.

Árvore de abrangência uniforme

Para qualquer grafo G , uma árvore geradora de G é um subgrafo de G contendo todos os vértices e algumas das arestas, que é uma árvore , ou seja, conectada e sem ciclos . Uma árvore geradora escolhida aleatoriamente entre todas as árvores geradoras possíveis com igual probabilidade é chamada de árvore geradora uniforme. Normalmente, há muitas árvores abrangentes exponencialmente (muitas para gerá-las todas e, em seguida, escolher uma aleatoriamente); em vez disso, árvores abrangentes uniformes podem ser geradas de maneira mais eficiente por um algoritmo chamado algoritmo de Wilson, que usa caminhadas aleatórias apagadas por loop.

O algoritmo prossegue de acordo com as etapas a seguir. Primeiro, construa uma árvore T de vértice único escolhendo (arbitrariamente) um vértice. Então, enquanto a árvore T construída até agora ainda não inclui todos os vértices do gráfico, seja v um vértice arbitrário que não está em T , execute um passeio aleatório apagado por loop de v até chegar a um vértice em T , e adicionar o caminho resultante para T . Repetir esse processo até que todos os vértices sejam incluídos produz uma árvore uniformemente distribuída, independentemente das escolhas arbitrárias de vértices em cada etapa.

Uma conexão na outra direção também é verdadeira. Se v e w são dois vértices em G , então, em qualquer árvore estendida, eles são conectados por um caminho único. Seguir esse caminho na árvore de abrangência uniforme fornece um caminho simples aleatório. Acontece que a distribuição desse caminho é idêntica à distribuição do passeio aleatório apagado por loop começando em v e parado em w . Este fato pode ser usado para justificar a correção do algoritmo de Wilson. Outro corolário é que o passeio aleatório apagado por loop é simétrico em seus pontos inicial e final. Mais precisamente, a distribuição do passeio aleatório apagado por loop começando em v e parado em w é idêntica à distribuição da reversão do passeio aleatório apagado por loop começando em w e parado em v . O apagamento de um passeio aleatório e o passeio reverso não dão, em geral, o mesmo resultado, mas de acordo com esse resultado as distribuições dos dois passeios apagados de um laço são idênticas.

O passeio aleatório Laplaciano

Outra representação de passeio aleatório apagado por loop deriva de soluções da equação de Laplace discreta . Vamos G voltar a ser um gráfico e deixe v e w haver dois vértices em G . Construa um caminho aleatório de v para w indutivamente usando o procedimento a seguir. Suponha que já definimos . Seja f uma função de G para R satisfazendo ${\ displaystyle \ gamma (1), ..., \ gamma (n)}$

${\ displaystyle f (\ gamma (i)) = 0}$para todos e${\ displaystyle i \ leq n}$${\ displaystyle f (w) = 1}$

f é discretamente harmônico em qualquer outro lugar

Onde uma função f em um gráfico é discretamente harmônica em um ponto x se f ( x ) é igual à média de f nos vizinhos de x .

Com f definido, escolha usando f nos vizinhos de como pesos. Em outras palavras, se são esses vizinhos, escolha com probabilidade ${\ displaystyle \ gamma (n + 1)}$${\ displaystyle \ gamma (n)}$${\ displaystyle x_ {1}, ..., x_ {d}}$${\ displaystyle x_ {i}}$

${\ displaystyle {\ frac {f (x_ {i})} {\ sum _ {j = 1} ^ {d} f (x_ {j})}}.}$

Continuando este processo, recalculando f a cada etapa, resultando em um caminho simples aleatório de v para w ; a distribuição desse caminho é idêntica à de um passeio aleatório apagado por loop de v para w .

Uma visão alternativa é que a distribuição de um passeio aleatório apagado de loop condicionado para começar em algum caminho β é idêntica ao apagamento de um passeio aleatório condicionado para não atingir β. Essa propriedade é freqüentemente referida como a propriedade de Markov do passeio aleatório apagado por loop (embora a relação com a propriedade de Markov usual seja um tanto vaga).

É importante notar que, embora a prova da equivalência seja bastante fácil, os modelos que envolvem funções ou medidas harmônicas que mudam dinamicamente são tipicamente extremamente difíceis de analisar. Praticamente nada se sabe sobre a caminhada p-Laplaciana ou agregação limitada por difusão . Outro modelo um tanto relacionado é o explorador de harmônicos .

Finalmente, há outro link que deve ser mencionado: o teorema de Kirchhoff relaciona o número de árvores geradoras de um grafo G aos autovalores do Laplaciano discreto . Consulte a árvore de abrangência para obter detalhes.

Grades

Seja d a dimensão, que assumiremos ser pelo menos 2. Examine Z ^d, isto é, todos os pontos com inteiro . Este é um gráfico infinito com grau 2 d quando você conecta cada ponto a seus vizinhos mais próximos. De agora em diante, consideraremos um passeio aleatório apagado por loop neste gráfico ou em seus subgráficos. ${\ displaystyle (a_ {1}, ..., a_ {d})}$${\ displaystyle a_ {i}}$

Dimensões altas

O caso mais fácil de analisar é a dimensão 5 e acima. Nesse caso, verifica-se que lá as interseções são apenas locais. Um cálculo mostra que se alguém fizer um passeio aleatório de comprimento n , seu apagamento de loop terá comprimento da mesma ordem de magnitude, ou seja, n . Escalando de acordo, verifica-se que o passeio aleatório apagado por loop converge (em um sentido apropriado) para o movimento browniano conforme n vai para o infinito. A dimensão 4 é mais complicada, mas o quadro geral ainda é verdadeiro. Acontece que o apagamento do laço de um passeio aleatório de comprimento n tem aproximadamente vértices, mas novamente, após o escalonamento (que leva em consideração o fator logarítmico) o trajeto apagado do laço converge para o movimento browniano. ${\ displaystyle n / \ log ^ {1/3} n}$

Duas dimensões

Em duas dimensões, argumentos da teoria de campo conforme e resultados de simulação levaram a uma série de conjecturas interessantes. Suponha D é alguns simplesmente ligado domínio no plano e x é um ponto em D . Considere o gráfico G como sendo

${\ displaystyle G: = D \ cap \ varepsilon \ mathbb {Z} ^ {2},}$

isto é, uma grelha de comprimento lateral £ restrita a D . Seja v o vértice de G mais próximo de x . Examinar agora um passeio aleatório apagada-circuito a partir de v e quando parou de bater o "limite" de G , isto é, os vértices de L que correspondem ao limite de D . Então as conjecturas são

• Conforme ε vai para zero, a distribuição do caminho converge para alguma distribuição em caminhos simples de x para a fronteira de D (diferente do movimento browniano, é claro - em 2 dimensões os caminhos do movimento browniano não são simples). Essa distribuição (denote-a por ) é chamada de limite de escala do passeio aleatório apagado por loop.${\ displaystyle S_ {D, x}}$
• Essas distribuições são invariáveis ​​conforme . Ou seja, se φ é um mapa de Riemann entre D e um segundo domínio E, então

${\ displaystyle \ phi (S_ {D, x}) = S_ {E, \ phi (x)}. \,}$

• A dimensão de Hausdorff desses caminhos é 5/4 quase certa .

O primeiro ataque a essas conjecturas veio da direção das telhas de dominó . Tomando uma árvore geradora de L e adicionando-lhe a sua dupla planar que se obtém um domino ladrilhos de um gráfico especial derivada (chame- H ). Cada vértice de H corresponde a um vértice, aresta ou face de G , e as arestas de H mostram qual vértice está em qual aresta e qual aresta em qual face. Acontece que, tendo um Spanning Tree uniforme de G conduz a um domino aleatório distribuído uniformemente ladrilhos de H . O número de dominó de um gráfico pode ser calculado usando o determinante de matrizes especiais, que permitem conectá-lo à função de Green discreta que é aproximadamente invariante conforme. Esses argumentos permitiram mostrar que certas mensuráveis ​​de passeio aleatório apagado por loop são (no limite) invariantes em conformidade, e que o número esperado de vértices em um passeio aleatório apagado por loop parado em um círculo de raio r é da ordem de . ${\ displaystyle r ^ {5/4}}$

Em 2002, essas conjecturas foram resolvidas (positivamente) usando o Stochastic Löwner Evolution . Grosso modo, é uma equação diferencial ordinária estocástica conformalmente invariante que permite capturar a propriedade de Markov de passeio aleatório apagado por loop (e muitos outros processos probabilísticos).

Três dimensões

O limite de escala existe e é invariável sob rotações e dilatações. Se denota o número esperado de vértices no passeio aleatório apagado por loop até chegar a uma distância de r , então ${\ displaystyle L (r)}$

${\ displaystyle cr ^ {1+ \ varepsilon} \ leq L (r) \ leq Cr ^ {5/3} \,}$

onde ε, c e C são alguns números positivos (os números podem, em princípio, ser calculados a partir das provas, mas o autor não o fez). Isso sugere que o limite de escala deve ter dimensão de Hausdorff entre e 5/3 quase com certeza. Experimentos numéricos mostram que deveria ser . ${\ displaystyle 1+ \ varepsilon}$${\ displaystyle 1,62400 \ pm 0,00005}$

Notas

Referências

• Kenyon, Richard (2000a), "The asymptotic determinant of the discrete Laplacian", Acta Mathematica , 185 (2): 239–286, arXiv : math-ph / 0011042 , doi : 10.1007 / BF02392811
• Kenyon, Richard (abril de 2000), "Conformal invariance of dominó tiling", Annals of Probability , 28 (2): 759–795, arXiv : math-ph / 9910002 , doi : 10.1214 / aop / 1019160260
• Kenyon, Richard (março de 2000), "Long-range properties of spanning trees" , Journal of Mathematical Physics , 41 (3): 1338–1363, doi : 10.1063 / 1.533190
• Kozma, Gady (2007), "O limite de escala de passeio aleatório apagado em três dimensões", Acta Mathematica , 199 (1): 29-152, arXiv : math.PR/0508344 , doi : 10.1007 / s11511-007- 0018-8
• Lawler, Gregory F. (setembro de 1980), "A self-Avoiding random walk", Duke Mathematical Journal , 47 (3): 655-693, doi : 10.1215 / S0012-7094-80-04741-9
• Lawler, Gregory F. , "A correção logarítmica para passeio aleatório apagado em quatro dimensões", Proceedings of the Conference in Honor of Jean-Pierre Kahane ( Orsay , 1993). Edição especial do Journal of Fourier Analysis and Applications , pp. 347-362, ISBN 9780429332838
• Lawler, Gregory F. (1999), "Loop-erased random walk", em Bramson, Maury; Durrett, Richard T. (eds.), Problemas perplexos em probabilidade: Festschrift em honra de Harry Kesten , Progress in Probability, 44 , Birkhäuser, Boston, MA, pp. 197-217, doi : 10.1007 / 978-1-4612- 2168-5
• Lawler, Gregory F .; Schramm, Oded ; Werner, Wendelin (2004), "Conformal invariance of planar loop- erased random walk and uniform spanning trees", Annals of Probability , 32 (1B): 939-995, arXiv : math.PR/0112234 , doi : 10.1214 / aop / 1079021469
• Pemantle, Robin (1991), "Choosing a spanning tree for the integer lattice uniformly", Annals of Probability , 19 (4): 1559-1574, doi : 10.1214 / aop / 1176990223
• Schramm, Oded (2000), "Scaling limits of loop- erased random walk and uniform spanning trees", Israel Journal of Mathematics , 118 : 221–288, arXiv : math.PR/9904022 , doi : 10.1007 / BF02803524
• Wilson, David Bruce (1996), "Generating random spanning trees more rapid than the cover time", STOC '96: Proceedings of the Vigésimo oitavo Simpósio Anual ACM sobre a Teoria da Computação (Filadélfia, PA, 1996) , Association for Computing Machinery, New York, pp. 296-303, doi : 10.1145 / 237814.237880
• Wilson, David Bruce (2010), "A dimensão do passeio aleatório apagado em três dimensões", Physical Review E , 82 (6): 062102, arXiv : 1008.1147 , doi : 10.1103 / PhysRevE.82.062102