Wykład 6

Metody Monte Carlo

Metody Monte Carlo

Najszerzej: są to metody oparte na wykorzystaniu
liczb losowych do rozwiązania określonego problemu
obliczeniowego.

Podstawowe pojęcia teorii prawdopodobieństwa:

• Zdarzenie elementarne jest to możliwy wynik

doświadczenia losowego, zwykle przypisane jest
jemu pewne prawdopodobieństwo wystąpienia.

• Prawdopodobieństwo jest to funkcja P(X), która

przyporządkowuje każdemu elementowi zbioru
zdarzeń losowych pewną nieujemną wartość
rzeczywistą.

Definicje prawdopodobieństwa:

n

A

k

A

P

n

n

)

(

lim

)

(







Definicja klasyczna (Laplace'a) w roku 1812.

Prawdopodobieństwem zajścia zdarzenia A
nazywamy iloraz liczby zdarzeń sprzyjających
zdarzeniu A do liczby wszystkich możliwych
przypadków, zakładając, że wszystkie przypadki
wzajemnie się wykluczają i są jednakowo możliwe.

Definicja częstościowa:

gdzie k

n

(A) to liczba rezultatów

sprzyjających zdarzeniu A po n
próbach.

Prawdopodobieństwo zajścia zdarzenia A możemy
zapisać w postaci:

gdzie |A| oznacza liczbę elementów zbioru A, zaś |Ω|
liczbę elementów zbioru Ω.

Przykład: Rzucamy sześcienną kostką. Jakie jest
prawdopodobieństwo, że liczba oczek będzie większa
od 5?

Zbiór zdarzeń elementarnych Ω = {1, 2, 3, 4, 5, 6},
zatem liczba możliwych zdarzeń |Ω| = 6. Zbiór zdarzeń
sprzyjających A = {6}, liczba zdarzeń sprzyjających |A|
= 1. Prawdopodobieństwo zajścia zdarzenia wynosi:

Definicje prawdopodobieństwa:

Prawdopodobieństwo geometryczne
Definicja klasyczna nie pozwala obliczać prawdopodobieństwa w
przypadku, gdy zbiory A i Ω są nieskończone, jeśli jednak zbiory
te mają interpretację geometryczną, zamiast liczebności zbiorów
można użyć miary geometrycznej (długość, pole powierzchni,
objętość).
Przykład: z przedziału [0,4] wybieramy losowo punkt. Jakie jest
prawdopodobieństwo, że wybrany punkt będzie należał do
przedziału [1,2]?

Odpowiedź: Długości przedziałów wynoszą odpowiednio: |[0,4]| =
4 i |[1,2]| = 1. Zatem prawdopodobieństwo opisanego zdarzenia
wynosi:

    

Prawdopodobieństwo ma następujące własności:
P(Ω) = 1, gdzie Ω jest przestrzenią (zbiorem) zdarzeń
elementarnych
prawdopodobieństwo sumy przeliczalnego zbioru
zdarzeń parami rozłącznych jest równe sumie
prawdopodobieństw tych zdarzeń:
P(A

1



...



A

n



... ) = P(A

1

) + ... + P(A

n

) + ... Wartość

P(X) nazywa się prawdopodobieństwem zdarzenia X.
Ważniejsze własności prawdopodobieństwa:
P(A) ≥ 0
P(Ø) = 0 (UWAGA: z P(A)=0 nie wynika, że A=Ø)
A  B  P(A) ≤ P(B)

P(A) ≤ 1
A



B



P(B|A) = 1

P(A) + P(A') = 1, gdzie A′ oznacza zdarzenie losowe
przeciwne do A
P(A



B) = P(A) + P(B) - P(A



B).

Rozkład zmiennej losowej X (o wartościach
rzeczywistych) jest to prawdopodobieństwo P

X

określone na zbiorze podzbiorów zbioru liczb
rzeczywistych R wzorem:

Funkcja gęstości rozkładu
Jeżeli istnieje funkcja f taka, że

to zmienną X nazywamy zmienną typu ciągłego. Mamy wtedy:

Funkcję f nazywamy funkcją gęstości rozkładu zmiennej X.
Funkcję P nazywamy dystrybuantą rozkładu losowego

Rozkład Boltzmanna

 

 

 

 

 

 







































































































E

B

B

N

N

B

N

N

B

N

N

B

i

i

B

i

i

dE

T

k

E

E

Q

dE

T

k

E

E

Q

dE

E

P

d

d

T

k

E

Q

d

d

T

k

E

Q

d

d

P

T

k

E

Q

T

k

E

Q

P

exp

exp

1

,

exp

,

exp

1

,

exp

exp

1





p

q

p

q

p

q

p

q

p

q

p

q

q p

k

B

(stała Boltzmanna)

= 1.3810

-23

J/K

N

A

k

B

= R (uniwersalna stała gazowa) = 8.3143 J/(molK)

q – położenia; p – pędy; (E) – gęstość stanów o energii E

Początki: prawdopodobnie starożytność

Pierwsze udokumentowane użycie: G. Comte de
Buffon (1777) obliczenia całki przez rzucanie igły
na poziomą płaszczyznę
pokrytą równoległymi liniami prostymi.

Pierwsze zastosowanie na wielką skalę: J. von
Neumann, S. Ulam, N. Metropolis, R.P. Feynman i
in. (lata 1940-te; projekt Manhattan) obliczenia
rozpraszania i absorpcji neutronów. Nazwa
,,Monte Carlo” została wymyślona jako kryptonim
dla tego typu rachunków i odpowiednich metod
matematycznych.

Zgrubny podział metod Monte Carlo

 Metoda von Neumanna
 Metoda Metropolisa (łańcuchów

Markowa)

Ilustracja różnicy między metodą von Neumanna a
metodą Metropolisa. Pomiar średniej głębokości Nilu

Metoda von Neumanna

Obszar w którym chcemy policzyć wielkość uśrednioną
pokrywamy siatką punktów i dla każdego z nich
obliczamy gęstość prawdopodobieństwa oraz wielkość,
którą chcemy uśrednić:









N

i

i

i

V

P

A

A

1

Np. dla rozkładu Boltzmanna:



























N

i

i

N

i

i

i

kT

E

kT

E

A

A

1

1

exp

exp

Przykład zastosowania podejścia von

Neumanna do obliczania liczby 

1

 

4

1

2

1

2

lim















tot

N

N

n

S

S





Metoda Metropolisa (łańcuchy Markowa)

1. Bierzemy startową konfigurację układu daną współrzędnymi

(x

1

0

,y

1

0

,z

1

0

,…,x

n

0

,y

n

0

,z

n

0

); tej konfiguracji odpowiada energia E

0

.

2. Zaburzamy losowo wybraną współrzędną, np. x

i

0

or x

i

(mała

wartość).

3. Obliczamy energię nowej konfiguracji i oznaczamy ją jako E

1

.

4. Jeżeli E

1

<E

0

to nową konfigurację akceptujemy traktując jako

nową konfigurację startową i przechodzimy do punktu 1; w
przeciwnym przypadku przechodzimy do punktu 5.

5. Wykonujemy test Metropolisa:

a) Generujemy liczbę losową y z przedziału (0,1).

b) Jeżeli exp[-(E

1

-E

0

)/kT]>y, (k jest stałą Boltzmanna)

akceptujemy nową konfigurację, w przeciwnym przypadku
przechodzimy do punktu 2 ze starą konfiguracją.

Zaburz konfigurację X

o

: X

1

= X

o

+ X

Oblicz nową energię (E

1

)

Konfiguracja X

o

, energia E

o

E

1

<E

o

?

Wylosuj Y z U(0,1)

Oblicz W=exp[-(E

1

-E

o

)/kT]

W>Y?

X

o

=X

1

,

E

o

=E

1

NIE

TAK

TAK

NIE

Obliczanie średnich metodą Monte

Carlo

Średnia wielkości A







N

i

i

A

N

A

1

1

Indeks i przebiega przez wszystkie kroki Monte Carlo,
również te gdzie nowa konfiguracja nie została
zaakceptowana. Tak więc jeżeli jakaś konfiguracja ma
bardzo niską energię i nie chce przejść w alternatywną,
będzie liczona wielokrotnie.

Reprezentacja przestrzeni w

metodach Monte Carlo

• Siatkowa (dyskretna). Centra

oddziaływań mogą być tylko w
węzłach sieci o określonej topologii.

• Ciągła. Centra oddziaływań mogą

przyjąć dowolne położenie w
przestrzeni trójwymiarowej.

Zastosowania metody

Metropolisa w chemii

obliczeniowej

• Wyznaczanie wielkości mechanicznych i

termodynamicznych (gęstość, średnia

energia, pojemność cieplna, przewodnictwo,

współczynniki wirialne).

• Symulacje przemian fazowych.
• Symulacje właściwości polimerów.
• Symulacje zwijania białek i innych

biopolimerów.

• Symulacje wiązania ligandów z receptorami

oraz szacowanie energii swobodnej tego

procesu (projektowanie leków).

• Symulacje reakcji chemicznych.