W postawionej niedawno zagadce pytamy jakie jest prawdopodobieństwo bycia mądrzejszym od każdej z dziewięciu osób wylosowanych z całej populacji wiedząc, że na pewno jesteśmy w górnych 10% tej populacji (ale nie wiadomo w której konkretnie części tych 10%).
Zaczniemy od rozwiązania uproszczonego: skoro nie wiemy w którym kawałku górnego decyla jesteśmy, możemy równie dobrze przyjąć, że jesteśmy w jego połowie (a więc dokładnie na 95%) i sprawdzić ile wynosi prawdopodobieństwo, że nikt z wylosowanych nie trafił powyżej 95%:
0.959≈0.63025 czyli ciut ponad 63%.
Odpowiedź ta jest w przybliżeniu poprawna. Jednak aby rozwiązać zagadkę dokładnie trzeba się jej przyjrzeć nieco bliżej - zobaczymy zaraz, że powyższe przybliżenie daje nam ponad 2% błędu (albo nawet ponad 3%, zależy z której strony patrzeć).
Poprawne rozumowanie przebiega tak:
Spośród 9 wylosowanych osób, część trafi do górnego decyla. Czym więcej ludzi w górnym decylu, tym mniejsze nasze szanse na to, że będziemy wśród nich na samej górze. Po kolei:
- Jeżeli do górnego decyla nie trafi ani jeden człowiek, jesteśmy najmądrzejsi. Szansa, że do górnego decyla nie trafi ani jeden człowiek wynoszą 0.99 czyli ~38.74%.
- Jeżeli do górnego decyla trafi dokładnie jeden z wylosowanych, nasze szanse są pół na pół. Szansa, że do górnego decyla trafi dokładnie jeden człowiek wynosi 0.1 * 0.98 * 9 czyli ~38.74%. Dzielimy to na dwa (bo pół na pół), czyli około 19.37%. A czemu mnożymy przez dziewięć? Bo tyle jest różnych kombinacji, że jedna osoba jest wśród top 10% a reszta nie.
- Jeżeli do górnego decyla trafią dwie osoby, nasze szanse na bycie na topie maleją do 33.(3)%. Szansa na to, że do górnego decyla trafią dwie osoby wynosi 0.12*0.97*36 czyli ~17.21%, a jedna trzecia z tego to okolice 5.74%.
- Jeżeli do górnego decyla trafią trzy osoby...
- Cztery...
- Pięć...
I tak dalej. Uzyskane w każdym kroku procenty sumujemy i na końcu okaże się, że prawdopodobieństwo bycia najmądrzejszym wynosi około 65.13% - i to jest ostatecznie poprawna odpowiedź (zaokrąglona do dwóch miejsc po przecinku). Jest to dwa procent więcej niż rozwiązanie przybliżone zaprezentowane na samym początku. A patrząc od dupy strony, jeżeli w wersji przybliżonej dokonamy niewielkiej zmiany i przesuniemy się o 3.4% "w górę" ze środka naszego decyla, czyli z 50% na 53.4% (a więc z 0.95 na 0.9534), wówczas dziewiąta potęga da nam poprawny wynik - z zadaną dokładnością rzecz jasna.
Oczywiście zamiast ufać matematyce zawsze można przeprowadzić symulację:
from random import random
wygrane = 0
proby = 100000000
for proba in range(proby):
ja = 0.9 + random() / 10
inny_madrala = max([random() for x in range(9)])
if(inny_madrala < ja):
wygrane += 1
print(wygrane / proby)
Powyższy kawałek kodu przeprowadza 100 milionów prób i liczy ile razy byliśmy najmądrzejsi. U mnie po kilku minutach oczekiwania wyszło 0.65126931 (czyli po zaokrągleniu 65.13%)
A jak Wam poszło?
1Tywan był pierwszy (zgłoszenie nadeszło o 7:39 - dokładnie dwie godziny po publikacji zagadki, to chyba rekord), ale poszedł na łatwiznę i nadesłał odpowiedź przybliżoną 63%, popartą obliczeniem 0.959. Nie zaliczam.
2Kilka godzin później głos dał Jaro, który jednak poszedł całkiem dziwną ścieżką i wyszło mu 0.12%. Rzecz jasna nie zaliczam, ale jestem bardzo zaciekawiony tokiem rozumowania:
3Chwilę później odezwał się Stefek Burczymucha, który jednak zamiast wziąć się za bary z zadaniem, obrócił je w krotochwilę z wynikiem 212.98 🙂 Nie zaliczam.
4Tego samego dnia pod wieczór odezwał się Butter, któremu nie działało wysyłanie odpowiedzi przez standardowy formularz więc przesłał bokiem. Odpowiedź 0.2% (w przybliżeniu (1/2)9) - rozumowanie Buttera pomija całkiem naszą przynależność do górnego decyla. Nie zaliczam.
5Następnego dnia rano swoje rozwiązanie (66.66%) przysłał Rozie, który miał ze wszystkich dotyczasowych zawodników największą szansę trafienia w poprawną odpowiedź, ale zaprzepaścił ją z trzech powodów. Symulacje w Pythonie dawały mu wyniki w okolicach 64.5 - 65.5, więc Rozie... zaokrąglił "na czuja" w górę do 2/3. Drugim błędem było przeprowadzenie symulacji na liczbach całkowitych 0-999 zamiast na ułamkach. Trzecim wreszcie - niewielka liczba prób (tylko 100 tysięcy). Szkoda, bo było blisko 🙂 Nie zaliczam.
6Około południa przyszło zgłoszenie Rafała, który powtórzył rozumowanie Tywana. Nie zaliczam.
7Zaraz potem odezwał się Waldek, któremu formularz też nie chciał działać i nadesłał swoje rozwiązanie pocztą. Poprawne! Gratuluję! Metody Waldka tak do końca nie rozumiem (Waldek jest misiem o zdecydowanie większym rozumku od mojego), prezentuję ją tutaj ku potomności. Szacun.
Cześc. Moje rozwiązanie jest błędne i generalnie bez sensu :).
Czy „mądrość” oznacza „inteligencję”? Jeśli nie, to jak się tę mądrość mierzy? Jeśli tak – nie wiem, czy to będzie miało tutaj znaczenie, ale rozkład inteligencji nie jest równomierny, tylko normalny 🙂
Bardzo słuszna uwaga! Faktycznie, w zagadce zabrakło informacji o tym, że rozkład „mądrości” jest równomierny. Do do „mądrość” == „inteligencja” to obydwa pojęcia są na tyle rozmyte znaczeniowo, że szkoda gadać 🙂
Szkoda, że nie wrzuciłeś kodu – nie mam go pod ręką. Wydaje mi się, że użycie liczb całkowitych nie powinno mieć znaczenia. Prędzej właśnie ilość próbek.
W ogóle podszedłem nieco inaczej i każdorazowo losowałem próbkę 1k osobników, następnie obliczałem dolną granicę górnego decyla z tej próbki. Potem losowałem siebie z zakresu od granicy decyla do maksimum i porównywałem wynik z max z 9 wylosowanych z próbki. Było to o tyle złe podejście, że złożone obliczeniowo, więc rzutujące na ilość prób.
OK, dokopałem się do kodu i się potwierdza. Miałem:
c = 0
for k in range(0, 100000):
a = []
b = []
for j in range(0, 1000):
b.append(random.randint(0, 1000000))
b.sort()
for l in range(0, 9):
a.append(b[random.randint(0, 999)])
r = b[random.randint(900, 999)]
if r > max(a):
c += 1
print(c)
Dodatkowa pętla w pętli, służąca do wyznaczania rzeczywistego percentyla jasno widoczna.
Natomiast samo użycie liczb całkowitych nie jest problemem:
import random
wygrane = 0
proby = 10000000
for proba in range(proby):
ja = 900000 + random.randint(0, 100000)
inny_madrala = max([random.randint(0, 1000000) for x in range(9)])
if(inny_madrala < ja):
wygrane += 1
print(wygrane / proby)
Wyniki oscylujące wokół prawidłowego w granicach błędu mamy już po 10 mln prób, nawet używając liczb całkowitych. Choć oczywiście ze względu na ostrą nierówność w warunku madrala < ja przedział mądrości wyrażony całkowicie musi być dość duży. Bez tego zaniży wynik.
skoro losowanie odnosi się tylko do czytelników Ignormatyka z których wszyscy są w tym samym decylu –> mamy więc ustalić, jakie jest prawdopodobieństwo, że jestem najmądrzejszy z grupy 10 osób. tak zrozumiałem zapis.
Ale że to prawdopodobieństwo to nie mam zamiaru się kłócić – niepokoiłby mnie tylko wynik mniejszy od 0 i większy od jedności.
Jesteś jedynym czytelnikiem, o którym wiesz na 100% że jest w górnym decylu…