Nie mogę się tym zająć, co jest bardziej przypadkowe?
rand()
LUB :
rand() * rand()
Uważam, że to prawdziwa łamigłówka, czy możesz mi pomóc?
EDYTOWAĆ:
Intuicyjnie wiem, że matematyczna odpowiedź będzie taka, że są one równie losowe, ale nie mogę nie myśleć, że jeśli „uruchomisz algorytm liczb losowych” dwa razy, pomnożąc je razem, stworzysz coś bardziej losowego niż po prostu robienie to raz.
math
language-agnostic
random
Trufa
źródło
źródło
Odpowiedzi:
Tylko wyjaśnienie
Chociaż poprzednie odpowiedzi są poprawne za każdym razem, gdy próbujesz dostrzec losowość zmiennej pseudolosowej lub jej pomnożenie, powinieneś zdawać sobie sprawę, że chociaż Random () jest zwykle równomiernie rozmieszczony, Random () * Random () nie.
Przykład
Jest to próbka jednolitego rozkładu losowego symulowana przez zmienną pseudolosową:
Jest to rozkład, który otrzymujesz po pomnożeniu dwóch zmiennych losowych:
Oba są więc „losowe”, ale ich rozkład jest bardzo różny.
Inny przykład
Podczas gdy 2 * Random () jest równomiernie rozmieszczony:
Random () + Random () nie jest!
Twierdzenie o granicy centralnej
Centralne twierdzenie graniczne stwierdza, że suma random () ma tendencję do rozkładu normalnego jako określenia wzrostu.
W zaledwie czterech terminach otrzymujesz:
I tutaj możesz zobaczyć drogę od rozkładu jednolitego do normalnego, dodając 1, 2, 4, 6, 10 i 20 równomiernie rozmieszczonych zmiennych losowych:
Edytować
Kilka kredytów
Dziękujemy Thomasowi Ahle za zwrócenie uwagi w komentarzach, że rozkłady prawdopodobieństwa pokazane na dwóch ostatnich obrazach są znane jako rozkład Irwina-Halla
Dzięki Heike za jej cudowną funkcję rozdarcia []
źródło
rand()+rand()
, skończyłoby się to dystrybucją typu „2d6” z centrum tłuszczu.Wydaje mi się, że obie metody są tak losowe, chociaż mój gutfeel powiedziałby, że
rand() * rand()
jest mniej losowy, ponieważ dałby więcej zer. Jak tylkorand()
jest0
, suma staje się0
źródło
Ani też nie jest „bardziej losowy”.
rand()
generuje przewidywalny zestaw liczb na podstawie nasion losowych psuedo (zwykle na podstawie bieżącego czasu, który zawsze się zmienia). Pomnożenie dwóch kolejnych liczb w sekwencji generuje inną, ale równie przewidywalną sekwencję liczb.Odpowiedź na pytanie, czy zmniejszy to liczbę kolizji, brzmi „nie”. To faktycznie zwiększy kolizje z powodu efektu pomnożenia dwóch liczb gdzie
0 < n < 1
. Wynik będzie mniejszy, powodując błąd w wyniku w kierunku dolnego końca widma.Kilka dalszych wyjaśnień. W dalszej części „nieprzewidywalne” i „losowe” odnoszą się do zdolności kogoś do odgadnięcia, jaka będzie kolejna liczba na podstawie poprzednich liczb, tj. wyrocznia.
Podane ziarno,
x
które generuje następującą listę wartości:rand()
wygeneruje powyższą listę irand() * rand()
wygeneruje:Obie metody zawsze będą generować tę samą listę liczb dla tego samego nasienia, a zatem są równie przewidywalne przez wyrocznię. Ale jeśli spojrzysz na wyniki pomnożenia dwóch wywołań, zobaczysz, że wszystkie są poniżej,
0.3
pomimo przyzwoitego rozkładu w oryginalnej sekwencji. Liczby są tendencyjne z powodu efektu pomnożenia dwóch ułamków. Wynikowa liczba jest zawsze mniejsza, dlatego znacznie bardziej prawdopodobne jest zderzenie, mimo że jest równie nieprzewidywalne.źródło
rand()+rand()+rand()...
staje się coraz mniej „losowy” (jeśli przez przypadek masz na myśli równomierny rozkład).rand()
że faktycznie jest losowy i nie próbuj „zwiększać” jego losowości. Nie ustawiaj nasion wiele razy. Każde pojedyncze ziarno jest w porządku, o ile samo jest pół losowe. Wiele wdrożeń, które widziałem, wykorzystują epokę UNIX jako zalążek, który zmienia się co sekundę i jest wyjątkowy za każdym razem, gdy się zmienia.Nadmierne uproszczenie w celu zilustrowania punktu.
Załóżmy, że funkcja losowa generuje tylko
0
lub1
.random()
jest jednym z(0,1)
, alerandom()*random()
jest jednym z(0,0,0,1)
Widać wyraźnie, że szanse na uzyskanie
0
w drugim przypadku nie są w żaden sposób równe szansom na uzyskanie1
.Kiedy po raz pierwszy pisał tę odpowiedź chciałem zachować możliwie jak najkrótszy, tak aby osoba czytająca go zrozumie od skrócie różnicę między
random()
arandom()*random()
, ale nie może utrzymać się z odebraniem oryginalny litteram ogłoszenie pytanie:Który jest bardziej losowy?
Jako że
random()
,random()*random()
,random()+random()
,(random()+1)/2
lub jakakolwiek inna kombinacja, która nie prowadzi do stałego związku mają to samo źródło entropii (lub tego samego stanu początkowego w przypadku generatorów pseudolosowych), odpowiedź będzie, że są one równie random (Różnica jest w ich dystrybucji). Doskonałym przykładem, na który możemy spojrzeć, jest gra w Craps. Liczba, którą dostaniesz, byłabyrandom(1,6)+random(1,6)
i wszyscy wiemy, że uzyskanie 7 ma największą szansę, ale to nie znaczy, że wynik rzutu dwiema kostkami jest mniej więcej losowy niż wynik rzutu jedną.źródło
Oto prosta odpowiedź. Rozważ Monopol. Rzucasz dwiema sześciostronnymi kośćmi (lub 2k6 dla tych z was, którzy wolą notację w grze) i bierze ich sumę. Najczęstszym wynikiem jest 7, ponieważ istnieje 6 możliwych sposobów na wyrzucenie 7 (1,6 2,5 3,4 4,3 5,2 i 6,1). Podczas gdy 2 można rzucić tylko na 1,1. Łatwo zauważyć, że rzut 2d6 różni się od rzutu 1d12, nawet jeśli zasięg jest taki sam (ignorując, że można uzyskać 1 na 1d12, punkt pozostaje ten sam). Pomnożenie wyników zamiast ich dodawania spowoduje wypaczenie ich w podobny sposób, przy czym większość wyników znajdzie się w środku zakresu. Jeśli próbujesz zmniejszyć wartości odstające, jest to dobra metoda, ale nie pomoże w wyrównaniu dystrybucji.
(I o dziwo, zwiększy to również niskie rzuty. Zakładając, że twoja losowość zaczyna się od 0, zobaczysz skok na poziomie 0, ponieważ zmieni ona wszystko, co jest drugim rzutem na 0. Rozważ dwie losowe liczby od 0 do 1 (włącznie ) i pomnożenie. Jeśli którykolwiek z wyników jest równy 0, cała rzecz staje się 0 bez względu na inny wynik. Jedynym sposobem na uzyskanie 1 jest to, że oba rzuty są równe 1. W praktyce prawdopodobnie nie miałoby to znaczenia ale tworzy dziwny wykres).
źródło
Obowiązkowe xkcd ...
źródło
Pomóc może myśleć o tym w bardziej dyskretnych liczbach. Zastanów się, czy chcesz generować losowe liczby od 1 do 36, więc zdecydujesz, że najłatwiejszym sposobem jest rzucić dwie jasne, 6-stronne kostki. Dostajesz to:
Mamy więc 36 liczb, ale nie wszystkie z nich są dość reprezentowane, a niektóre wcale nie występują. Liczby w pobliżu środkowej przekątnej (od lewego dolnego rogu do prawego górnego rogu) będą występować z najwyższą częstotliwością.
Te same zasady, które opisują niesprawiedliwy rozkład między kostkami, dotyczą w równym stopniu liczb zmiennoprzecinkowych od 0,0 do 1,0.
źródło
Niektóre rzeczy dotyczące „losowości” są sprzeczne z intuicją.
Zakładając, że rozkład płaski
rand()
jest następujący, otrzymamy rozkłady płaskie:sqrt(rand(range^2))
(rand(range) + rand(range))/2
range - sqrt(rand(range^2))
Istnieje wiele innych sposobów tworzenia określonych krzywych odchylenia. Zrobiłem szybki test
rand() * rand()
i uzyskałem bardzo nieliniowy rozkład.źródło
Większość implementacji rand () ma pewien okres. Tzn. Po ogromnej liczbie wywołań sekwencja się powtarza. Sekwencja
rand() * rand()
powtórzeń w połowie czasu, więc jest w tym sensie „mniej losowa”.Ponadto, bez starannej konstrukcji, wykonywanie arytmetyki na losowych wartościach powoduje mniej losowości. Plakat powyżej cytowany „
rand()
+rand()
+rand()
...” (powiedzmy k razy), który faktycznie będzie miał tendencję do k razy średnią wartość zakresu wartościrand()
. (To losowy spacer z krokami symetrycznymi względem tego środka.)Załóżmy dla konkretności, że funkcja rand () zwraca równomiernie rozłożoną losową liczbę rzeczywistą w zakresie [0,1). (Tak, ten przykład pozwala na nieskończoną precyzję. Nie zmieni to wyniku.) Nie wybrałeś konkretnego języka, a różne języki mogą robić różne rzeczy, ale następująca analiza obejmuje modyfikacje dla dowolnej nieprzewidywalnej implementacji rand ( ). Produkt
rand() * rand()
jest również w zakresie [0,1), ale nie jest już równomiernie rozprowadzany. W rzeczywistości produkt może znajdować się w przedziale [0,1 / 4) tak jak w przedziale [1 / 4,1). Większe mnożenie spowoduje przesunięcie wyniku jeszcze bardziej w kierunku zera. Dzięki temu wynik jest bardziej przewidywalny. W szerokich pociągnięciach bardziej przewidywalny == mniej losowy.Prawie każda sekwencja operacji na jednorodnie losowych danych wejściowych będzie nierównomiernie losowa, co prowadzi do większej przewidywalności. Ostrożnie można pokonać tę właściwość, ale łatwiej byłoby wygenerować równomiernie rozłożoną liczbę losową w żądanym zakresie, niż marnować czas na arytmetykę.
źródło
„losowy” vs. „bardziej losowy” przypomina trochę pytanie, które zero jest bardziej zerowe.
W tym przypadku
rand
jest to PRNG, więc nie jest całkowicie losowy. (w rzeczywistości dość przewidywalne, jeśli nasiona są znane). Pomnożenie go przez inną wartość powoduje, że nie będzie on mniej więcej losowy.Prawdziwy RNG typu kryptograficznego będzie w rzeczywistości losowy. A uruchamianie wartości za pomocą dowolnej funkcji nie może dodawać do niej więcej entropii i może bardzo prawdopodobne, że usuwa entropię, dzięki czemu nie jest już losowa.
źródło
Koncepcja, której szukasz, to „entropia”, „stopień” nieporządku ciągu bitów. Pomysł jest najłatwiejszy do zrozumienia pod względem pojęcia „maksymalnej entropii”.
Przybliżona definicja ciągu bitów o maksymalnej entropii polega na tym, że nie można go wyrazić dokładnie w kategoriach krótszego ciągu bitów (tj. Używając jakiegoś algorytmu, aby rozwinąć mniejszy ciąg z powrotem do pierwotnego ciągu).
Znaczenie maksymalnej entropii dla losowości wynika z faktu, że jeśli wybierzesz liczbę „losową”, prawie na pewno wybierzesz liczbę, której ciąg bitów jest bliski maksymalnej maksymalnej entropii, to znaczy nie można jej skompresować. To jest nasze najlepsze zrozumienie tego, co charakteryzuje „losową” liczbę.
Tak więc, jeśli chcesz utworzyć losową liczbę z dwóch losowych próbek, która jest „dwa razy” losowa, połącz dwa ciągi bitów razem. Praktycznie po prostu umieściłbyś próbki w wysokich i niskich połówkach słowa o podwójnej długości.
Mówiąc prościej, jeśli poczujesz się obleśny randem (), może czasem pomóc w pobraniu kilku próbek razem - chociaż, jeśli naprawdę złamana, nawet ta procedura nie pomoże.
źródło
4
lub binarna @CurtainDog xkcd0100
może być skompresowana do zera. Program dekompresyjny zwróciłby po prostu „4”. To nie staje się mniej losowe niż to. Problem z dilbertem polega na tym, że nie wiemy, czy możemy go skompresować do zera bitów (dekompresując zawsze zwracając „dziewięć”). Może również zwrócić osiem, a następnie możemy skompresować do 1 bitu. Dekompresowanie przez: 0-> dziewięć, 1-> osiem. Mielibyśmy 1 losowy bit.Przyjęta odpowiedź jest całkiem urocza, ale istnieje inny sposób odpowiedzi na twoje pytanie. Odpowiedź PachydermPunchera przyjmuje już to alternatywne podejście i zamierzam go trochę rozwinąć.
Najłatwiejszym sposobem myślenia o teorii informacji jest najmniejsza jednostka informacji, pojedynczy bit.
W standardowej bibliotece C
rand()
zwraca liczbę całkowitą z zakresu od 0 doRAND_MAX
limitu, który może być różnie zdefiniowany w zależności od platformy. ZałóżmyRAND_MAX
, że tak się składa, że2^n - 1
gdzien
jest jakaś liczba całkowita (tak się dzieje w przypadku implementacji Microsoftu, gdzien
jest 15). Powiedzielibyśmy wtedy, że dobra implementacja zwrócin
fragmenty informacji.Wyobraź sobie, że
rand()
konstruuje losowe liczby, przewracając monetę, aby znaleźć wartość jednego bitu, a następnie powtarzając, aż będzie miała partię 15 bitów. Wtedy bity są niezależne (wartość jednego bitu nie wpływa na prawdopodobieństwo, że inne bity w tej samej partii mają pewną wartość). Tak więc każdy bit rozpatrywany niezależnie jest jak liczba losowa od 0 do 1 włącznie i jest „równomiernie rozłożony” w tym zakresie (prawdopodobnie będzie równy 0 jako 1).Niezależność bitów zapewnia, że liczby reprezentowane przez partie bitów będą również równomiernie rozłożone w ich zakresie. Jest to intuicyjnie oczywiste: jeśli jest 15 bitów, dozwolony zakres wynosi od zera do
2^15 - 1
= 32767. Każda liczba w tym zakresie jest unikalnym wzorem bitów, takim jak:a jeśli bity są niezależne, wówczas bardziej prawdopodobne jest, że nie wystąpi żaden wzór niż jakikolwiek inny wzór. Zatem wszystkie możliwe liczby w tym zakresie są jednakowo prawdopodobne. I tak jest odwrotnie: jeśli
rand()
produkuje równomiernie rozmieszczone liczby całkowite, wówczas liczby te składają się z niezależnych bitów.Pomyśl więc o
rand()
linii produkcyjnej do produkcji bitów, która po prostu podaje je w partiach o dowolnej wielkości. Jeśli nie podoba ci się rozmiar, podziel partie na pojedyncze części, a następnie złóż je ze sobą w dowolnych ilościach (jeśli potrzebujesz określonego zakresu, który nie jest potęgą 2, musisz zmniejszyć swoje liczby , a zdecydowanie najłatwiejszym sposobem jest konwersja na zmiennoprzecinkową).Wracając do pierwotnej sugestii, załóżmy, że chcesz przejść od partii 15 do partii 30, zapytaj
rand()
o pierwszą liczbę, przesuń ją o 15 miejsc, a następnie dodaj kolejnąrand()
. Jest to sposób na połączenie dwóch połączeńrand()
bez zakłócania równomiernej dystrybucji. Działa po prostu dlatego, że nie ma nakładania się lokalizacji, w których umieszczasz fragmenty informacji.Różni się to bardzo od „rozciągania” zakresu
rand()
przez pomnożenie przez stałą. Na przykład, jeśli chcesz podwoić zasięg,rand()
możesz pomnożyć przez dwa - ale teraz otrzymujesz tylko liczby parzyste, a nigdy nieparzyste! To nie jest dokładnie płynna dystrybucja i może być poważnym problemem w zależności od aplikacji, np. Gra w ruletkę podobno dopuszcza zakłady nieparzyste / parzyste. (Myśląc w kategoriach bitów, unikniesz tego błędu intuicyjnie, ponieważ zdasz sobie sprawę, że pomnożenie przez dwa jest równoznaczne z przesunięciem bitów w lewo (większe znaczenie) o jedno miejsce i wypełnienie luki zerem. Więc oczywiście ilość informacji jest taka sama - po prostu trochę się poruszyła.)Takich luk w zakresach liczbowych nie można uchwycić w aplikacjach liczb zmiennoprzecinkowych, ponieważ zakresy liczb zmiennoprzecinkowych z natury mają w sobie luki, których po prostu nie można w ogóle przedstawić: istnieje nieskończona liczba brakujących liczb rzeczywistych w przerwie między każdym z dwóch reprezentatywnych liczb zmiennoprzecinkowych numery punktowe! Więc i tak musimy nauczyć się żyć z lukami.
Jak ostrzegają inni, intuicja jest ryzykowna w tym obszarze, szczególnie dlatego, że matematycy nie są w stanie oprzeć się urokowi prawdziwych liczb, które są strasznie mylące rzeczy pełne srogich nieskończoności i pozornych paradoksów.
Ale przynajmniej jeśli myślisz, że jest to bit, intuicja może cię jeszcze posunąć. Bity są naprawdę łatwe - nawet komputery mogą je zrozumieć.
źródło
Jak powiedzieli inni, prosta krótka odpowiedź brzmi: nie, nie jest bardziej losowa, ale zmienia rozkład.
Załóżmy, że grałeś w kości. Masz całkiem całkiem losowe kości. Czy rzuty byłyby „bardziej losowe”, gdyby przed każdym rzutem rzuciłbyś dwie kostki do miski, potrząsnąłeś nią, wybrałeś jedną losową kostkę, a następnie rzucił ją? Oczywiście nie miałoby to znaczenia. Jeśli obie kości dadzą losowe liczby, losowe wybranie jednej z dwóch kości nie będzie miało znaczenia. Tak czy inaczej, otrzymasz losową liczbę od 1 do 6 z równomiernym rozkładem na wystarczającą liczbę rzutów.
Podejrzewam, że taka procedura może być przydatna, jeśli podejrzewasz, że kości NIE są sprawiedliwe. Jeśli powiedzmy, że kości są nieco niezrównoważone, więc jeden ma tendencję do dawania 1 częściej niż 1/6 czasu, a inny ma tendencję do dawania 6 niezwykle często, wówczas losowe wybieranie między nimi może zaciemniać tendencyjność. (Chociaż w tym przypadku 1 i 6 nadal występowałyby więcej niż 2, 3, 4 i 5. Cóż, myślę, że w zależności od charakteru nierównowagi.)
Istnieje wiele definicji losowości. Jedną z definicji losowej serii jest to, że jest to seria liczb wytworzona przez losowy proces. Według tej definicji, jeśli rzucę rzetelną kostką 5 razy i otrzymam liczby 2, 4, 3, 2, 5, jest to losowa seria. Jeśli następnie rzucę 5 razy tę samą uczciwą kością i otrzymam 1, 1, 1, 1, 1, to będzie to również losowa seria.
Kilka plakatów wskazało, że funkcje losowe na komputerze nie są tak naprawdę losowe, ale raczej pseudolosowe, a jeśli znasz algorytm i ziarno, są one całkowicie przewidywalne. To prawda, ale przez większość czasu zupełnie nieistotna. Jeśli potasuję talię kart, a następnie odwrócę je pojedynczo, powinna to być losowa seria. Jeśli ktoś zerknie na karty, wynik będzie całkowicie przewidywalny, ale według większości definicji losowości nie spowoduje to, że będzie mniej losowy. Jeśli seria przejdzie statystyczne testy losowości, fakt, że zajrzałem do kart, nie zmieni tego faktu. W praktyce, jeśli gramy dużymi sumami pieniędzy w Twoją zdolność odgadnięcia następnej karty, to fakt, że rzuciłeś okiem na karty, jest bardzo istotny. Jeśli używamy tej serii do symulacji wyborów menu odwiedzających naszą stronę internetową w celu przetestowania wydajności systemu, to fakt, że zerknąłeś nie zrobi żadnej różnicy. (Dopóki nie zmodyfikujesz programu, aby skorzystać z tej wiedzy).
EDYTOWAĆ
Nie sądzę, żebym mógł wypowiedzieć się w sprawie Monty Hall w komentarzu, więc zaktualizuję swoją odpowiedź.
Dla tych, którzy nie czytali linku Belizariusz, jego sedno brzmi: uczestnik teleturnieju ma do wyboru 3 drzwi. Za jednym jest cenna nagroda, za innymi coś bezwartościowego. On wybiera drzwi # 1. Przed ujawnieniem, czy jest zwycięzcą, czy przegranym, gospodarz otwiera drzwi # 3, aby ujawnić, że jest przegrany. Następnie daje zawodnikowi możliwość przejścia do drzwi # 2. Czy zawodnik powinien to zrobić, czy nie?
Odpowiedź, która obraża intuicję wielu ludzi, brzmi: powinien się zmienić. Prawdopodobieństwo, że jego pierwotnym wyborem był zwycięzca, wynosi 1/3, a drugie drzwi są zwycięzcą - 2/3. Moją początkową intuicją, podobnie jak wielu innych ludzi, jest to, że zmiana nie przyniosłaby korzyści, że szanse zostały właśnie zmienione na 50:50.
W końcu załóżmy, że ktoś włączył telewizor tuż po tym, jak gospodarz otworzył przegrywające drzwi. Ta osoba zobaczy dwoje pozostałych zamkniętych drzwi. Zakładając, że zna naturę gry, powiedziałby, że istnieje 1/2 szansy, że każde drzwi ukryją nagrodę. Jak szanse widza mogą wynosić 1/2: 1/2, podczas gdy szanse zawodnika wynoszą 1/3: 2/3?
Naprawdę musiałem o tym pomyśleć, aby ukształtować intuicję. Aby sobie z tym poradzić, zrozum, że kiedy mówimy o prawdopodobieństwach w takim problemie, mamy na myśli prawdopodobieństwo, które przypisujesz, biorąc pod uwagę dostępne informacje. Dla członka załogi, który odłożył nagrodę za, powiedzmy, drzwi nr 1, prawdopodobieństwo, że nagroda znajduje się za drzwiami nr 1, wynosi 100%, a prawdopodobieństwo, że stoi ona za którymś z pozostałych dwóch drzwi, wynosi zero.
Szanse członka załogi są inne niż szanse zawodnika, ponieważ wie coś, czego on nie wie, a mianowicie, za które drzwi postawił nagrodę. Podobnie, szanse zawodnika są inne niż szanse widza, ponieważ wie on coś, czego widz nie wie, a mianowicie, jakie drzwi początkowo wybrał. Nie jest to bez znaczenia, ponieważ wybór gospodarza, które drzwi mają zostać otwarte, nie jest przypadkowy. Nie otworzy drzwi, które wybrał zawodnik, i nie otworzy drzwi, w których ukrywa się nagroda. Jeśli są to te same drzwi, pozostawiają mu dwie możliwości. Jeśli są to różne drzwi, pozostawia tylko jedne.
Jak więc wymyślić 1/3 i 2/3? Kiedy zawodnik pierwotnie wybrał drzwi, miał 1/3 szansy na wyłonienie zwycięzcy. Myślę, że to jest oczywiste. Oznacza to, że istniała 2/3 szansa, że jedno z pozostałych drzwi wygra. Gdyby gospodarz gra dla niego możliwość zmiany bez podania dodatkowych informacji, nie byłoby żadnego zysku. To znowu powinno być oczywiste. Ale jednym ze sposobów na to jest stwierdzenie, że istnieje 2/3 szansy na wygraną przez zmianę. Ale ma 2 alternatywy. Tak więc każdy ma tylko 2/3 podzielone przez 2 = 1/3 szansy na zwycięstwo, co nie jest lepsze niż jego pierwotny typ. Oczywiście, znaliśmy już końcowy wynik, to po prostu oblicza go w inny sposób.
Ale teraz gospodarz ujawnia, że jedna z tych dwóch opcji nie jest zwycięzcą. Tak więc z 2/3 szansy, że drzwi, których nie wybrał, są zwycięzcami, teraz wie, że 1 z 2 alternatyw nie jest. Drugi może, ale nie musi. Więc nie ma już 2/3 podzielonej przez 2. Ma zero dla otwartych drzwi i 2/3 dla zamkniętych drzwi.
źródło
Weź pod uwagę, że masz prosty problem z rzucaniem monetą, w którym parzyste uważa się za główki, a parzyste za ogony. Logiczna implementacja to:
Przy wystarczająco dużym rozkładzie liczba liczb parzystych powinna być równa liczbie liczb nieparzystych.
Rozważmy teraz drobną poprawkę:
Jeśli jeden z wyników jest parzysty, to cały wynik powinien być parzysty. Rozważ 4 możliwe wyniki (parzyste * parzyste = parzyste, parzyste * nieparzyste = parzyste, nieparzyste * parzyste = parzyste, nieparzyste * nieparzyste = nieparzyste). Teraz, przy wystarczająco dużej dystrybucji, odpowiedź powinna wynosić nawet 75% czasu.
Obstawiłbym głowy, gdybym był tobą.
Ten komentarz jest raczej wyjaśnieniem, dlaczego nie powinieneś implementować niestandardowej funkcji losowej opartej na twojej metodzie, niż dyskusją na temat matematycznych właściwości losowości.
źródło
rand()%2
może nie być losowy; to naprawdę zależy od losowości niskiego bitu, a niektóre PRNG nie są zbyt dobre w ten sposób. (Oczywiście w niektórych językach wynik jest zmiennoprzecinkowy,rand()
więc w ogóle nie można tego zrobić w ten sposób…)W razie wątpliwości co do tego, co stanie się z kombinacjami liczb losowych, możesz skorzystać z lekcji, których nauczyłeś się w teorii statystycznej.
W sytuacji OP chce wiedzieć, jaki jest wynik X * X = X ^ 2, gdzie X jest zmienną losową rozmieszczoną wzdłuż Uniformu [0,1]. Wykorzystamy technikę CDF, ponieważ jest to mapowanie jeden na jeden.
Ponieważ X ~ Uniform [0,1] cdf to: f X (x) = 1 Chcemy transformacji Y <- X ^ 2, więc y = x ^ 2 Znajdź odwrotność x (y): sqrt (y) = x daje nam to x jako funkcję y. Następnie znajdź pochodną dx / dy: d / dy (sqrt (y)) = 1 / (2 sqrt (y))
Rozkład Y podano jako: f Y (y) = f X (x (y)) | dx / dy | = 1 / (2 sqrt (y))
Jeszcze nie skończyliśmy, musimy uzyskać domenę Y. ponieważ 0 <= x <1, 0 <= x ^ 2 <1, więc Y jest w zakresie [0, 1). Jeśli chcesz sprawdzić, czy pdf Y jest rzeczywiście pdf, zintegruj go w domenie: Zintegruj 1 / (2 sqrt (y)) od 0 do 1 i rzeczywiście wyskakuje jako 1. Również zwróć uwagę na kształt wspomniana funkcja wygląda jak opublikowana przez belizariusza.
Jeśli chodzi o rzeczy takie jak X 1 + X 2 + ... + X n , (gdzie X i ~ Uniform [0,1]) możemy po prostu odwołać się do centralnego twierdzenia granicznego, które działa dla każdego rozkładu, którego momenty istnieją. Dlatego faktycznie istnieje test Z.
Inne techniki określania wynikowego pdf obejmują transformację Jakobian (która jest uogólnioną wersją techniki cdf) i technikę MGF.
EDYCJA: Jako wyjaśnienie, zauważ, że mówię o rozkładzie wynikowej transformacji, a nie o jej losowości . To właściwie na osobną dyskusję. To, co faktycznie wyprowadziłem, było dla (rand ()) ^ 2. W przypadku rand () * rand () jest to o wiele bardziej skomplikowane, co w żadnym wypadku nie spowoduje jednolitego rozkładu jakiegokolwiek rodzaju.
źródło
Nie jest to do końca oczywiste, ale
rand()
zazwyczaj jest bardziej losowe niżrand()*rand()
. Ważne jest to, że tak naprawdę nie jest to bardzo ważne w przypadku większości zastosowań.Ale po pierwsze, wytwarzają różne rozkłady. Nie jest to problemem, jeśli tego właśnie chcesz, ale ma to znaczenie. Jeśli potrzebujesz określonej dystrybucji, zignoruj całe pytanie „które jest bardziej losowe”. Dlaczego więc jest
rand()
bardziej losowy?Trzon dlaczego
rand()
jest bardziej losowy (przy założeniu, że generuje zmiennoprzecinkowe liczby losowe o zakresie [0..1], co jest bardzo powszechne) polega na tym, że mnożąc dwie liczby FP wraz z dużą ilością informacji w mantysie, otrzymujesz pewna utrata informacji na końcu; po prostu nie ma wystarczającej ilości bitów w pływakach podwójnej precyzji IEEE, aby pomieścić wszystkie informacje, które były w dwóch pływakach podwójnej precyzji IEEE, losowo wybranych losowo z [0..1], i te dodatkowe bity informacji są tracone. Oczywiście nie ma to większego znaczenia, ponieważ (prawdopodobnie) nie zamierzałeś korzystać z tych informacji, ale strata jest prawdziwa. Nie ma też tak naprawdę znaczenia, jaką dystrybucję tworzysz (tj. Jaką operację wykonujesz, aby wykonać kombinację). Każda z tych liczb losowych ma (co najwyżej) 52 bity losowej informacji - że „Większość zastosowań liczb losowych nie wykorzystuje nawet takiej losowości, jaka jest faktycznie dostępna w losowym źródle. Zdobądź dobry PRNG i nie przejmuj się tym zbytnio. (Poziom „dobroci” zależy od tego, co z nim robisz; musisz zachować ostrożność, wykonując symulację lub kryptografię Monte Carlo, ale w przeciwnym razie prawdopodobnie możesz użyć standardowego PRNG, ponieważ zwykle jest to znacznie szybsze.)
źródło
Liczby zmiennoprzecinkowe są generalnie oparte na algorytmie, który generuje liczbę całkowitą od zera do pewnego zakresu. Jako taki, używając rand () * rand (), zasadniczo mówisz int_rand () * int_rand () / rand_max ^ 2 - co oznacza, że wykluczasz dowolną liczbę pierwszą / rand_max ^ 2.
To znacznie zmienia losowy rozkład.
rand () jest równomiernie dystrybuowany w większości systemów i jest trudny do przewidzenia, jeśli zostanie poprawnie zaszczepiony. Użyj tego, chyba że masz konkretny powód, aby na nim wykonywać matematykę (tj. Kształtować rozkład do potrzebnej krzywej).
źródło
rand()*rand()
jest mniejsza niż przestrzeń wynikówrand()
- ponieważ nie obejmuje liczb pierwszych.Mnożenie liczb skończyłoby się mniejszym zakresem rozwiązań, w zależności od architektury komputera.
Jeśli wyświetlacz komputera pokazuje 16 cyfr
rand()
, powiedzmy 0,1234567890123 pomnożonych przez sekundęrand()
, 0,1234567890123, dałby 0,0152415 coś, co na pewno znalazłbyś mniej rozwiązań, gdybyś powtórzył eksperyment 10 ^ 14 razy.źródło
Większość tych dystrybucji ma miejsce, ponieważ musisz ograniczyć lub znormalizować liczbę losową.
Normalizujemy go, aby był dodatni, mieścił się w zakresie, a nawet pasował do ograniczeń wielkości pamięci dla przypisanego typu zmiennej.
Innymi słowy, ponieważ musimy ograniczyć losowe wywołanie od 0 do X (X jest granicą wielkości naszej zmiennej), będziemy mieć grupę „losowych” liczb od 0 do X.
Teraz, gdy dodasz liczbę losową do innej liczby losowej, suma będzie wynosić między 0 a 2X ... to wypaczy wartości od punktów krawędzi (prawdopodobieństwo dodania dwóch małych liczb razem i dwóch dużych liczb razem jest bardzo małe, gdy masz dwie losowe liczby z dużego zakresu).
Pomyśl o przypadku, w którym masz liczbę zbliżoną do zera i dodasz ją z kolejną liczbą losową, z pewnością będzie ona większa i oddalona od zera (będzie to prawdą w przypadku dużych liczb, a także prawdopodobnie nie będzie dwóch dużych liczb (liczby zbliżone do X) zwrócone dwukrotnie przez funkcję Random.
Teraz, gdyby ustawić metodę losową z liczbami ujemnymi i dodatnimi (rozciągającymi się równo na osi zerowej), nie byłoby to już prawdą.
Powiedzmy na przykład
RandomReal({-x, x}, 50000, .01)
, że uzyskasz równomierny rozkład liczb po stronie ujemnej, po stronie dodatniej, a jeśli dodasz liczby losowe, zachowają one swoją „losowość”.Teraz nie jestem pewien, co by się stało z
Random() * Random()
rozpiętością od ujemnej do dodatniej ... to byłby interesujący wykres do zobaczenia ... ale muszę teraz wrócić do pisania kodu. :-Pźródło
Nie ma czegoś bardziej losowego. Jest albo losowy, albo nie. Losowy oznacza „trudny do przewidzenia”. Nie oznacza to niedeterministycznego. Zarówno random (), jak i random () * random () są jednakowo losowe, jeśli random () jest losowy. Dystrybucja nie ma znaczenia, jeśli chodzi o losowość. Jeśli występuje nierównomierny rozkład, oznacza to po prostu, że niektóre wartości są bardziej prawdopodobne niż inne; wciąż są nieprzewidywalne.
Ponieważ w grę wchodzi pseudolosowość, liczby są bardzo deterministyczne. Jednak pseudolosowość jest często wystarczająca w modelach prawdopodobieństwa i symulacjach. Powszechnie wiadomo, że skomplikowanie generatora liczb pseudolosowych utrudnia tylko analizę. Jest mało prawdopodobne, aby poprawić losowość; często powoduje to, że nie przejdzie testów statystycznych.
Ważne są pożądane właściwości liczb losowych: powtarzalność i odtwarzalność, statystyczna losowość (zwykle) równomiernie rozłożona, a duży okres to kilka.
Odnośnie transformacji na liczbach losowych: jak ktoś powiedział, suma dwóch lub więcej równomiernie rozmieszczonych wyników daje rozkład normalny. Jest to addytywne twierdzenie o limicie centralnym. Ma zastosowanie niezależnie od dystrybucji źródłowej, o ile wszystkie dystrybucje są niezależne i identyczne. mnożnikowycentralne twierdzenie graniczne mówi, że iloczyn dwóch lub więcej niezależnych i losowo rozmieszczonych zmiennych losowych jest logarytmiczny. Wykres utworzony przez kogoś innego wygląda wykładniczo, ale jest naprawdę nietypowy. Tak więc random () * random () jest logarytmicznie rozłożony (chociaż może nie być niezależny, ponieważ liczby są pobierane z tego samego strumienia). Może to być pożądane w niektórych aplikacjach. Jednak zwykle lepiej jest wygenerować jedną liczbę losową i przekształcić ją w logarytmicznie rozłożoną liczbę. Random () * random () może być trudny do analizy.
Aby uzyskać więcej informacji, zajrzyj do mojej książki na www.performorama.org. Książka jest w budowie, ale odpowiedni materiał jest już dostępny. Pamiętaj, że numery rozdziałów i rozdziałów mogą z czasem ulec zmianie. Rozdział 8 (teoria prawdopodobieństwa) - sekcje 8.3.1 i 8.3.3, rozdział 10 (liczby losowe).
źródło
Możemy porównać dwie tablice liczb dotyczące losowości, stosując złożoność Kołmogorowa. Jeśli nie można skompresować sekwencji liczb, to jest ona najbardziej losowa, jaką możemy osiągnąć przy tej długości ... Wiem, że ten rodzaj pomiaru jest bardziej teoretyczny opcja...
źródło
Właściwie, kiedy myślisz o tym,
rand() * rand()
jest mniej przypadkowa niżrand()
. Dlatego.Zasadniczo istnieje taka sama liczba liczb nieparzystych jak liczba parzysta. Mówiąc, że 0,04325 jest nieparzysty i jak 0,388 jest parzysty, a 0,4 jest parzysty, a 0,15 jest nieparzysty,
Oznacza to, że
rand()
ma równe szanse na uzyskanie parzystej lub nieparzystej liczby dziesiętnej .Z drugiej strony
rand() * rand()
szanse są nieco inaczej ułożone. Powiedzmy:a
ib
oba mają 50% szans na bycie parzystym lub nieparzystym. Wiedząc tooznacza, że istnieje 75% szansa, że
c
jest parzysta, a tylko 25% szansa jest nieparzysta, dzięki czemu wartość jestrand() * rand()
bardziej przewidywalna niżrand()
, a zatem mniej losowa.źródło
rand()
zwykle podaje liczbę od 0 do 1. Czy mówienie o tym, czy jest parzyste czy nieparzyste, ma sens?0.2*0.2=0.04
co sugeruje podstawową wadę tego podejścia: pomnożenie 53 bitów z dwóch podwójnych da w wyniku około 100 bitów. Ale ostatnia połowa tych bitów zostanie odrzucona. Tak więc, jeśli weźmiesz dwa podwójne z 1 jako najmniej znaczącym bitem, nie możesz nic powiedzieć o najmniej znaczącym fragmencie ich produktu.rand()
jest taka sama, jak definicja „parzystej” i „nieparzystej”, która ma sens dla rozkładu zrand()*rand()
. Jeśli tak nie jest, ten argument nie powiedzie się. Dotyczy to liczb całkowitych, ale nie są to liczby całkowite.Użyj rejestru przesuwnego z liniowym sprzężeniem zwrotnym (LFSR), który implementuje prymitywny wielomian.
Wynikiem będzie sekwencja 2 ^ n liczb pseudolosowych, tzn. Żadna z nich nie będzie powtarzana w sekwencji, w której n jest liczbą bitów w LFSR .... co powoduje jednolity rozkład.
http://en.wikipedia.org/wiki/Linear_feedback_shift_register http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
Użyj „losowego” ziarna na podstawie mikrosekund zegara komputera lub może podzbioru wyniku md5 na ciągle zmieniających się danych w systemie plików.
Na przykład 32-bitowy LFSR wygeneruje 2 ^ 32 unikatowe liczby w sekwencji (nie 2 podobne), zaczynając od danego ziarna. Sekwencja zawsze będzie w tej samej kolejności, ale punkt początkowy będzie inny (oczywiście) dla różnych nasion. Tak więc, jeśli ewentualnie powtarzająca się sekwencja między siewkami nie stanowi problemu, może to być dobry wybór.
Użyłem 128-bitowych LFSR do generowania losowych testów w symulatorach sprzętowych przy użyciu zarodka, który jest wynikiem md5 przy ciągłej zmianie danych systemowych.
źródło
Zakładając, że
rand()
zwraca liczbę pomiędzy[0, 1)
, jest oczywiste, żerand() * rand()
będzie tendencyjny w kierunku 0. Jest tak, ponieważ pomnożeniex
przez liczbę między[0, 1)
spowoduje, że liczba będzie mniejsza niżx
. Oto rozkład 10000 kolejnych liczb losowych:Pokaż fragment kodu
Jeśli
rand()
zwraca liczbę całkowitą między,[x, y]
to masz następujący rozkład. Zwróć uwagę na liczbę wartości nieparzystych w porównaniu do parzystych:Pokaż fragment kodu
źródło
OK, więc postaram się dodać pewną wartość, aby uzupełnić inne odpowiedzi, mówiąc, że tworzysz i używasz generatora liczb losowych.
Generatory liczb losowych to urządzenia (w bardzo ogólnym sensie), które mają wiele charakterystyk, które można modyfikować w celu dopasowania do określonego celu. Niektóre z nich (ode mnie) to:
W większości odpowiedzi rozkład jest głównym przedmiotem zainteresowania, ale poprzez mieszanie i dopasowywanie funkcji i parametrów tworzysz nowe sposoby generowania liczb losowych, które będą miały różne cechy, dla których ocena może nie być oczywista na pierwszy rzut oka.
źródło
Łatwo jest wykazać, że suma dwóch liczb losowych niekoniecznie jest losowa. Wyobraź sobie, że masz 6-stronną kostkę i rzuć. Każda liczba ma szansę pojawienia się w 1/6. Teraz powiedz, że miałeś 2 kości i zsumował wynik. Rozkład tych kwot nie wynosi 1/12. Dlaczego? Ponieważ niektóre liczby pojawiają się bardziej niż inne. Istnieje wiele partycji . Na przykład liczba 2 jest sumą tylko 1 + 1, ale 7 może być utworzone przez 3 + 4 lub 4 + 3 lub 5 + 2 itd., Więc ma większą szansę na pojawienie się.
Dlatego zastosowanie transformacji, w tym przypadku dodanie funkcji losowej, nie czyni jej bardziej losową lub niekoniecznie zachowuje losowość. W przypadku kości powyżej rozkład jest przekrzywiony do 7, a zatem mniej losowy.
źródło
Jak już zauważyli inni, na to pytanie trudno odpowiedzieć, ponieważ każdy z nas ma w głowie swój własny obraz losowości .
Dlatego bardzo polecam poświęcić trochę czasu i przeczytać tę stronę, aby uzyskać lepszy obraz losowości:
Wróćmy do prawdziwego pytania. W tym terminie nie ma mniej lub bardziej losowych:
oba wydają się losowe !
W obu przypadkach - tylko rand () lub rand () * rand () - sytuacja jest taka sama: po kilku miliardach liczb sekwencja się powtórzy (!) . To pojawia się losowo do obserwatora, ponieważ nie zna całą sekwencję, ale komputer ma żadnej prawdziwej losowego źródła - więc nie może produkować albo przypadkowość.
np .: czy pogoda jest losowa? Nie mamy wystarczającej liczby czujników ani wiedzy, aby ustalić, czy pogoda jest przypadkowa, czy nie.
źródło
Odpowiedź brzmi: to zależy, mam nadzieję, że rand () * rand () będzie bardziej losowy niż rand (), ale jako:
Cóż, jeśli zaznaczysz którykolwiek z powyższych, sugeruję skorzystanie z prostej „rand ()”. Ponieważ twój kod byłby bardziej czytelny (nie zadawałby sobie pytania, dlaczego to napisałeś, przez ... cóż ... ponad 2 sekundy), łatwy w utrzymaniu (jeśli chcesz zastąpić swoją funkcję randową super_randem).
Jeśli chcesz mieć lepszy losowy, poleciłbym go przesyłać strumieniowo z dowolnego źródła, które zapewnia wystarczającą ilość szumów ( radio statyczne ), a wtedy wystarczy zwykły
rand()
.źródło