274844712

1. Wprowadzenie

gdzie (£fci rjk) są niezależnymi wektorami losowymi o jednakowym rozkładzie prawdopodobieństwa:

t ((&, it) = (o, i)) = P ((&, m) = (o, -i))

= *((&,»*) = (i,0))=K(6,ift) = (-1,0)) = i.

Błądzimy tak długo, aż natrafimy na brzeg obszaru. Formalnie, określamy moment zatrzymania T — min{fc : (Xk,Yk) € dT>}. Łatwo zauważyć, że funkcja

u(x,y) := E[fi(X_r)yr)|(*0,yo) = (®,y)]

jest rozwiązaniem zagadnienia! Istotnie, ze wzoru na prawdopodobieństwo całkowite wynika, że

= j E E[a(jr_T,y_T)|(jri,yi) = (!!',»')].

Wystarczy teraz spostrzeżenie, że rozkład zmiennej losowej u(Xt, Yp) pod warunkiem (.Xi, Y}) = (z', y') jest taki sam jak pod warunkiem (Xo, Vo) = (x', y¹), bo błądzenie „rozpoczyna się na nowo”.

Algorytm Monte Carlo obliczania u(x, y) oparty na powyższym spostrzeżeniu został wynaleziony przez von Neumanna i wygląda następująco:

—    Powtórz wielokrotnie, powiedzmy n razy, niezależnie doświadczenie:

„błądź startując startując z (x,y) aż do brzegu; oblicz u(Xt,Yt)"

—    Uśrednij wyniki n doświadczeń.

Dla bardziej formalnego zapisu algorytmu będę się posługiwał pseudo-kodem, który wydaje się zrozumiały bez dodatkowych objaśnień:

Listing.

{ 'Gen' oznacza 'Generuj'}

U := 0; for j = 1 to n begin

(X,Y) :=(*,»); while (X,Y)eV begin

Gen (£, ij) ~ U{(0,1), (0, —1), (1,0), (—1,0)}; [ rozkład jednostajny na zbiorze 4—punktowym ]

(X,F):=(*,n+ («,»)

end

U := U+ u{X, Y) end

U := U/n

Przykład 1.5 (Problem „plecakowy”). Załóżmy, że a = (ai,... ,a_m)^T jest wektorem o współrzędnych naturalnych (a* € {1,2,...}) i b € {1,2,...}. Rozważamy wektory x — (xi,..., x_m)^T o współrzędnych zero-jedynkowych (xj 6 (0,1}). Interesuje nas liczba rozwiązań nierówności

x^Ta = ^ XiOi < 6,