Wykłady (ab)

Temat: Modele przeciekania (percolation)
Algorytmy stosowane w tzw. modelach perkolacyjnych (przeciekania). Przejście fazowe. Próbkowanie Monte Carlo. Zadania.

Na podstawie: Binder, Heermann, Monte Carlo simulations in statistical physics, Springer, 1997

1 Model przeciekania

Rozpatrujemy problem obsadzania węzłów nieskończonej sieci. Prawdobieństwo obsadzenia węzła jest równe p. Prawdopodobieństwo, że węzeł pozostaje pusty wynosi 1−p. Sąsiadujące obsadzone węzły tworzą tzw. klastry. Istnieje krytyczne p_c takie, że dla p < p_c na sieci istnieją tylko klastry o skończonych rozmiarach l, natomiast przy p > p_c istnieje jeden klaster, który przecieka z jednego brzegu sieci do przeciwnego. Algorytm przeciekania jest bardzo prosty. Dla sieci 3-wymiarowej o rozmiarze L można go zapisać następująco.

for (i=0;i<L;i++)
    for(j=0;j<L;j++)
        for(k=0;k<L;k++)
            lattice[i][j][k] = Math.random()<p?1:0;

Jeden przebieg przez wszystkie węzły sieci wyznacza całą konfigurację. Problemy:

Ile klastrów n_l(p), zawierających l węzłów istnieje na sieci w przeliczeniu na jeden węzeł?
Czy istnieje klaster rozciągający się od brzegu do brzegu?
Ile wynosi p_c?
Jakie jest prawdopodobieństwo, że obsadzony węzeł neleży do klastra przeciekającego, tzw. prawdopodobieństwo przeciekania, P_∞(p)?
Czemu równa się podatność χ zdefiniowana wzorem:

χ = ∞
∑
l=1
′l²n_l(p)/p .

(Prim oznacza, że w sumowaniu pominięto największy klaster).

Typowy algorytm obliczeń polega w tym problemie na wygenerowaniu N konfiguracji i na uśrednieniu odpowiednich wielkości.

1 powtarzaj konfig = 1 aż do N
2    utwórz konfigurację
3    przeanalizuj konfigurację
4    wylicz interesujące wielkości
5    dodaj odpowiadające wyniki
6 wykonaj uśrednianie

Analiza konfiguracji (3) polega na przeliczeniu klastrów i wyznaczeniu ich rozmiarów. Jak zidentyfikować klastry? Klaster jest takim zbiorem węzłów, że każdy element zbioru posiada sąsiada należącego do tego zbioru. Obsadzone węzły można traktować jak graf. Graf może składać się z oddzielnych podgrafów. Istnieją grafy z jednym wierzchołkiem, dwoma, trzema itd. Zadanie polega na przeliczeniu podgrafów w każdej klasie. Jak sprawdzić, że klaster jest nieskończony? Zadanie sprowadza się do sprawdzenia czy istnieje ścieżka łącząca dwa przeciwległe brzegi sieci. Prawdopodobieństwo znalezienia takiej ścieżki określa tzw. parametr porządku P_s, który może być następnie użyty do wyznaczenia punktu przejścia p_c. Poniżej p_c prawdopodobieństwo znalezienia takiej ścieżki jest zerowe, gdyż istnieją tylko klastry skończone. Powyżej progu p_c istnieje klaster nieskończony, który pozwala na przejście od brzegu do brzegu sieci; parametr porządku skacze gwałtownie do jedynki.

Z a d a n i e 1. Znaleźć algorytm rozstrzygający czy w danej konfiguracji problemu przeciekania istnieje ścieżka, łącząca przeciwne brzegi sieci. Wyznaczyć parametr porządku P_s dla różnych sieci o wielkości L i dla różnych prawdopodobieństw p. (Za parametr porządku w danej konfiguracji przyjąć stosunek wielkości największego klastra do liczby wszystkich obsadzonych węzłów sieci.)