Co to jest?
Monte Carlo, spacery i polimery
Z czym kojarzy się Monte Carlo? Z kasynami, hazardem, ruletką. A więc Monte Carlo jest symbolem potęgi przypadku, który jednym pozwala zbijać fortuny, innych rujnuje. Są jednak ludzie, którzy przypadkowość, losowość potrafią okiełznać i wykorzystać z pożytkiem (przynajmniej dla siebie). Oczywiście, takimi ludźmi są właściciele kasyn gry, ale nie tylko. Również matematycy zaprzęgają losowość do pożytecznej roboty. Metody obliczeniowe oparte na generowaniu (symulowaniu komputerowym) zdarzeń losowych nazywają się... oczywiście, metodami Monte Carlo.

Rys. 1 Przykład SAW-a o długości
Liczenie przedmiotów nie wydaje się zadaniem wymagającym wyrafinowanej matematyki, wykraczającej ponad program przedszkolny. Nie widać też, jaką rolę w czynności zliczania miałby odgrywać przypadek. A jednak! Rozważymy pozornie proste zadanie zliczania dróg, w którym ujawnią się nieoczekiwane trudności i pokażemy, jak pomysłowe metody Monte Carlo wynaleziono, aby te trudności pokonać.
Wyobraźmy sobie, że idziemy na spacer. Załóżmy, że mieszkamy w mieście, w którym ulice tworzą regularną, kwadratową siatkę, tak jak na rysunku 1. Ruszamy z punktu początkowego, wybierając jedną z czterech ulic. Idziemy zatem na północ, na zachód, na południe lub na wschód. Przechodzimy do sąsiedniego skrzyżowania i znowu wybieramy jeden z 4 kierunków. Powtarzamy całą procedurę, powiedzmy, razy. Przebyta droga jest łamaną składającą się z
odcinków o jednostkowej długości. Na rysunku 1 mamy przykład drogi o długości
Używając układu współrzędnych "zaczepionego w punkcie początkowym", możemy tę drogę zapisać jako ciąg kolejno odwiedzanych punktów:

Inny sposób zakodowania tej samej drogi to podanie kierunków ruchu w kolejnych "krokach": Ile jest wszystkich dróg o długości
Odpowiedź jest łatwa:
Musimy tu wyjaśnić, że licząc drogi wychodzące z tego samego punktu, utożsamiamy drogi z ciągami literek z alfabetu

Zmieńmy teraz nasze "reguły spacerowania". Przypuśćmy, że nie chcemy powtórnie przechodzić przez punkt, który już wcześniej odwiedziliśmy. W ciągu opisującym drogę nie może dwukrotnie pojawić się ten sam punkt. Tę własność ma np. droga na rysunku 1. Po angielsku taka droga nazywa się Self Avoiding Walk, w skrócie SAW. Ile jest SAW-ów o długości Wystarczy je wszystkie narysować i policzyć, prawda? Tą metodą można zbudować następującą tabelkę. Liczbę SAW-ów o długości
oznaczymy przez
Ale co dalej? Im dalej, tym gorzej. Ile jest SAW-ów o długości
W istocie, liczenie SAW-ów jest na tyle trudnym zadaniem, że matematycy (i fizycy, o czym dalej) uciekają się do przybliżonego zliczania metodą Monte Carlo. Najprostszy algorytm tego rodzaju jest niemal oczywisty. Ustalmy
Oznaczmy przez
zbiór wszystkich dróg o długości
zaś przez
zbiór SAW-ów o długości
Oczywiście
i
(kreseczki
oznaczają liczbę elementów zbioru; dla uproszczenia przy symbolach zbiorów zrezygnowaliśmy z indeksu
). Jeśli wybierzemy losowo jedną z dróg ze zbioru
to prawdopodobieństwo otrzymania "przypadkiem" SAW-a jest równe
Jeśli wybierzemy losowo i niezależnie
dróg, to spośród nich znajdzie się pewna liczba, powiedzmy
SAW-ów. Widać, że dla dużych
powinniśmy mieć
![]() |
(1) |
Przybliżenie staje się coraz lepsze w miarę zwiększania Ścisłe sformułowanie tego stwierdzenia nazywa się Prawem Wielkich Liczb (PWL) i jest podstawą rachunku prawdopodobieństwa. Nie trzeba jednak wielkiej wiedzy z tej dziedziny, wystarczy trochę zdrowego rozsądku, aby w przybliżoną równość (1) uwierzyć i ją zrozumieć. Z naszego punktu widzenia ważne jest wykorzystanie PWL do oszacowania nieznanej liczby SAW-ów. Wiemy, że
jest oszacowaniem liczby
prostą metodą Monte Carlo.
W zasadzie możemy osiągnąć dowolną dokładność dla odpowiednio dużych Zauważmy, że bardzo łatwo wylosować drogę ze zbioru
w taki sposób, aby dla każdego
prawdopodobieństwo wybrania
było jednakowe, równe
Na każdym kroku wybieramy jeden z 4 kierunków losowo. Możemy dwa razy rzucić monetą i umówić się: jeśli otrzymamy OO, to
jeśli OR, to
jeśli RO, to
jeśli RR, to
W ten sposób generujemy ciąg kodujący drogę "błądzenia przypadkowego". Komputer pozwala szybko "rzucić monetą" np.
razy i wygenerować
takich dróg.
Niestety, prosta metoda Monte Carlo jest bardzo nieefektywna, bo dla dużych prawdopodobieństwo
szybko zbliża się do zera. Oczekiwanie na przypadkowe trafienie w zbiór
czyli wylosowanie SAW-a, zaczyna przypominać poszukiwanie igły w stogu siana. Możliwym rozwiązaniem tego problemu jest metoda "wzrostu" zaproponowana przez Ariannę i Marshalla Rosenbluthów polega na losowaniu kolejnych kroków błądzenia przypadkowego tylko spośród "dopuszczalnych punktów", to znaczy punktów wcześniej nieodwiedzonych. W każdym kroku, z wyjątkiem pierwszego, mamy co najwyżej
możliwości. Rysunek 2 (następna strona) pokazuje kolejne kroki prowadzące do zbudowania SAW-a z rysunku 1. Widać, że kolejne kroki wybieraliśmy spośród

