Dobra i prosta miara losowości

Question

Jaki jest najlepszy algorytm do wykonania długiej sekwencji liczb całkowitych (powiedzmy 100 000 z nich) i zwrócony pomiar losowości sekwencji?

Funkcja powinna zwracać pojedynczy wynik, powiedzmy 0, jeśli sekwencja nie jest cała losowa, do, powiedz 1, jeśli idealnie losowa. Może dać coś pośredniego, jeśli sekwencja jest nieco przypadkowa, np. 0,95 może być dość przypadkową sekwencją, podczas gdy 0,50 może mieć pewne nielosowe części i niektóre losowe części.

Gdybym przekazał pierwsze 100 000 cyfr Pi funkcji, powinien podać liczbę bardzo bliską 1. Jeśli przekazałem sekwencję 1, 2, ... 100 000, powinna ona zwrócić 0.

W ten sposób mogę z łatwością wziąć 30 sekwencji liczb, określić, jak losowe są każde z nich, i zwrócić informacje o ich względnej losowości.

Czy istnieje takie zwierzę?

Answer 1

To można zrobić w ten sposób:

CAcert Research Lab robi a Random Number Generator Analysis.

Their results page ocenia każdą sekwencję losową za pomocą 7 testów (Entropia, Urodziny, Szeregi Macierzy, Szkielety Matrycy 6x8, Minimalna Odległość, Losowe Kule i Squeeze). Każdy wynik testu jest następnie oznaczany kolorem jako jeden z "Brak problemów", "Potencjalnie deterministyczny" i "Nie przypadek".

Można więc zapisać funkcję, która przyjmuje losową sekwencję i wykonuje 7 testów. Jeśli którykolwiek z 7 testów ma wartość "Nie jest losowa", to funkcja zwraca wartość 0. Jeśli wszystkie z 7 testów to "Brak problemów", to zwraca wartość 1. W przeciwnym razie może zwrócić pewną liczbę w zależności od tego, jak wiele testów pojawia się jako "Potencjalnie deterministyczne".

Jedyne czego brakuje w tym rozwiązaniu to kod dla 7 testów.

Answer 2

Zgodnie z Knuth, upewnij się, że testujesz bity niskiego rzędu pod kątem losowości, ponieważ wiele algorytmów wykazuje straszliwą losowość w najniższych bitach.

Answer 3

Twoje pytanie odpowiada. "Gdybym przekazał pierwsze 100 000 cyfr Pi funkcji, powinien podać cyfrę bardzo zbliżoną do 1", z tym że cyfry Pi nie są liczbami losowymi, więc jeśli twój algorytm nie rozpoznaje bardzo specyficznej sekwencji jako nie losowo to nie jest zbyt dobre.

Problem polega na tym, że istnieje wiele rodzajów nielosowości: - np. "121,351,991,7898651,12398469018461" lub "33,27,99,30003,3,231" lub nawet "14297141600464,14344872783104,819534228736,3490442496" zdecydowanie nie są przypadkowe.

Myślę, że należy zidentyfikować aspekty losowości, które są dla Ciebie ważne - dystrybucja, dystrybucja cyfr, brak typowych czynników, spodziewana liczba liczb pierwszych, fibonacci i inne "specjalne" cyfry itp.

PS. Szybki i brudny (i bardzo efektywny) test przypadkowości jest taki, że plik kończy się mniej więcej w tym samym rozmiarze po tym, jak go zgasisz.

Answer 4

To, czego szukasz, nie istnieje, a przynajmniej nie tak, jak opisujesz to teraz.

Podstawową kwestią jest to, że:
Jeśli jest losowa, to przejdzie testy losowości; ale rozmowa nie działa - nie ma testu, który mógłby zweryfikować przypadkowość.

Na przykład, można mieć bardzo silne korelacje między elementami odległymi od siebie i trzeba na ogół jednoznacznie to przetestować. Albo można mieć płaską dystrybucję, ale generowaną w bardzo nie-losowy sposób. Itd, itp.

Ostatecznie musisz zdecydować, jakie aspekty losowości są dla ciebie ważne, i przetestować je (jak opisuje James Anderson w swojej odpowiedzi). Jestem pewien, że jeśli myślisz o czymś, co nie jest oczywiste, jak przetestować, ludzie tutaj pomogą.

Btw, zwykle podchodzę do tego problemu z drugiej strony: Dostaję zestaw danych, które szukają wszystkiego, co mogę zobaczyć, aby był całkowicie losowy, ale muszę ustalić, czy jest gdzieś jakiś wzorzec. Bardzo nieoczywisty, w ogóle.

