Po konkursie drugim

Już po konkursie i jego omówieniu otrzymałem dwa kolejne rozwiązania.

Rozwiązanie pierwsze

Z autorem pierwszego sporo czasu spędziłem na dyskusji, bo okazało się, że jego rozwiązanie daje lepsze wyniki niż program p12! Wprawdzie różnica była na poziomie błędu statystycznego, ale jednak zawsze ze wskazaniem na pokonkursowy program! Zmarnowałem sporo czasu autorowi, bo nawet nie próbowałem zrozumieć skąd się to bierze, gdyż cały czas zastanawiałem się, co by mogło być nie tak w tym p12, aż w końcu zrozumiałem: naszym sukcesem nie jest zdarzenie polegające na tym, że wszystkie kolejne liczby będą mniejsze od danej! Sukcesem jest zdarzenie będące sumą dwóch rozłącznych zdarzeń:

  1. wszystkie kolejne liczby będą mniejsze od danej
  2. będzie liczba większa i w kolejnych próbach prawidłowo ją wytypujemy!

Prawdopodobieństwa tych zdarzeń wynoszą odpowiednio p1 i p2. Możemy zapisać znów warunek, że prawdopodobieństwo naszego sukcesu musi być większe od prawdopodobieństwa zdarzenia przeciwnego:

p1+p2 > 1-(p1+p2)

co, po uproszczeniu daje

p1+p2 > 0.5

p1 to znane nam już xn, (gdzie n–liczba liczb, których jeszcze nie znamy), więc

xn + p2 > 0.5

Ponieważ p2 >= 0, więc wynika z tego, że warto się zatrzymywać dla liczb nieco mniejszych niż (jak pierwotnie) pierwiastek n-tego stopnia z 0.5.

Obliczenie p2 nie jest banalne, gdyż p2 jest funkcją dwóch zmiennych: f(x, n).

Autor nadesłanego rozwiązania (akrasuski1) podszedł do tego nieco inaczej, bo porównywał te dwa prawdopodobieństwa i w zależności od tego, które z nich było większe, podejmował decyzję: jeśli większe było prawdopodobieństwo, że nie będzie już większych liczb, to typował x; a jeśli większe było prawdopodobieństwo, że jednak może wystąpić liczba większa i ją dobrze wytypujemy, czekał. Oczywiście, przy następnej liczbie sytuacja się powtarzała.

Linki do rozwiązanie zamieszczam poniżej, a ich mnogość tłumaczę tym, że ich autor włożył naprawdę dużo wysiłku, by przekonać mnie do tego, co w końcu wydaje się oczywiste.

http://pastebin.com/8TQHDXFx
http://pastebin.com/h3c27wpK
http://pastebin.com/7rCWnwuD
Opis rozwiązania
http://pastebin.com/hiwxmUDS
http://pastebin.com/9TdJ6cC8

No i jeszcze wyniki dla miliona zbiorów danych (N=3)

 akrasuski1 accuracy for N=3: 68.437600% (1000000 runs)
         My accuracy for N=3: 68.412100%

Rozwiązanie drugie

Przepraszam autora (pingwindykator), że nie omówię szczegółowo tego rozwiązania, ale P.T. Czytelników zachęcam do zapoznania się z kodem:

https://github.com/pingwindyktator/guessing_machine

Advertisements

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