Nie jest dobrze ;-)

Kilka dni temu mi się w pracy nudziło [niby miałem robotę, ale jakoś nie mogłem wymyślić [zawsze myślałem, że się powinno pisać i mówić wymyśleć, lepiej mi to brzmi] jak się za to zabrać i przeszedłem w tryb losowego błądzenia, czyli zajmowania się innymi rzeczami bo a nóż coś mi podsuną] i zajrzałem na 9 Fingers [taki niby portal dla programistów, ale bardziej to portalik i nie dla programistów a dla studentów szukających rozwiązań do zadań] gdzie ktoś spytał jak napisać kod do losowania 10 niepowtarzających się liczb od 1 do 100.

Napisałem, ale męczyło mnie czy nie byłoby łatwiej po prostu olać możliwość powtórek, w tym celu chciałem sprawdzić jakie jest prawdopodobieństwo takiego zdarzenia.
Nie do końca miałem pomysł jak się za to złapać, bo na 2 czy 3 mi wychodziło, ale nie potrafiłem na szybko zgeneralizować mojego rozwiązania i użyć go do 10 prób ;-)

No i okazało się, że łatwiej mi było napisać programik, który to przetestował niż to rozwiązać po bożemu.

Wyszło mi, że w około 37% przypadków jakaś liczba się powtórzy, czyli nie można tego zignorować [w pierwszym podejściu wyszło mi 5%, ale po przyjrzeniu się kodowi uświadomiłem sobie, że mierzyłem nie ilość przypadków w których doszło do powtórzenia, a "nadmiar" losowań - tu warto zapamiętać, w razie robienia eksperymentu trzeba się kilka razy upewnić czy jego wynikiem jest dokładnie to co nas interesuje ;-), ja miałem sugestię co do tego, że mój pierwszy wynik był zły, bo skoro w przypadku wylosowanych już 9 liczb istnieje blisko 10% szansa wylosowania jednej z nich to w jaki niby sposób łączne prawdopodobieństwo takiego zdarzenia jak konieczność ponownego losowania miała być niższa?]

Zresztą ten pierwszy zły wynik eksperymentu sprowadził mnie na manowce też w wyliczenie tego po bożemu, bo wpadłem na pomysł tylko, że wyniki mi się nie zgadzały z eksperymentem to je odrzuciłem uznając, że skoro eksperyment pokazał coś innego to trudno, moje wnioskowanie było błędne ;-)

Ale wracając do tytułu, że nie jest dobrze ;-)
Nie jest dobrze, że szybciej mi było napisać coś do testowania niż zaatakować problem od strony teoretycznej. [Chociaż w samym robieniu eksperymentu nie ma problemu i to jest dobry pomysł do pierwszego ataku, albo przetestowania teorii... problemem są jednak błędy w eksperymentach ;-)]

Mój dobry program testujący wygląda tak:

import math
import random

SAMPLES = 100000

def test():
 l = {}
 for i in range(0,10):
  r = math.floor(random.random()*100)+1
  l[r]=True
 return len(l)

sum=0
for i in range(0,SAMPLES):
 if test()<10:
  sum=sum+1

print(sum/SAMPLES)

I jak widać jego działanie opiera się przeprowadzeniu pewnej ilości takich wypełnień tablicy 10 elementów :-)

Tu zresztą widać przewagę JavaScriptu nad Pythonem czy dowolnym innym językiem, jako językiem do pisania takich cosiów. Jakby to był JavaScript to dodałbym do tego postu "interaktywną" wersję narzędzia, że każdy mógłby sobie poklikać by zobaczyć efekty.

Jak już dotarłem do tego, że robię błąd w narzędziu do symulacji to wpadłem i na to jak znaleźć wynik teoretycznie ;-)
Jeszcze się w tym upewniłem przejrzawszy w miejscu spania "75 sposobów na statystykę".

Wg. teorii, prawdopodobieństwo powtórzenia się liczby przy losowaniu 10 liczb z zakresu 1 do 100 wynosi też około 37%.
Dochodzimy do tego "od tyłu", czyli sprawdzamy jaka jest szansa, że liczby się nie powtórzą.
Jedna liczba się nie powtórzy, jak są już dwie to może dojść do powtórki, z jakim prawdopodobieństwem? Dokładnie 0.99, bo mamy 99 na 100 liczb takich, których jeszcze nie mieliśmy.
Przy trzeciej liczbie mamy 98 takich liczb i tak dalej.
Ponieważ to czy za 3 razem wylosujemy liczbę powtarzającą się jest niezależne od tego czy zdarzy się to za 2 czy 5 razem to wiemy, że są to zdarzenia niezależne, możemy więc ich prawdopodobieństwa pomnożyć :-)

Czyli (nie umiem zmusić Chrome do narysowania ładnego wzorku z produktem więc będą cyferki tylko ;-)):
P(10 niepowtarzających ze 100)=1-99/100*98/100*97/100*96/100*95/100*94/100*93/100*92/100*91/100=0.3718 :-)

A programik, który to liczy wygląda tak:

prod = 1
for i in range(1,10):
 prod=prod*(100-i)/100
print(1-prod)

Swoją szosą trzeba szlifować algorytmy, bo żeby taki duperelek jak to wyżej sprowadzało na mnie taką niepewność, że muszę posuwać się do pisania programów które to testują?
Wstyd.


Podobne posty^beta
Matematyczne podstawy zakupu skarpetek ;-)
Jak uniknąć zonka ;-)
Losowanie dobre
Transhumanizm [długo i nudno ;-)]
Rankingi, to nie takie proste ;-)