Answer 5

Jak zauważyli inni, nie można bezpośrednio obliczyć, jak losowa jest sekwencja, ale istnieje kilka testów statystycznych, które można wykorzystać do zwiększenia pewności, że sekwencja jest lub nie jest przypadkowa.

Standard de facto dla tego rodzaju testów, ale nie zwraca ani jednej wartości, ani nie jest prosty.

ENT - A Pseudorandom Number Sequence Test Program, jest prostszą alternatywą, która łączy 5 różnych testów. Strona wyjaśnia, w jaki sposób działa każdy z tych testów.

Jeśli naprawdę potrzebujesz tylko jednej wartości, możesz wybrać jeden z 5 testów ENT i użyć tego. Najprawdopodobniej najlepiej byłoby użyć Chi-Squared test, ale to może nie odpowiadać definicji prostej.

Należy pamiętać, że pojedynczy test nie jest tak dobry, jak przeprowadzenie kilku różnych testów w tej samej sekwencji. W zależności od tego, który test wybierzesz, powinno być wystarczająco dobre, aby oznaczyć podejrzane sekwencje jako nieprzypadkowe, ale może nie zawieść w przypadku sekwencji, które powierzchownie wydają się przypadkowe, ale faktycznie wykazują pewien wzór.

Answer 6

W wizji komputerowej podczas analizy tekstur pojawia się problem próbowania losowości tekstury, aby ją posegmentować. Jest to dokładnie to samo, co w przypadku pytania, ponieważ próbujesz określić losowość sekwencji bajtów/liczb całkowitych/zmiennoprzecinkowych. Najlepszą dyskusją jaką mogłem znaleźć na temat entropii obrazu jest http://www.physicsforums.com/showthread.php?t=274518.

Zasadniczo jest to statystyczna miara losowości dla sekwencji wartości.

Chciałbym również wypróbować autokorelację sekwencji ze sobą. W wyniku autokorelacji, jeśli nie ma pików innych niż pierwsza wartość, co oznacza, że ​​nie ma okresowości dla danych wejściowych.

Answer 7

Można spróbować skompresować sekwencję zip. Im lepiej Ci się uda, tym mniej przypadkowa jest kolejność.

Zatem heurystyczny losowość = długość kodu pocztowego/długość oryginalnej sekwencji

Answer 8

„Jak to jest losowa sekwencja?” to trudne pytanie, ponieważ zasadniczo interesuje cię, w jaki sposób wygenerowano sekwencję. Jak powiedzieli inni, jest całkowicie możliwe generowanie sekwencji, które pojawiają się losowo, ale nie pochodzą ze źródeł, które uznalibyśmy za przypadkowe (np. Cyfry pi).

Większość testów losowości stara się odpowiedzieć na nieco inne pytania, które brzmią: "Czy ta sekwencja jest anomalna w odniesieniu do danego modelu?".Jeśli jesteś modelem toczącym kość dziesiętną, to łatwo jest określić, jak prawdopodobne jest, że sekwencja jest generowana z tego modelu, a cyfry pi nie wyglądałyby anormalnie. Ale jeśli twój model brzmi "Czy ta sekwencja może być łatwo wygenerowana z algorytmu?" staje się znacznie trudniejsze.

Answer 9

Możesz traktować 100 000 wyników jako możliwe wyniki zmiennej losowej i obliczyć powiązaną z nią entropię. Da ci to miarę niepewności. (Poniższy obraz jest z wikipedii i można znaleźć więcej informacji na Entropy tam). Po prostu:

Trzeba tylko obliczyć częstotliwości każdego numeru w sekwencji. To da ci p (xi) (np. Jeśli 10 pojawi się 27 razy p (10) = 27/L, gdzie L to 100 000 dla twojej sprawy). To powinno ci dać miarę entropii.

Mimo że nie daje liczby od 0 do 1. Wciąż 0 będzie minimalną niepewnością. Jednak górna granica nie będzie 1. Musisz znormalizować wyjście, aby to osiągnąć.

Answer 10

@JohnFx "... matematycznie niemożliwe".

stany plakatu: wziąć długi ciąg liczb całkowitych ...

Tak więc, podobnie jak limity są wykorzystywane w rachunku, możemy przyjąć wartość jako wartość - badanie pokazuje nam Chaotics skończone granice mogą "same się włączyć", wytwarzając pola tensorów, które zapewniają iluzję absolutną (absolutną), i które mogą być uruchamiane tak długo, jak długo jest czas i energia. Ze względu na krzywiznę czasoprzestrzeni, nie ma doskonałości - stąd op "... powiedzmy 1, jeśli idealnie losowe." "jest mylące.

