Od igły Buffona do metody Monte Carlo: statystyczne wyznaczenie liczby pi oraz wielkości mrowiska

Jean Marie Leclerc, hrabia de Buffon, był obok swego rówieśnika ze Szwecji Carla Linneusza najsławniejszym naturalistą drugiej połowy XVIII wieku. Za jego życia ukazało się trzydzieści sześć tomów historii naturalnej, a jeszcze kilka po jego śmierci z pozostawionych przez uczonego materiałów. W młodości nic nie zapowiadało, że zdolny jest do tak gigantycznej pracy. Studiował nauki przyrodnicze i Newtona zamiast poświęcić się prawu i być jak ojciec, adwokat parlamentu Burgundii oraz poborca podatku od soli. W Angers zabił w pojedynku chorwackiego oficera i musiał uciekać. Podróżował dłuższy czas po Europie razem z Evelynem Pierrepontem, drugim diukiem Kingston-upon-Hall, potem osiadł w Paryżu i zaczął starać się o przyjęcie do Akademii Nauk. Bardziej od zasług naukowych liczyły się kontakty, Buffon napisał jednak oryginalną, choć nietrudną pracę dotyczącą pewnej gry hazardowej, le jeu du franc-carreau. Polegała ona na tym, aby upuszczać przypadkowo monetę na posadzkę z drobnych płytek. Liczyło się, czy moneta mieści się całkowicie wewnątrz jednej z płytek, czy przecina jakieś granice między nimi. Buffon zastanawiał się, jak duże muszą być monety w stosunku do długości boku kwadratowej płytki, aby gra taka była sprawiedliwa. Przedstawił też jej prostszą odmianę: rzucamy w sposób przypadkowy igły długości l na podłogę z desek o szerokości d i sprawdzamy, czy igła przecina linię oddzielającą deski. Znów można zadać pytanie, przy jakim stosunku l/d gra będzie sprawiedliwa.

BuffonsNeedle

http://demonstrations.wolfram.com/BuffonsNeedleProblem/

Okazuje się, że prawdopodobieństwo przecięcia którejś linii równe jest

p=\dfrac{2}{\pi}\dfrac{l}{d}.

Wzór ten słuszny jest dla l\le d.Buffon ogłosił swe rozważania, po czterdziestu z górą latach, w roku 1777, w długiej rozprawie Essai d’arithmétique morale (arytmetyka moralna to rachunek prawdopodobieństwa). Dla kogoś, kto przełożył na francuski Traktat o fluksjach Isaaca Newtona, nie było to trudne zagadnienie. W roku 1812 Pierre Simon de Laplace zwrócił uwagę, że jeśli znamy stosunek długości igły do odległości linii, możemy eksperymentalnie wyznaczyć wartość liczby \pi. Np. na rysunku powyżej wylosowano 100 rzutów i igła przecina linię 66 razy oraz l=d. Wartość liczby \pi oszacowana na podstawie tego eksperymentu równa jest

\pi=\dfrac{2}{0,66}\approx 3,03

 My pokażemy, jak znaleźć to prawdopodobieństwo, nie korzystając z żadnych całek. Jeśli igła dowolnej długości l pada losowo na układ równoległych linii, to może je przeciąć pewną skończoną liczbę razy. Załóżmy, że zliczamy liczby przecięć dla kolejnych rzutów.

buffon1

Wartość oczekiwana liczby przecięć równa jest

E(l)=p_1+2p_2+3p_3+\ldots.

 Prawdopodobieństwo, że przecięć będzie k oznaczyliśmy p_k, suma zawiera tyle składników, ile trzeba dla danej długości igły. Jeśli podzielimy naszą igłę na dwie części o długościach l=l_1+l_2, to można ustalić zawsze, która część przecina daną linię.

buffon1_5

Jeśli przecięcia obu części będziemy zliczać oddzielnie, a następnie je zsumujemy, wynik nie może być inny niż przed podzieleniem igły:

E(l)=E(l_1)+E(l_2).

Moglibyśmy podzielić igłę na dowolną liczbę kawałków, łatwo widać, że E(cl)=cE(l) dla dowolnych wymiernych wartości c. Funkcja E(l) jest rosnąca, możemy więc napisać

E(l)=E(1)l=cl.

Wyznaczenie E(l) sprowadza się więc do znalezienia stałej c, która jest niezależna od długości igły.

Wyobraźmy sobie, że nasza igła to kawałek drutu, który zaginamy, jak na rysunku. Wartość oczekiwana liczby przecięć nadal będzie sumą wartości oczekiwanych liczby przecięć obu części. Inaczej mówiąc, wygięcie drutu nie zmieni wartości oczekiwanej całkowitej liczby liczby przecięć.

buffon2

A skoro tak, to możemy wyobrazić sobie, że rzucamy jakieś wielokąty foremne i obliczamy wartość oczekiwaną całkowitej liczby przecięć wielokąta z liniami prostymi. Nadal powinna to być ta sama funkcja E(l).

buffon2_5

