Archive for Science

Dwa paradoksy prawdopodobieństwa

2009-04-05 18:34

Na dzisiaj przewidziałem ciekawostki z nieco innej niż zwykle beczki :) Chciałem mianowicie pokazać dwa przykłady na to, jak intuicyjnie całkiem proste pojęcie matematyczne w rzeczywistości jest bardzo podatne na niewłaściwe zrozumienie. Chodzi tutaj o zwykłe prawdopodobieństwo – czyli szansę na zajście jakiegoś zdarzenia.

Pierwszy przykład jest z gatunku rozrywkowo-medialnych i związany jest z pewnym teleturniejem, który zresztą był kiedyś emitowany także w Polsce. Oto w pewnym jego etapie uczestnik jest konfrontowany z trzema zasłoniętymi bramkami, z których jedna zawiera nagrodę, a dwie pozostałe są puste. Spośród tej trójki gracz wybiera jedną bramkę, by stać się właścicielem jej ewentualnej zawartości. Trik polega na tym, że gospodarz programu – już po wyborze gracza – odsłania jedną z pozostałych bramek, która okazuje się być pusta. Zgodnie z regułami teleturnieju gracz może w tym momencie zmienić swój wybór i wskazać trzecią bramkę zamiast tej wybranej pierwotnie. Pytanie brzmi: czy taka zamiana mu się opłaca?
Część ludzi stwierdziłaby zapewne, że nie ma to znaczenia, bo szansa wygranej przecież i tak wynosi 1 do 3, bo tylko za jedną bramką jest nagroda. Inni mogliby uznać, że po odsłonięciu jednej bramki wybieramy już spośród dwóch, więc nasze szansę rosną do 50% – też niezależnie od tego, czy zmienimy swój pierwotny wybór czy nie… A jak jest naprawdę?
Może się to wydawać niedorzeczne, jednak będąc na miejscu gracza, powinniśmy zawsze zmienić swój wybór. Mało tego, w ten sposób nasze szanse na wygraną rosną dokładnie dwukrotnie! Jak to możliwe?… Otóż kluczowe w wyjaśnieniu tego zjawiska jest zauważenie, że gospodarz programu zawsze odsłoni bramkę pustą i niewybraną przez gracza (w innym przypadku gra skończyłaby się od razu i w ogóle nie byłoby możliwości zmiany). Dlatego też opłaca się dokonać zmiany, bo w ten sposób w istocie odwracamy prawdopodobieństwo wygranej i przegranej. Możliwe są bowiem dwie sytuacje:

  • gracz początkowo wybiera bramkę z nagrodą – po zmianie kończy więc z bramką pustą
  • gracz najpierw wskazuje bramkę pustą; wówczas gospodarz odsłoni drugą pustą bramkę, więc zmiana skończy się wyborem bramki z nagrodą

Jak wiadomo prawdopodobieństwo dobrego wyboru spośród trzech bramek wynosi 1/3, a złego – 2/3. Takie są też odpowiednie prawdopodobieństwa dwóch powyższych scenariuszy; innymi słowy, zmiana bramki powoduje, że prawdopodobieństwo wygranej rośnie z początkowego 1/3 do 2/3.
Jeśli ktoś ma nadal wątpliwości, to nie ma czym się martwić – podobno wielu matematyków też ma kłopoty z ogarnięciem tego paradoksu :) Wydaje mi się, że rzecz w tkwi w błędnym określeniu, co tak naprawdę jest tutaj zdarzeniem losowym. Jeśli za takie będziemy uważali zarówno początkowy wybór, jak i zmianę, to rzeczywiście mogą być kłopoty z dojściem do poprawnych wniosków. Zamiast tego całą grę powinno się traktować jako jedno doświadczenie losowe, ze z góry ustalonym scenariuszem.

A co z drugim przykładem? Jest na szczęście nieco prostszy i dotyczy koncepcji zdarzeń (nie)zależnych. Oto kilka pytań dotykających tej kwestii, dla których odpowiedzi “intuicyjne” są zwykle błędne:

  • Jeśli zakręcimy kołem ruletki 57 razy i za każdym razem kulka wpadnie w czarne pole, to jaka jest szansa na to, że będzie tak również przy następnym obrocie?
  • Jeśli liczba 42 ostatni raz wystąpiła w Dużym Lotku pół roku temu, to jaka jest szansa, iż wypadnie w dzisiejszym losowaniu?
  • Jeśli w grze X potwór Y wyrzuca przedmiot Z z prawdopodobieństwem 1/n, to jak dużo potworów Y powinienem zabić, aby być prawie pewien, że wypadnie mi z nich przedmiot Z?