możliwych. Nasz SAW został zatem wylosowany z prawdopodobieństwem

Powiedzmy ogólniej, że przy budowaniu SAW-a o długości
mamy kolejno

możliwości. Nie jest przy tym wykluczone, że w pewnym kroku nie mamy żadnej dalszej możliwości,
Mówimy wtedy, że powstał nieprzedłużalny SAW o długości
Niech
oznacza zbiór wszystkich SAW-ów o długości
oraz nieprzedłużalnych SAW-ów o długości
Oczywiście,

Rys. 2 Generowanie SAW-a metodą "wzrostu".
Prawdopodobieństwo wylosowania SAW-a jest równe

Niech, dla będzie

Można interpretować jako "wagę" SAW-a
Powtórzmy teraz losowanie metodą wzrostu
razy. Powstaje
losowych SAW-ów
ze zbioru
Obliczamy "średnią wagę" wylosowanych SAW-ów i zauważamy, że
![]() |
(2) |
W rezultacie,
jest to oszacowaniem liczby
"metodą wzrostu".
Dodajmy komentarz na temat wzoru (2). Po lewej stronie mamy średnią wagę obliczoną dla wylosowanych elementów, czyli "średnią z próbki". Po prawej mamy też średnią, ale "w całej populacji
". Wagi
zostały specjalnie dobrane tak, aby ta średnia populacyjna była równa
Jeśli
jest dużo, dużo mniejsze od
to obliczenie
jest możliwe, a bezpośrednie policzenie elementów
jest niemożliwe. Kluczowy jest fakt, że średnia próbkowa przybliża średnią populacyjną. To jest odrobinę ogólniejsza wersja PWL. Poniższy rachunek jest próbą przekonania Czytelnika, że aproksymacja we wzorze (2) jest równie intuicyjna jak ta we wzorze (1). Niech
oznacza liczbę tych spośród wylosowanych elementów
dla których
i
Podobnie jak we wzorze (1), na mocy PWL,
Mamy zatem

Poniższa tabelka podaje dokładne wartości oszacowania tych liczb prostą metodą Monte Carlo (MC) i "metodą wzrostu". Dla obu metod, dla każdego
liczba symulowanych doświadczeń losowych była równa





SAW-y pojawiają się w fizyce jako najprostszy model budowy polimerów. Są to duże cząsteczki mające postać łańcucha złożonego z monomerów. Znajdują się w najróżniejszych materiałach: od włókien tkanin, tworzyw sztucznych, gumy i celulozy, aż po białka w żywych organizmach. Struktura przestrzenna łańcucha wpływa na własności fizyczne polimeru. W ogromnym uproszczeniu tę strukturę reprezentuje trójwymiarowy SAW (o długości od ok.
do
). W przestrzeni trójwymiarowej SAW definiuje się bardzo podobnie jak dwuwymiarowy: jako ciąg punktów o trzech współrzędnych całkowitych, w którym nie ma powtórzeń. Okazuje się, że pewne istotne cechy polimerów są związane np. z odległością (euklidesową) między końcami łańcucha. Badanie tej wielkości było zasadniczą motywacją przytoczonych prac. Zadanie zliczenia SAW-ów pojawiło się "przy okazji" i zafrapowało matematyków. Na zakończenie przytoczę przypuszczenie, którego dotąd nie udało się ani udowodnić, ani obalić. Powróćmy do dwuwymiarowych SAW-ów o długości
i liczb
Przypuszcza się, że istnieje granica

gdzie i
Coś, co zaczyna się jak przedszkolna zabawa, prowadzi do takich tajemnic.