Amostragem de Wang-Landau

O algorítmo de amostragem de Wang-Landau é um método de amostragem para simulações de Monte Carlo introduzido por F.Wang e D.P Landau em 2001 que apresenta diversas vantagens sobre outros métodos para sistemas de spins. Dentre eles podemos citar o algoritmo de Metropolis, o algoritmo de clustering de Wolff, ou em um modelamento de ensamble multi-canônico. Nestes dois últimos métodos são utilizados métodos de repesagem de histogramas que são limitados em sistemas grandes devido as baixa qualidade estatística nas asas do histograma. Dentro deste contexto, o algoritmo Wang-Landau promete resolver problemas encontrados em amostragens convencionais como o critical slowing down para temperaturas próximas da temperatura critica Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle T_c} utilizando-se de caminhadas aleatórias controladas para mapear a densidade de estados Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E)} de um sistema, sem fazer uso de qualquer repesagem de histogramas.

---

A maioria dos algoritmos de amostragem convencionais geram uma distribuição canônica não normalizada

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(E,T) = g(E)e^{-E/K_BT}, }

para uma determinada temperatura Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} , Geralmente estas distribuições são estreitas e se faz necessário múltiplas simulações para obter algum parâmetro termodinâmico para uma distribuição significantemente grande de temperaturas. Como Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E)} não depende de temperatura do sistema, se pudermos encontrá-lo para todo Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} , podemos encontrar a função de partição

Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z(T) = \sum_E g(E)e^{-E/K_BT}, }

e o sistema esta essencialmente resolvido, uma vez que grande parte dos parâmetros termodinâmicos podem ser derivados de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z} . Além disso, a amostragem de Wang-Landau é provada ser útil em diversas aplicações como o antiferromagneto de Potts, sistemas de spins aleatórios, sistemas quânticos, etc... .

Descrição do algoritmo de Wang Landau

Descreveremos o funcionamento do algoritmo de Wang-Landau num sistema de spins clássicos de 2 estados com valores discretos de energia e sem campo magnético. Portanto quando nos referirmos a Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E)} como densidade de estados, interpretamos como o número de estados com energia E. A amostragem de Wang-Landau faz caminhadas aleatórias no espaço de energia mudando os estados de spins aleatoriamente selecionados, porém esta mudança só é aceita com probabilidade proporcional a reciproca da densidade de estados. Durante a caminhada também se acumula o número de vezes que uma energia é visitada durante a caminhada Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E)} , isto é, ao visitarmos a energia Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_1} faz-se a atualização da variável Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E_1) \rightarrow H(E_1) + 1 } . Por outro lado, a atualização da densidade de estados Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E_1)} se da por um fator multiplicativo Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} (Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E_1) \rightarrow g(E_1) \times f } ) controlado ao longo da simulação para que seja muito próximo de 1 ao final das caminhadas.

Podemos descrever os passos do algoritmo da seguinte maneira:

1. Inicializamos as densidades de energias com Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E) = 1} para todo Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} , da mesma forma Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E) = 0} para todo Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} .
2. Inicializamos Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f = f_0 = e \approx 2.71828} e um sistema Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle L\times L} de spins de valor 1 e -1 aleatoriamente distribuídos.
   • O valor de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} é arbitrário e deve ser escolhido não muito pequeno, pois irá fazer com que a simulação demore muito tempo para explorar diversas energias, por outro lado se escolhido muito grande, levará a erros estatísticos significativos.
3. Começamos a caminhada inicial escolhendo aleatoriamente um dos spins e mudando o seu estado.
4. Se denotamos Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_1} como a energia antes da mudança de estado do spin selecionado e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_2} como a energia após, aceitamos este novo estado com a seguinte probabilidade: Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(E_1 \rightarrow E_2) = \text{min}\left(\frac{g(E_1)}{g(E_2)},1\right)}
   • Se aceitarmos a mudança de estado do spin, fazemos as atualizações de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E)} e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E)} como Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E_2) \rightarrow g(E_2) \times f} e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E_2) \rightarrow H(E_2) +1} respectivamente.
   • Se não aceitarmos a mudança de estado do spin, fazemos as atualizações de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E)} e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E)} como Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E_1) \rightarrow g(E_1) \times f} e Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E_1) \rightarrow H(E_1) +1} respectivamente, de maneira a recontar o estado Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_1} .
   • Destaca-se que em ambos os casos usamos Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ln(g(E)) = \rightarrow \ln(g(E)) + \ln(f)} , pois ao longo da simulação acabamos usando números muito grandes.