Nie, prawdopodobieństwo wpadnięcia kulki w czarne pole to cały czas 1/2. Nie, liczba 42 może wypaść z takim samym prawdopodobieństwem dzisiaj, jak i w każdym innym losowaniu. Nie, zabicie n potworów Y wcale nie da nam prawie-pewności dostania Z – o ile mówimy o zwyczajowym użyciu słowa ‘prawie’ ;)
Wszędzie tutaj mamy bowiem do czynienia z sekwencją zdarzeń całkowicie niezależnych, których wyniki nie wpływają na siebie. Zatem nie ma znaczenia to, ile razy wcześniej kręciliśmy ruletką, ile wysłaliśmy już w życiu kuponów Lotto i ile wrażych monstrów zdołaliśmy zaszlachtować – prawdopodobieństwo zajścia interesującego nas zdarzenia w kolejnej próbie jest zawsze identyczne. Możemy aczkolwiek spróbować policzyć, na ile jest to prawdopodobne dla ciągu k kolejnych prób. Otóż ze schematu Bernoulliego wynika, że szansa na sukces wynosi wtedy

1 – (1 – p)k

jeśli dla pojedynczej próby prawdopodobieństwo wynosi p. Stąd dla p = 1/n i k = n otrzymujemy (po kilku, jak to by powiedzieli matematycy, “trywialnych przekształceniach ;D) wynik: (e – 1)/e; nieco ponad 63%. To trochę mało jak na prawie-pewność, czyż nie? ;]

Jak więc widać na przykładach, szansa na to, że opacznie zrozumiemy sytuację, w której zastosowania mają pojęcia ‘szansy’ czy ‘prawdopodobieństwa’ (używane tutaj jako synonimy) jest – nomen omen dosyć duża. Może dlatego w szkole niespecjalnie przepadałem za tym działem matematyki :)

Tags:
Author: Xion, posted under Math » 19 comments

Losowanie tabelkowe

2007-08-26 14:35

W niemal każdym programie chociaż raz zdarza się potrzeba, by “rzucić kośćmi” i pozwolić, by wydarzyło się coś losowego. Oznacza to skorzystanie z generatora liczb pseudolosowych, aby uzyskać ‘przypadkową’ wartość. Nie będzie ona faktycznie losowa, lecz dzięki zastosowaniu matematycznych formuł o dużej nieregularności rezultat może być bardzo zbliżony do ideału. Istnieje oczywiście wiele algorytmów wyznaczania liczb pseudolosowych, różniących się faktyczną przypadkowością uzyskiwanego wyniku.
W różnych językach programowania mamy natomiast odmienne sposoby na uzyskanie liczby ‘losowej’. Zwykle najwygodniejszym jest wartość z zakresu [0..1], bo odpowiada to matematycznemu pojęciu prawdopodobieństwa. Aby w C++ uzyskać taki rezultat, wystarczy napisać proste opakowanie na biblioteczną funkcję rand:

  1. float Random() { return rand() / (float)RAND_MAX; }

Mając taki generator, możemy już łatwo sprawdzić, czy “zdarzyło się” coś, czego prawdopodobieństwo znamy:
// doświadczenie losowe z określonym prawdopodobieństwem
bool RandomOccured(float fProbability) { return Random() <= fProbability; }[/cpp] W ten sposób możemy na przykład rzucać wirtualną monetą. Przykładowa tabelka ataku w World of WarcraftSprawa się jednak komplikuje, jeżeli możliwych wyników doświadczenia jest więcej, a przy okazji mają one różne prawdopodobieństwa zajścia. Tak się dzieje na przykład w grach RPG, w których konieczne jest obliczanie rezultatów zadanych ciosów (trafienie, pudło, unik, blok, itp.). Skuteczność postaci w walce zależy zwykle od jej statystyk, więc szanse poszczególnych wyników nie są stałe i zmieniają się w trakcie gry.
Dobre generatory liczb pseudolosowych są zaś nierzadko względnie kosztowne obliczeniowo. Dlatego zamiast wykonywać po jednym losowaniu dla każdego możliwego rezultatu (zaszedł – nie zaszedł), znacznie lepiej jest załatwić wszystko jednym losowaniem. Nie jest to trudne:
// doświadczenie losowe z prawdopodobieństwem określonym tabelką
int RandomResult(const float* aProbs, int n)
{
float fRand = Random();

float fAccum = 0.0f;
for (int = 0; i < n; ++i) { // sprawdzamy, czy wylosowana liczba mieści się w zakresie p-stwa if (fAccum <= fRand && fRand < fAccum + aProbs[i]) return i; fAccum += aProbs[i]; } // błąd return -1; }[/cpp] Tak naprawdę liczymy tutaj dla każdego możliwego rezultatu wartość tzw. dystrybuanty. Ale chyba nie warto wnikać w takie teoretyczne szczegóły – grunt, że powyższa metoda działa w praktyce :) Trzeba tutaj jednak pamiętać, aby prawdopodobieństwa sumowały się do 1. Jeśli tak nie jest, można przeskalować wylosowaną liczbę.

Tags: ,
Author: Xion, posted under Math, Programming » Comments Off on Losowanie tabelkowe
 


© 2018 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.