Aby znaleźć wartość stałej c rozpatrzymy zamiast wielokątów ich graniczny przypadek czyli okrąg o średnicy d. Okręgi takie przecinają nasze linie proste dokładnie w dwóch punktach.

buffon3

Możemy więc napisać równość

2=E(d\pi)=d\pi E(1) \Rightarrow E(l)=\dfrac{2l}{\pi d}.

Obliczyliśmy w ten sposób wartość oczekiwaną liczby przecięć dla dowolnej igły. Co to ma wspólnego z prawdopodobieństwem pojedynczego przecięcia? Jeśli nasza igła jest krótsza niż odległość linii, to może przeciąć najwyżej jedną z nich, a więc E(l)=p_1.

Nietrudno zauważyć, że nasze obliczenie sprowadza się do ustalenia stosunku dwóch pól powierzchni z rysunku, czyli inaczej mówiąc do obliczenia pola powierzchni między sinusoidą a osią odciętych.

buffon0Można sobie wyobrazić bardziej bezpośredni sposób obliczenia pola powierzchni i tym samym liczby \pi. Wyobraźmy sobie kwadrat i załóżmy, że losujemy w sposób całkowicie przypadkowy punkty wewnątrz tego kwadratu. Jeśli w kwadrat wpiszemy okrąg, to niektóre z nich znajdą się wewnątrz okręgu, inne na zewnątrz.

MonteCarlo1000

Na rysunku wylosowano 1000 punktów, 773 leżą wewnątrz okręgu, zatem

\dfrac{\pi}{4}\approx\dfrac{773}{1000}\Rightarrow \pi\approx 3,092

Obliczenie to stanowi prosty przykład działania metody Monte Carlo. Jest ona dość powolna, bo trzeba wygenerować wiele punktów, aby wynik był w miarę dokładny. Zauważmy jednak, że moglibyśmy w ten sposób zmierzyć pole pod dowolną krzywą, czyli mówiąc inaczej, obliczyć dowolną całkę. Metodę tę zaproponował w roku 1946 Stanisław Ulam, pracujący wówczas w Los Alamos. Dzięki pierwszemu komputerowi ENIAC można już było generować liczby losowe. Podczas rekonwalescencji po chorobie Ulam, specjalista od metod probabilistycznych, a do tego wielki miłośnik gier i hazardu, układał sobie pasjanse Canfielda i zaczął zastanawiać się, jak obliczyć w tym przypadku prawdopodobieństwo sukcesu. Było to trudne, ale można by np. wymodelować pewną liczbę gier i oszacować prawdopodobieństwo na podstawie częstości sukcesów. Razem z Johnem von Neumannem zastosowali po raz pierwszy metodę Monte Carlo do obliczeń dyfuzji neutronów.

Ciekawe zastosowania rozumowania typu igły Buffona można napotkać w biologii. Wyobraźmy sobie płaski obszar wypukły o polu powierzchni S. Zamiast igieł mamy dwa zestawy łuków krzywych. Ich całkowita długość to l_1 oraz l_2. Jeśli będziemy losowo umieszczać krzywe obu rodzajów w naszym obszarze, to średnia liczba przecięć między krzywymi obu rodzajów dana jest wzorem analogicznym do wzoru Buffona:

E=\dfrac{2l_1l_2}{\pi S}.

Możemy np. posłużyć się tą zależnością do statystycznego wyznaczenia pod mikroskopem długości pewnej krzywej (np. kawałka korzenia rośliny). Umieszczamy losowo w naszym obszarze badaną krzywą wraz z odcinkami prostej o ustalonej długości. Teraz wystarczy obliczyć, ile razy badana krzywa przecina się z odcinkami prostoliniowymi, co jest znacznie prostsze niż śledzenie za konkretną krzywą (wyobraźmy sobie, że mamy do zbadania tysiące takich korzeni).

root

Niech N będzie liczbę przecięć, zaś H całkowitą długością wylosowanych odcinków, wówczas długość krzywej równa jest

R=\dfrac{\pi NS}{2H}.

Zależność ta (oraz rysunek) pochodzą z klasycznej pracy E.I. Newmana, A Method of Estimating the total length of root in a SampleJournal of Applied Ecology, t. 3, (May, 1966), s. 139-145. Wzór Newmana można też wykorzystać do znalezienia pola powierzchni S, gdy znane są pozostałe wielkości. Sugerowano, że algorytmu tego rodzaju używają mrówki, szacując, czy jakieś miejsce nadaje się na nowe mrowisko. Dwa zestawy krzywych byłyby w tym przypadku dwoma trasami tej samej mrówki-zwiadowcy: liczyłaby ona, ile razy pierwsza trasa i druga się przecinają (trasy są znaczone feromonami, zakłada się, że mrówka reaguje na swoje indywidualne feromony). Nie potrafię ocenić, czy to dobra hipoteza, z pewnością ciekawa. Szczegóły można znaleźć w pracy: E.B. Mallon, N.R. Franks, Ants estimate area using Buffon’s needle, „Proc. R. Soc. London” B, t. 267 (2000) s. 765-770.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s