{zauważyć: obszerne uwagi na temat, które zostały dostarczone - części mnie}

Według twojej pozycji, biorąc pod uwagę dwa byte [] od kilku k, każdy losowanych niezależnie - op nie może uzyskać „pomiar jak losowa jest sekwencja "Artykuł na Wiki ma charakter informacyjny i sprawia, że ​​definitywne kroki dezintegrują materię, ale w fizyce kwantowej przewiduje się, że właściwości układu kwantowego zależą od pomiaru, w przeciwieństwie do fizyki klasycznej. kontekście, tj. czy przeprowadzane są inne pomiary systemowe.

zespół fizyków z Innsbruck, Austria, doprowadziła Christian Roos i Rainera Blatta, mają po raz pierwszy sprawdzonej w kompleksowy eksperymentu , że nie jest możliwe, aby wyjaśnić kwantowych zjawisk w nie- kontekstowe warunki: .

Źródło: Science Daily

Rozważmy nieprzypadkowe ruchy jaszczurki. Źródło bodźca, które inicjuje złożone ruchy w szopach lamparta, pod pierwotną, skorygowaną hiper-tezą, nigdy nie będzie znane. My, doświadczeni informatycy, cierpimy z powodu niewinnego wyzwania, jakie stawiają nowicjusze, wiedząc zbyt dobrze, że tam, w kontekście nie skażonego i nieskazitelnego umysłu, są klejnotami i kreatorami myślenia ukierunkowanego na rozwój.

Jeśli pole myślowe oryginalnej jaszczurki wytworzy pole tensorowe (traktuj ludzi, to jest pierwsza faza badań w fizyce sub-liniowej), wtedy możemy mieć "najlepszy algorytm do wykonania długiej sekwencji" cywilizacji, działającym z imprezy Toba przedstawienia przez Chaotic Inversion „Należy rozważyć kwestię, czy taka myśl pola wytwarzane przez jaszczurki, są rozpatrywane niezależnie, to straszne lub poznawalne.

” bezpośrednia obserwacja paradoksu Hardy'ego przez wspólny słaby pomiar z parą splątanych fotonów , "autor: Kazuhiro Yokota, Takashi Yamamoto, Masato Koashi i Nobuyuki Imoto z Graduate School of Engineering Nauki na Uniwersytecie w Osace i CREST fotoniczne Quantum Information Projekt w Kawaguchi Miasto

Źródło: Science Daily

(biorąc pod uwagę upiorny/poznawalną dychotomii)

Wiem z własnych eksperymentów, że bezpośrednia obserwacja osłabia absolutność odczuwalnych tensorów, odróżnienie myśli od odczuwalnych tensorów jest niemożliwe przy użyciu tylko jednej techniki skupiania, ponieważ wyczuwalny tensor nie jest oryginalną myślą. Podstawową konsekwencją quantaeusu jest to, że tylko słabe stany wyczuwalnych tensorów można w niezawodny sposób odróżnić od siebie, nie powodując zapaści w zjednoczony wyczuwalny tensor. Spróbuj tego kiedyś - popracuj nad głównym celem jakiejś pożądanej sytuacji, używając czystej myśli. Ponieważ idea nie ma czasu ani przestrzeni, jest zatem nieskończona. (nieskończoność), a zatem może osiągnąć "doskonałość" - tj. absolutność. Dla podpowiedzi, zacznij od pogody, ponieważ jest to najłatwiejsza rzecz do wpłynięcia (przynajmniej tak daleko, jak jest to obecnie znane), a następnie poruszaj się tak szybko, jak to tylko możliwe, aby robić sprzężenie ze stanu uśpienia do stanu przebudzenia z praktycznie żadna przerwa w sekwencyjnym łańcuchowaniu.

Istnieje nieunikniony blip tam, gdzie ciało się budzi, ale to tak, jak dzwoni dzwonek, mówiąc o tym, co prowadzi do ciekawego obszaru badań statystycznych do dostępności finansowania: Ile myśli można utrzymać synchronicznie? Uważam, że dualność jest praktycznym limitem roboczym, w trójjedności albo przerywa następną myśl, albo nie trwa długo.

Być może dzieło Yokota et al mogłoby ujawnić źródło fałszywego ruchu sieciowego ... może to duchy.