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(Xr)yr)|(*0,yo) = (®,y)]
jest rozwiązaniem zagadnienia! Istotnie, ze wzoru na prawdopodobieństwo całkowite wynika, że
= j E E[a(jrT,yT)|(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', y1), 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,... ,am)T jest wektorem o współrzędnych naturalnych (a* € {1,2,...}) i b € {1,2,...}. Rozważamy wektory x — (xi,..., xm)T o współrzędnych zero-jedynkowych (xj 6 (0,1}). Interesuje nas liczba rozwiązań nierówności
xTa = ^ XiOi < 6,
Wyszukiwarka
Podobne podstrony:
Rozkłady dwuwymiarowe, niezależność zmiennych 1 .Wektor losowy (X,Y). Niech rozkład wektora losowego
CZESC< (1) Test 3 z Metod Probabilistycznych gr.M 1. Niech dany będzie wektor losowy (X, Y§ć rozkład
74 5. EstymacjaZadanie 5.1.6*. Niech Xl,X2,...,Xn będą niezależnymi zmiennymi losowymi o jednakowych
IMG 1201104005 ZAD.1.09 punkty) Wektor losowy (X.Y) ma rozkład Y -V -i _L_i 1
IMG 1201104005 ZAD.1.09 punkty) Wektor losowy (X.Y) ma rozkład Y -V -i _L_i 1
img299 //0 : wektory x i y są niezależne. Jest ona równoważna hipotezie:Mo:Ip? = 0 , izn. że wszystk
img299 //0 : wektory x i y są niezależne. Jest ona równoważna hipotezie:Mo:Ip? = 0 , izn. że wszystk
102 7. Wektory losowe Dla dwuwymiarowego przypadku dyskretnego niezależność zmiennych losowych X i Y
23 (447) - METODY PROBABILISTYCZNE I STA TYSTYKA -ĆWICZENIA 3.WEKTOR LOSOWY DWUWYMIAROWY, NIEZALEŻNO
ćw lista zadań 3 - METODY PROBABILISTYCZNE I STA TYSTYKA -ĆWICZENIA 3.WEKTOR LOSOWY DWUWYMIAROWY, NI
9. Zbadać liniową niezależność podanych wektorów (tzn. rozstrzygnąć, jakie są te wektory: linio
-musi być wprowadzony, gdzie zatrudnionych jest. co najmniej 20 pracowników -którzy nie są objęd zak
skanuj0063 (46) Wszystkie węzły sieci są końcami wektorów ua--vb przy czym u i v oznaczają dowolne l
0000001 8 Ryc. 7b. Układ mięśniowy z tyłu. Proste odruchy motoryczne są niezależne od naszej woli.
więcej podobnych podstron