Ale najpierw przedstawię oryginalny problem. Sprawa ma się tak:
Zawodnik stoi przed trzema zasłoniętymi bramkami. Za jedną z nich (za którą – wie to tylko prowadzący program) jest nagroda (umieszczana całkowicie losowo). Gracz wybiera jedną z bramek. Prowadzący program odsłania inną bramkę (co istotne – anonsując, że jest to bramka pusta), po czym proponuje graczowi zmianę wyboru. (źródło: Wikipedia)Pytanie brzmi: czy zawodnik zyskuje coś przez zmianę bramki?
Intuicyjnie można powiedzieć, że nie. Zostają przecież dwie bramki: jedna z nagrodą, druga bez. Szansa wynosi więc 50 na 50, fifty-fifty, bo raz wygramy, a raz nie. Nie ma więc znaczenia, czy bramkę zmienimy, czy nie. Przypomina mi się tutaj głupi żart - Polska ma 50% szans na wygranie Mistrzostw Świata w piłkę nożna: albo wygramy albo nie. No cóż, najwidoczniej nie mam poczucia humoru :P
Paradoks w wyborze bramek polega na tym, że prezenter daje nam o wiele więcej informacji niż myślimy. Dlatego powyższe rozumowanie jest to błędne. Zmiana bramki w istocie zwiększa szansę na wygraną dwukrotnie! Dobrze, że nie wszyscy zawodnicy pojawiający się u Hajzera o tym wiedzieli. Zza bramek masowo wyskakiwały kochane Zonki. No i gracze łapali zonka! Cudnie! Kasa zostaje w programie.
Dlaczego tak się nie dzieje? Próbowałem wytłumaczyć to w mojej odpowiedzi. Oto jej wycinek:
- Najłatwiejsze do zobrazowania: zmieńmy zasady gry i użyjmy 1000 bramek zamiast 3. Zasady gry są takie: Wybierasz 1 bramkę, po czym prowadzący odsłania 998 pustych bramek. Zostają dwie: Twój początkowy wybór i jeszcze jedna bramka. W tej sytuacji oczywistym jest zmienić bramkę. Prawdopodobieństwo trafienia wygranej wynosi początkowo 1 na 1000. Natomiast druga bramka pozostawiona przez gospodarza to wygrana w 999 przypadkach na 1000. Więc generalnie dla n bramek, nie zmieniając wyboru prawdopodobieństwo wygranej to 1/n. Zmieniając bramkę to (n-1)/n.
- Inne rozwiązanie: wyobraź sobie dwóch graczy O: Optymista i P: Pesymista. O zawsze wierzy, że jego pierwszy wybór jest słuszny. P zawsze uważa, że za pierwszym razem nie trafi. Jakie jest prawdopodobieństwo, że mają rację? O trafia z prawdopodobieństwem 1/3 i takie jest prawdopodobieństwo, że ma rację. P ma rację, że nie trafi, jeśli padnie na pustą bramkę, czyli 2/3 szansy. Teraz nadchodzi czas odsłonięcia jednej pustej bramki. O dalej twierdzi, że miał rację, więc decyduje się pozostać ze swoim początkowym wyborem i ma 1/3 szansy, że wygra. P wie natomiast, że ma 2/3 szansy na spudłowanie jeśli zostanie ze swoją bramką. Jako, że jedna pusta bramka już znikła, w pozostałej nieodsłoniętej siedzi nagroda w 2 przypadkach na 3. Zmieniając bramkę prawdopodobieństwo przegranej (2/3) przechodzi na prawdopodobieństwo wygranej (2/3) i vice versa. Konkluzja jest taka, że w tej grze opłaca się być pesymistą (co do pierwotnego wyboru).
Niech A, B, C określają zdarzenia, że wygrywa kolejno bramka a, b lub c. Początkowo P(A) = P(B) = P(C) = ⅓
Załóżmy, że miała miejsce następująca sytuacja: zawodnik wybrał bramkę a, gospodarz odsłonił bramkę c. Można niemal natychmiast wyprowadzić taki wzór na prawdopodobieństwo warunkowe: "A pod warunkiem, że nie C". Zapisujemy to tak: P(A|C') = P(A∩C) / P(C) i po prostych kalkulacjach otrzymujemy: ⅓ / ⅔ = ½. Czyli prosta konkluzja, że szansa na wygraną po usunięciu bramki c wynosi połowę. (Błąd!)
 |
| Gracz wybiera pierwszą bramkę, prowadzący odsłania trzecią z Zonkiem. Prawdopodobieństwo przesuwa się. (źródło: Wikipedia) |
Jak to wcześniej podkreślałem, jest subtelna, acz zasadnicza różnica pomiędzy zdaniem: "a wygrywa pod warunkiem, że nie wygrywa c", a zdaniem "a wygrywa pod warunkiem, że odsłonięto c". Pierwsze zdanie to uproszczenie problemu. Tak moglibyśmy rozumować w przypadku, gdy gracz miałby wybrać bramkę a lub b, wiedząc, że c jest zawsze pusta (usuwamy c z konkursu). Lub gospodarz po odsłonięciu pustej bramki losowałby spośród pozostałych bramek nowe miejsce dla nagrody. Niestety ważne są reguły gry, a problem jest sformułowany inaczej. Poprawny wzór dla danego problemu to P(A|O(c)) = P(A∩O(c)) / P(O(c)), gdzie O(x) oznacza odsłonięcie bramki x.
Jak obliczyć prawdopodobieństwo odsłonięcia bramki c? Jeśli C to O(c) wynosi 0 (gospodarz nigdy nie odsłania bramki z nagrodą). Podobnie, gdy W(c) to O(c) wynosi 0 (nasza bramka nie zostanie odsłonięta). Co jednak, gdy nagroda nie znajduje się w c oraz gracz nie wybierze c? Wprowadźmy jeszcze inne wydarzenie W(x), gdy gracz wybiera bramkę x. Mamy kolejno:
P(W(a)) = P(W(b)) = P(W(c)) = ⅓,bo szansa na wybranie bramki wygrywającej lub przegrywającej jest zawsze taka sama i nie zależy od początkowego wyboru (zdarzenia niezależne). Odsłanianie bramek natomiast, wprost przeciwnie. Spójrzmy:
P(W(a)|A) = P(W(b)|B) = P(W(c)|C) = P(W(c)∩C) / P(C) = ⅓,
P(A|W(a)) = P(B|W(b) = P(C|W(c) = P(C∩W(c)) / P(W(c)) = ⅓,
P(O(c)|W(a)) =również:
= P(O(c)∩W(a)) / P(W(a)) =
= (P(O(c)∩W(a)∩A) + P(O(c)∩W(a)∩B) + P(O(c)∩W(a)∩C)) / P(W(a)) =
= (½ * (⅓ * ⅓) + 1 * (⅓ * ⅓) + 0 * (⅓ * ⅓)) / ⅓ =
= ½ * ⅓ + ⅓
= ½,
P(O(c)|W(b)) = ½,ale:
P(O(c)|W(c)) = 0,co jest zgodne z intuicją, bo jeśli nie wybierzemy bramki c, to szansa, że zostanie ona odsłonięta wynosi 1 do 2. Wynika stąd jeszcze jeden ważny wniosek: aby obliczyć szansę na odsłonięcie danej bramki, potrzebujemy informacji o pierwotnym wyborze, bez niego obliczenie P(O(c)), jak i P(A|O(c)) jest niemożliwe.
Obliczmy więc prawdopodobieństwo bardziej szczegółowych sytuacji: "a wygrywa pod warunkiem, że wybrano a i odsłonięto c" oraz "a wygrywa pod warunkiem, że wybrano b i odsłonięto c".
P(A|W(a)∩O(c)) =co daje nam szansę 1 na 9. Natomiast:
= P(A∩W(a)∩O(c)) / P(W(a)∩O(c)) =
= (⅓ * ⅓ * ½) / ½ = ⅓ * ⅓,
P(A|W(b)∩O(c)) =daje szansę 2 na 9 i jest dwukrotnie bardziej prawdopodobne.
= P(A∩W(b)∩O(c)) / P(W(b)∩O(c)) =
= (⅓ * ⅓ * 1) / ½ = ⅓ * ⅓ * 2,
Wniosek jest następujący: jeśli początkowo wybierzemy bramkę przegrywającą (na co mamy ⅔ szans), to prezenter będzie zmuszony odsłonić drugą przegrywającą bramkę, jednocześnie pozostawiając nam bramkę wygrywającą. W tej sytuacji, zmieniając pierwotny wybór, nagroda trafia w nasze ręce.
Ta strategia zawodzi jedynie wtedy, kiedy mieliśmy to "nieszczęście" trafić od razu bramkę z nagrodą. Wraz ze wzrostem bramek to prawdopodobieństwo maleje i dąży do zera, dlatego łatwo wyobrazić sobie, dlaczego dla 1000 bramek mamy praktycznie wygraną w kieszeni (99.9% szans).
Opierając się na powyższych wywodach prezentuję Bonus dla wytrwałych:
Załóżmy, że mamy pewien proces generujący całkowicie losowe liczby rzeczywiste. Dzięki niemu Alicja wygenerowała liczbę a. Bob (nie znając a), podobnie używając generatora, bądź na własną rękę, uzyskał liczbę rzeczywistą b. Wtedy Alicja mówi: "moja liczba wynosi a lub b". Jakie jest prawdopodobieństwo odgadnięcia przez Boba liczby Alicji?Zagadka jest trywialna. Wiedząc, że możliwych liczb (bramek) jest nieskończenie wiele, jakie jest prawdopodobieństwo, że Bob trafi? A co jeśli liczby są identyczne?
A to Hardkorowy bonus dla wytrwałych, luźno związany z powyższymi rozważaniami:
Alicja w sekrecie wybiera dwie różne liczby rzeczywiste, używając nieznanego procesu generowania liczb całkowicie losowych, a następnie umieszcza je w dwóch (abstrakcyjnych) kopertach. Bob losowo wybiera jedną z kopert (poprzez sprawiedliwy rzut monetą) i pokazuje Ci liczbę z tej koperty. Twoim zadaniem jest odgadnąć czy liczba w drugiej kopercie jest większa czy mniejsza od tej, którą widziałeś.
Czy istnieje strategia, dająca większą niż 50% szansę na poprawne odgadnięcie, bez względu na to jakiego procesu używała Alicja? (źródło: xkcd blog)Ta zagadka jest o wiele ciekawsza. Sugerowane rozwiązanie znajdziesz podążając za linkiem do oryginału. Jednak jeśli wymyślisz coś ciekawego, nie wahaj podzielić się tym w komentarzach ;)
Cheers,
Jurek
Chłopski rozum niejednego zwiódł na manowce, więc o ile jest dobrym źródłem inspiracji, o tyle wartym weryfikacji źródłem dowodów. ;)
ReplyDeleteDobrym przykładem są komentarze do linkowanego przez ciebie problemu kopert i liczb rzeczywistych. O ile nie mam niestety czasu na rozważania nad samym problemem (ani jego rozwiązaniem), to niektórzy z tamtych komentatorów twierdzą, że liczb rzeczywistych większych od 100 jest mniej niż mniejszych. Na "zdrowy" rozum wydaje się to naturalne. Jednak jest ich tyle samo. (z tego też powodu ma przeczucie, że wbrew sprytnej funkcji wykorzystanej do rozwiązania problemu, nie tylko nie da się znaleźć strategii o szansie na wygraną większą niż 50%, co nawet określić szans na wygraną)
trzycwierci
Istotnie czasami może zawieść, tak samo jak intuicja. Jednak jeśli coś na chłopski rozum ma dla mnie sens to zaraz próbuję to sprawdzić prostymi kontrprzykładami. I tak do skutku.
ReplyDeleteCo do problemu kopert to zahacza on o nieskończoności, co dla mnie zawsze było grząskim terenem do rozważań. Ale nawet na chłopski rozum można dojść do wniosku, że dodając do nieskończoności drugą nieskończoność, wciąż otrzymamy coś nieskończonego.
Więc takie porównywanie rozmiarów nieskończoności do niczego według mnie nie prowadzi, póki nie mamy wymiernych wyników między różnicami.
A co do samego problemu to mam zamiar niedługo napisać jakąś prostą pseudo-symulację, co by się empirycznie przekonać czy ta strategia daje wygrane większe niż w 50% przypadków.
Empirycznie przekonasz się tylko dla przypadków skończonych - co nie da ci ŻADNEJ informacji o przypadku nieskończonym. Co prawda trochę upraszczam, ale dla zobrazowania sytuacji porównaj sobie dwa problemy:
ReplyDelete1) Jaka jest szansa wylosowania liczby parzystej ze skończonego zbioru liczb naturalnych od 1 do 2n (gdzie n jest liczbą naturalną)?
2) Jaka jest szansa wylosowania liczby parzystej ze zbioru wszystkich liczb naturalnych?
Różnica jest uderzająca: 1) 1/2, 2) nie da się określić (jako że do tej pory wykazałeś się większą wiedzą z prawdopodobieństwa, zakładam że to wiesz). Więc wątpię, czy uda ci się uzyskać wyniki w jakikolwiek sposób miarodajne (nie mniej z chęcią je poznam ;)).
Dlatego też zastanawiałem się nad lekkim przeformułowaniem treści zadania. Niech Alicja losuje liczbę ze zbioru skończonego, tylko my go nie znamy. Różnica wydaje się być tylko kosmetyczna, ale może nam się udać uniknąć określania prawdopodobieństwa na wszystkich podzbiorach zbioru liczb rzeczywistych (a obawiam się, że to właśnie próbujemy robić w tej surowej wersji). Może - słowo klucz, bo to tylko luźna hipoteza/propozycja, która de facto może też jednak niczego nie zmieniać.
trzycwierci
Nastawienie wybierającego do życia nie ma znaczenia gdyż prawdopodobieństwo w przypadku zbioru 2 elementowego wynosi 50% niezależnie od tego co było wcześniej (tzn. czy były 3, 5 czy 10 bramek). Wiedza o jednej pustej bramce po prostu eliminuje ją ze zbioru możliwych odpowiedzi. Jej prawdopodobieństwo nie przenosi się cudownie na inną bramkę - po prostu znika. Zostaje 1/3 +1/3 czyli przysłowiowe "fifty-fifty". Matematyczne zabawy są fajne i łatwo się nabrać przyjmując fałszywe założenia.
Delete