5. Faz-se esta caminhada aleatória nos diferentes estados do sistema até que o histograma Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E)} esteja aproximadamente plano.
   • O critério para decidir se um histograma está plano é arbitrário. Para um hamiltoniano Ising 2D este critério pode ser definido tão alto quanto 95% (i.e. todos os valores de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E)} devem ser pelo menos 95% de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle H(E) \rangle } ), porém valores mais altos que isso podem resultar no programa nunca identificando o histograma como plano.
6. Checa-se se Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E)} está plano a cada 10000 passos MC. Quando está plano, podemos dizer que todos os estados foram visitados uma quantidade de vezes aproximadamente igual e a densidade de estados Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(E)} converge ao valor real com precisão da ordem de Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} .
7. Reduz-se o fator Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} da seguinte maneira Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1 \rightarrow \sqrt{f_0}} , reinicia-se o histograma Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(E) = 0} e recomeça-se a caminhada aleatória com este novo fator Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} . (Todos os parâmetros não mencionados neste passo permanecem intocados).
8. Continuamos executando os passos 5-7, reduzindo o fator Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} segundo a seguinte expressão Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{i+1} = \sqrt{f_{i}}}
9. Encerra-se a simulação quando Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{final}} estiver da ordem do erro desejado.
   • Claro que Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_{final}} pode ser escolhido arbitrariamente pequeno, mas sempre com um certo limite razoável Falhou ao verificar gramática (MathML com retorno SVG ou PNG (recomendado para navegadores modernos e ferramentas de acessibilidade): Resposta inválida ("Math extension cannot connect to Restbase.") do servidor "https://wikimedia.org/api/rest_v1/":): {\displaystyle (10^{-6}-10^{-8})} , ou a simulação pode tomar tempos não razoáveis para completar.

Observações sobre o algoritmo

Nesta seção discutimos algumas observações importantes a se levar em conta na implementação do método de amostragem de Wang-Landau

Fator de modificação f

Quando tratamos da atualização do fator $f$, a expressão $f_{i+1}={\sqrt {f_{i}}}$ é apenas uma recomendação, uma vez que outros valores de $n>1$ podem ser escolhidos para uma atualização do tipo $f_{i+1}=f_{i}^{(1/n)}$. Não obstante, $n=2$ é adequado para grande parte dos sistemas estudados, resultando em boa acurácia em relativamente pouco tempo de simulação.

Implementação paralela

A simulação pode ser melhorada ainda fazendo múltiplas caminhadas aleatórias paralelamente no espaço de energias. Restringindo o alcance das caminhadas proporcionalmente com o número de caminhantes em paralelo (e.g. No caso de 2 caminhantes simultâneos, dividimos o espaço de energias em 2 e restringimos um caminhante para a metade inferior das energias, e o outro para a parte superior) e depois juntando as densidades de estados resultantes.

Balanço detalhado

A condição de balanço detalhado inicialmente não é satisfeita uma vez que $g(E)$ é constantemente modificada durante a caminhada aleatória. Porém após várias iterações, a condição é satisfeita a medida que $f$ se aproxima de 1. Observa-se que se $P(E_{1}\rightarrow E_{2})$ é a probabilidade de transição da energia $E_{1}$ para a energia $E_{2}$, utilizando a equação do passo 4 do algoritmo temos que:

${\frac {P(E_{1}\rightarrow E_{2})}{P(E_{2}\rightarrow E_{1})}}={\frac {g(E_{1})}{g(E_{2})}}.$

Podemos reescrever a equação de uma forma mais familiar

${\frac {1}{g(E_{1})}}P(E_{1}\rightarrow E_{2})={\frac {1}{g(E_{2})}}P(E_{2}\rightarrow E_{1})$

que é a condição de balanceamento detalhado, uma vez que interpretamos que $1/g(E_{1})$ como a probabilidade do sistema possuir a energia $E_{1}$ e analogamente para $E_{2}$. Concluímos então que a condição de balanço detalhado é satisfeita com precisão proporcional a $\ln(f)$.