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.

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ą:

        BarChart[BinCounts[RandomReal[{0, 1}, 50000], 0.01]]

Jest to rozkład, który otrzymujesz po pomnożeniu dwóch zmiennych losowych:

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] * 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

Oba są więc „losowe”, ale ich rozkład jest bardzo różny.

Inny przykład

Podczas gdy 2 * Random () jest równomiernie rozmieszczony:

        BarChart[BinCounts[2 * RandomReal[{0, 1}, 50000], 0.01]]

Random () + Random () nie jest!

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

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:

BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000] +
                   Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000],
                   {50000}],
         0.01]]  

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 []

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 tylko rand()jest 0, suma staje się0

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, xktóre generuje następującą listę wartości:

0.3, 0.6, 0.2, 0.4, 0.8, 0.1, 0.7, 0.3, ...

rand()wygeneruje powyższą listę i rand() * rand()wygeneruje:

0.18, 0.08, 0.08, 0.21, ...

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.3pomimo 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.

Nadmierne uproszczenie w celu zilustrowania punktu.

Załóżmy, że funkcja losowa generuje tylko 0lub 1.

random()jest jednym z (0,1), ale random()*random()jest jednym z(0,0,0,1)

Widać wyraźnie, że szanse na uzyskanie 0w drugim przypadku nie są w żaden sposób równe szansom na uzyskanie 1.

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()a random()*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)/2lub 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łaby random(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ą.

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).

Obowiązkowe xkcd ...

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:

     1    2    3    4    5    6
  -----------------------------
1|   1    2    3    4    5    6
2|   2    4    6    8   10   12
3|   3    6    9   12   15   18
4|   4    8   12   16   20   24   
5|   5   10   15   20   25   30
6|   6   12   18   24   30   36

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.

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:

• wysoka stronniczość: sqrt(rand(range^2))
• odchylenie osiągające szczyt: (rand(range) + rand(range))/2
• niski: stronniczość: 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.

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ści rand(). (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ę.

„losowy” vs. „bardziej losowy” przypomina trochę pytanie, które zero jest bardziej zerowe.

W tym przypadku randjest 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.

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.

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 do RAND_MAXlimitu, który może być różnie zdefiniowany w zależności od platformy. Załóżmy RAND_MAX, że tak się składa, że 2^n - 1gdzie njest jakaś liczba całkowita (tak się dzieje w przypadku implementacji Microsoftu, gdzie njest 15). Powiedzielibyśmy wtedy, że dobra implementacja zwróci nfragmenty 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:

010110101110010

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ć.

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.

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:

rand() mod 2

Przy wystarczająco dużym rozkładzie liczba liczb parzystych powinna być równa liczbie liczb nieparzystych.

Rozważmy teraz drobną poprawkę:

rand() * rand() mod 2

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.

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 ₁ + X ₂ + ... + 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.

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.)

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).

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.

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

1. 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.

2. 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.

3. 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.

4. 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).

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...

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:

double a = rand();
double b = rand();
double c = a * b;

ai boba mają 50% szans na bycie parzystym lub nieparzystym. Wiedząc to

• parzysty * parzysty = parzysty
• parzysty * nieparzysty = parzysty
• nieparzysty * nieparzysty = nieparzysty
• nieparzysty * parzysty = parzysty

oznacza, że ​​istnieje 75% szansa, że cjest parzysta, a tylko 25% szansa jest nieparzysta, dzięki czemu wartość jest rand() * rand()bardziej przewidywalna niż rand(), a zatem mniej losowa.

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.

Zakładając, że rand()zwraca liczbę pomiędzy [0, 1), jest oczywiste, że rand() * rand()będzie tendencyjny w kierunku 0. Jest tak, ponieważ pomnożenie xprzez liczbę między [0, 1)spowoduje, że liczba będzie mniejsza niż x. Oto rozkład 10000 kolejnych liczb losowych:

google.charts.load("current", { packages: ["corechart"] });
google.charts.setOnLoadCallback(drawChart);

function drawChart() {
  var i;
  var randomNumbers = [];
  for (i = 0; i < 10000; i++) {
    randomNumbers.push(Math.random() * Math.random());
  }
  var chart = new google.visualization.Histogram(document.getElementById("chart-1"));
  var data = new google.visualization.DataTable();
  data.addColumn("number", "Value");
  randomNumbers.forEach(function(randomNumber) {
    data.addRow([randomNumber]);
  });
  chart.draw(data, {
    title: randomNumbers.length + " rand() * rand() values between [0, 1)",
    legend: { position: "none" }
  });
}

<script src="https://www.gstatic.com/charts/loader.js"></script>

<div id="chart-1" style="height: 500px">Generating chart...</div>

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:

google.charts.load("current", { packages: ["corechart"] });
google.charts.setOnLoadCallback(drawChart);
document.querySelector("#draw-chart").addEventListener("click", drawChart);

function randomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function drawChart() {
  var min = Number(document.querySelector("#rand-min").value);
  var max = Number(document.querySelector("#rand-max").value);
  if (min >= max) {
    return;
  }
  var i;
  var randomNumbers = [];
  for (i = 0; i < 10000; i++) {
    randomNumbers.push(randomInt(min, max) * randomInt(min, max));
  }
  var chart = new google.visualization.Histogram(document.getElementById("chart-1"));
  var data = new google.visualization.DataTable();
  data.addColumn("number", "Value");
  randomNumbers.forEach(function(randomNumber) {
    data.addRow([randomNumber]);
  });
  chart.draw(data, {
    title: randomNumbers.length + " rand() * rand() values between [" + min + ", " + max + "]",
    legend: { position: "none" },
    histogram: { bucketSize: 1 }
  });
}

<script src="https://www.gstatic.com/charts/loader.js"></script>

<input type="number" id="rand-min" value="0" min="0" max="10">
<input type="number" id="rand-max" value="9" min="0" max="10">
<input type="button" id="draw-chart" value="Apply">

<div id="chart-1" style="height: 500px">Generating chart...</div>

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:

• Entropia: jak w Shannon Entropia
• Rozkład: rozkład statystyczny (Poissona, normalny itp.)
• Typ: jakie jest źródło liczb (algorytm, zdarzenie naturalne, kombinacja itp.) I zastosowany algorytm.
• Wydajność: szybkość lub złożoność wykonania.
• Wzory: okresowość, sekwencje, przebiegi itp.
• i prawdopodobnie więcej ...

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.

Ł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.

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:

• http://www.random.org/

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.

Odpowiedź brzmi: to zależy, mam nadzieję, że rand () * rand () będzie bardziej losowy niż rand (), ale jako:

• obie odpowiedzi zależą od wielkości bitu twojej wartości
• że w większości przypadków generujesz w zależności od pseudolosowego algorytmu (który jest w większości generatorem liczb, który zależy od zegara komputera i nie jest zbyt losowy).
• uczyń kod bardziej czytelnym (i nie wywołuj losowego boga voodoo z tego rodzaju mantrą).

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().