274844710

1. Wprowadzenie

Przykład 1.1 (Igła Buffona, 1777). Podłoga jest nieskończoną płaszczyzną, podzieloną równoległymi prostymi na „deski” szerokości d. Rzucamy „losowo” igłę o długości l. Elementarne rozważania prowadzą do wniosku, że

21

p = P(igła przetnie którąś z prostych) = —:.

TT d

Buffon zauważył, że tę prostą obserwację można wykorzystać do... obliczania liczby n metodą „statystyczną”. Powtórzmy nasze doświadczenie niezależnie n razy. Oczywiście, mamy do czynienia ze schematem Bernoulliego, w którym „sukcesem” jest przecięcie prostej. Niech

„ liczba sukcesów ^ⁿ    liczba doświadczeń

= — ^ I(w i-tym doświadczeniu igła przecięła prostą)

Wielkość p_n jest empirycznym odpowiednikiem prawdopodobieństwa p i powinna przybliżać to prawdopodobieństwo, przynajmniej dla dużych n. W takim razie, możemy za przybliżenie liczby 7r przyjąć

_ 21 Pnd'

Statystyk powiedziałby, że zmienna losowa ir_n jest estymatorem liczby 7r. To wszystko jest bardzo proste, ale parę kwestii wymaga uściślenia. Jak duża ma być liczba powtórzeń, żeby przybliżenie było odpowiednio dokładne? Ale przecież mamy do czynienia ze „ślepym losem”! Czyż pech nie może sprawić, że mimo dużej liczby doświadczeń przybliżenie jest kiepskie? Czy odpowiednio dobierając l i d możemy poprawić dokładność? A może da się zaprojektować lepsze doświadczenie?

Przykład 1.2 (Sieć zawodnych połączeń). Niech V, £ będzie grafem skierowanym spójnym. Krawędzie reprezentują „połączenia” pomiędzy wierzchołkami. Krawędź e G £, niezależnie od pozostałych, ulega awarii ze znanym prawdopodobieństwem p_e. W rezultacie powstaje losowy podzbiór C C £ sprawnych połączeń o rozkładzie prawdopodobieństwa

P(C)= Y[P< U^-Pe)-

egC e€C

Jest jasne, jak można symulować to zjawisko: dla każdej krawędzi e „losujemy” zmienną U_e o rozkładzie równomiernym na [0,1] i przyjmujemy

je 0 C jeśli U_e < p_e\

[eeC jeśli U_e > p_e-

Powiedzmy, że interesuje nas możliwość znalezienia ścieżki (ciągu krawędzi) wiodącej z ustalonego wierzchołka vo do innego wierzchołka v\. Niech

0 = P( w zbiorze C istnieje ścieżka z vq do v\).

Generujemy niezależnie n kopii C\,..., C_n zbioru C. Nieznane prawdopodobieństwo 6 przybliżamy przez odpowiednik próbkowy:

0_n = — ^Pl( w zbiorze Ci istnieje ścieżka z vo do t>i).