Algorytm działania generatora liczb losowych. Generatory liczb losowych. Liniowa metoda kongruencji

Liczby losowe to prosty element kryptografii, o którym najmniej się mówi, a jest tak samo ważny jak pozostałe. Prawie wszystkie systemy bezpieczeństwa komputerowego korzystające z kryptografii wymagają liczb losowych – kluczy, unikalnych numerów w protokołach itp. – a bezpieczeństwo takich systemów często zależy od losowości ich losowe liczby. Jeśli generator liczb losowych będzie zawodny, cały system ulegnie awarii.

W zależności od tego, z kim rozmawiasz, generowanie liczb losowych wydaje się trywialne lub niemożliwe. Teoretycznie jest to niemożliwe. John von Neumann, ojciec informatyki, powiedział: „Każdy, kto wierzy, że istnieją arytmetyczne metody uzyskiwania losowych cyfr, z pewnością grzeszy”. Miał na myśli to, że nie da się wrzucić czegoś przypadkowego W każdym sensie słowa są wytworem tak deterministycznej bestii jak komputer. To prawda, ale na szczęście jest kilka rzeczy, które możemy zrobić. Od generatora liczb losowych oczekujemy nie tego, że liczby są naprawdę losowe, ale tego, że nie można ich przewidzieć ani odtworzyć. Jeśli spełnimy te dwa warunki, możemy osiągnąć bezpieczeństwo.

Z drugiej strony, jeśli naruszymy te dwa warunki, nie ma bezpieczeństwa. W 1994 roku w kasynie w Montrealu zainstalowano komputerowy generator liczb losowych dla loterii. Jeden uważny gracz, który spędził dużo czasu w kasynie, zauważył, że zwycięskie liczby były codziennie takie same. Udało mu się trafić trzy jackpoty z rzędu i otrzymał 600 000 dolarów. (Po załamaniu rąk, zgrzytaniu zębami i zbadaniu wszystkiego kasyno wypłaciło wygraną.)

Istnieje kilka szerokich klas generatorów liczb losowych. Część z nich opiera się na procesach fizycznych, które można uznać za dość losowe. Agencja Bezpieczeństwa Narodowego lubi wykorzystywać szum elektryczny wytwarzany przez diody w swoim sprzęcie do tworzenia liczb losowych. Inne możliwości to liczniki Geigera lub odbiorniki zakłóceń radiowych. Korzysta z jednego systemu w Internecie aparat cyfrowy, wycelowany w kilka stroboskopów. Inne systemy wykorzystują turbulencje powietrza w napędach lub taktowanie pakietów sieciowych.

Niektóre generatory liczb losowych śledzą losowe ruchy użytkownika. Program może poprosić użytkownika o wpisanie na klawiaturze dużego ciągu dowolnych znaków; może wykorzystać sekwencję znaków lub nawet czas pomiędzy naciśnięciami klawiszy, aby wygenerować liczby losowe. Inny program może z łatwością wymagać od użytkownika poruszania myszą w przód i w tył lub chrząkania do mikrofonu.

Niektóre generatory liczb losowych stosują wprowadzone informacje bez modyfikacji. W innych służy jako ziarno (liczba początkowa) dla matematycznych generatorów liczb losowych. Technika ta działa najlepiej, jeśli system wymaga większej liczby liczb losowych, niż podaje dane wejściowe.

Niezależnie od pochodzenia losowości, generator utworzy serię losowych bitów. Można je następnie wykorzystać jako klucze kryptograficzne i do wszystkiego, czego potrzebuje system.

Wszystkie zjawiska, które nam się przytrafiają, są dwojakiego rodzaju - przypadkowe i naturalne. Nie miałeś np. rachunków na magnetofon i zdecydowałeś się na zakup odtwarzacza – tj. działanie jest logiczne i oczekiwane. Ale idąc do sklepu, odkrywasz wymaganą kwotę, która losowo zmieniła plany. Działanie generatora liczb losowych całkowicie zależy od mechanizmu określonego w operatorze, dzięki czemu wszystkie wydawane liczby są w bieżącym zdarzeniu pseudolosowe. Operatory, które zwracają losowe liczby, odnoszą się do czasu, a mianowicie czasu systemowego. Te. Zarówno w świecie, jak i w programowaniu nic nie jest całkowicie absolutne.

funkcja Randa

W programowaniu w C wynaleziono wbudowane operatory, które pozwalają uzyskać losowe wartości, które dają nam wymagane wyniki. I tak, aby utworzyć liczbę losową, użyj funkcja Randa, Który operatora Rand służy do uzyskiwania liczb losowych, które zwracają zakres od 0 do określonej stałej. Co więcej, stała ta jest zadeklarowana w dyrektywie systemowej „stdlib.h”, na której opiera się ta funkcja Rand. Składnia tej funkcji jest prosta: int m= rand(); te. zwracana jest liczba całkowita. Po przetestowaniu operatora w praktyce przekonasz się, że liczby pojawiające się przy uruchomieniu aplikacji są identyczne. Przeoczenie polega na tym, że operator Rand pracuje z tym samym czasem systemowym, który został zachowany podczas kompilacji. Ten generator liczb losowych jest powiązany z algorytmem zmiany czasu programu, ale wszystko działa niepoprawnie.

Teraz o srand i random

W przypadku tego problemu niezbędna była funkcja, która resetowałaby wbudowany czas do zera przy każdym wywołaniu operatora Rand, a twórcy oprogramowania tak zrobili funkcja srand. Akcja umożliwia funkcji Rand dostęp za każdym razem nie do zainstalowanego timera, ale do aktualnie wbudowanego timera, co otwiera możliwość poprawnej pracy generatora - generowania losowych wartości. Ostatnio w programowaniu w C++ udoskonalono mechanizm wydawania liczb losowych ze względu na pojawienie się mikrosekund. Dodatkowo rozszerzono zakres wartości, a wszystkie obecne innowacje zostały przekształcone w funkcję losową.

Każda osoba, niezależnie od stopnia hazardu i awanturnictwa, w taki czy inny sposób zetknęła się z taką koncepcją jak loteria. I tylko nieliczni zadali sobie pytanie, jak zachodzi losowa dystrybucja zwycięskie kombinacje liczby Jak wychodzi ten lub inny numer? Co sprawia, że ​​szala przechyla się w stronę zwycięzcy? Przyjrzyjmy się temu szczegółowo.

Każdy z nas przynajmniej raz w życiu spotkał się z takim zjawiskiem jak loteria. Ale niewiele osób myślało lub wyobrażało sobie dokładnie, jak działa ten system, czym jest generator liczb dla loterii i jaka jest jego zasada działania.

Pojęcie generatora liczb

Generator liczb losowych dla loterii to określone urządzenie lub dany program, który generuje liczby znajdujące się w wyznaczonym przedziale w losowej (a właściwie pseudolosowej) kolejności. Dla określonego rodzaju loterii, np. „Sportloto”, generowane są liczby z zakresu od 1 do 49.

Istnieją generatory numerów sprzętu i oprogramowania dla loterii. W każdym języku programowania istnieje funkcja RAND(), która odpowiada za tworzenie liczb pseudolosowych z zadanego zakresu.

Dlaczego jest napisane, że podawane wyniki są pseudolosowe i że generator liczb loteryjnych działa właśnie na tej zasadzie?

Funkcja LOS: koncepcja i sposób użycia

Funkcja LOS() to program lub na przykład urządzenie z deterministycznym algorytmem, które w tych samych określonych warunkach będzie stale pokazywać te same wyniki. Aby jednak warunki prawdziwej sekwencji losowej były spełnione, nie może być żadnej zależności warunki początkowe lub parametry. Dlatego należy unikać podobne przypadki, dodatkowo stosowana jest specjalna procedura RANDOMIZE, która usuwa przewidywalność warunków początkowych, czyniąc je losowymi.

Oprócz znanej nam już zasady generowania, stosuje się inny rodzaj generatora loterii. Przyjrzyjmy się temu poniżej.

Generator liczb 6 z 45

Generator liczb dla loterii 6 z 45 - program, który służy do uzyskania Szczęśliwe liczby. W tym przypadku istnieje możliwość ustawienia Dodatkowe opcje aby uzyskać lepsze rezultaty.

Możesz określić kryteria wyboru, na przykład:

• Ilość zwycięskie liczby, które należy uzyskać w wyniku końcowym.
• Należy wskazać zakres liczb, w jakim zostanie przeprowadzona selekcja.
• Liczby można sortować rosnąco lub malejąco.
• Wybierz rodzaj i metodę separacji.
• Wyeliminuj duplikaty lub pozostaw wybór nieposortowany.
• Skopiuj link do wyniku i umieść go na stronie w w sieciach społecznościowych w celu opublikowania wyniku.

Generator liczb: instrukcja obsługi

• Domyślnym wyjściem jest pięć liczb. Zmieniając ustawienia, możesz uzyskać aż 250 losowych zwycięskich kombinacji.
• Ustawiamy zakres, standard wynosi od 0 do 36, ale maksymalnie można określić aż do 9 999 999 999.
• Wybieramy sortowanie wymagane dla naszego rodzaju loterii: rosnące, malejące lub umieszczanie liczb w kolejności losowej.
• Kolejnym krokiem jest wskazanie w jaki sposób liczby będą od siebie oddzielane – przecinek, kropka, spacja, średnik.
• Pozbywamy się przypadkowych powtórzeń, które powstały w procesie pobierania próbek.

W ten sposób otrzymujemy wysokiej jakości wyselekcjonowane liczby, które mogą być tymi najszczęśliwszymi i zwycięskimi.

Należy zauważyć, że w idealnym przypadku krzywa gęstości rozkładu liczb losowych wyglądałaby tak, jak pokazano na ryc. 22.3. Oznacza to, że w idealnym przypadku każdy przedział obejmuje ten sam numer zwrotnica: N I = N/k , Gdzie N — Łączna zwrotnica, k liczba interwałów, I= 1, , k .

Należy pamiętać, że generowanie dowolnej liczby losowej składa się z dwóch etapów:

• generowanie znormalizowanej liczby losowej (to znaczy równomiernie rozłożonej od 0 do 1);
• znormalizowana konwersja liczb losowych R I do liczb losowych X I, które są dystrybuowane zgodnie z (arbitralnym) prawem dystrybucji wymaganym przez użytkownika lub w wymaganym odstępie czasu.

Generatory liczb losowych ze względu na sposób uzyskiwania liczb dzielą się na:

• fizyczny;
• tabelaryczny;
• algorytmiczne.

Fizyczne RNG

Przykładem fizycznego RNG może być: moneta („reszka” 1, „reszka” 0); kostka do gry; bęben ze strzałką podzielony na sektory z liczbami; sprzętowy generator szumu (HS), który wykorzystuje hałaśliwe urządzenie termiczne, na przykład tranzystor (ryc. 22.422.5).

Tabelaryczny RNG

Tabelaryczne RNG wykorzystują specjalnie opracowane tabele zawierające zweryfikowane nieskorelowane, czyli w żaden sposób od siebie zależne, liczby jako źródło liczb losowych. W tabeli Rysunek 22.1 pokazuje mały fragment takiej tabeli. Przemierzając tabelę od lewej do prawej, z góry na dół, można otrzymać liczby losowe o równomiernym rozkładzie od 0 do 1 z wymaganą liczbą miejsc po przecinku (w naszym przykładzie dla każdej liczby używamy trzech miejsc po przecinku). Ponieważ liczby w tabeli nie są od siebie zależne, tabelę można przeglądać różne sposoby, na przykład od góry do dołu lub od prawej do lewej, lub, powiedzmy, możesz wybrać liczby, które znajdują się na parzystych pozycjach.

Godność Ta metoda polega na tym, że generuje liczby naprawdę losowe, ponieważ tabela zawiera zweryfikowane, nieskorelowane liczby. Wady tej metody: do przechowywania duża ilość liczby wymagają dużo pamięci; Generowanie i sprawdzanie tego rodzaju tabel wiąże się z dużymi trudnościami, powtórzenia przy korzystaniu z tabeli nie gwarantują już losowości ciągu liczbowego, a co za tym idzie wiarygodności wyniku.

Istnieje tabela zawierająca 500 całkowicie losowo zweryfikowanych liczb (zaczerpnięta z książki I. G. Venetsky'ego, V. I. Venetskaya „Podstawowe pojęcia i wzory matematyczne i statystyczne w analizie ekonomicznej”).

Algorytmiczny RNG

Liczby generowane przez te RNG są zawsze pseudolosowe (lub quasi-losowe), to znaczy każda kolejna wygenerowana liczba zależy od poprzedniej:

R I + 1 = F(R I) .

Sekwencje złożone z takich liczb tworzą pętle, co oznacza, że ​​z konieczności istnieje cykl, który się powtarza nieskończona liczba raz. Powtarzające się cykle nazywane są okresami.

Zaletą tych RNG jest ich prędkość; generatory nie wymagają praktycznie żadnych zasobów pamięci i są kompaktowe. Wady: liczb nie można w pełni nazwać losowymi, ponieważ istnieje między nimi zależność, a także obecność kropek w sekwencji liczb quasi-losowych.

Rozważmy kilka algorytmicznych metod uzyskiwania RNG:

• metoda środkowych kwadratów;
• metoda produktów średnich;
• metoda mieszania;
• liniowa metoda kongruencji.

Metoda środkowego kwadratu

Jest jakaś czterocyfrowa liczba R 0. Liczba ta jest podnoszona do kwadratu i wprowadzana R 1. Następny od R 1 bierze środkową (cztery środkowe cyfry) nową liczbę losową i zapisuje ją R 0. Następnie procedurę powtarza się (patrz ryc. 22.6). Zauważ, że tak naprawdę jako liczbę losową nie musisz brać ghij, A 0.ghj z zerem i kropką dziesiętną dodaną po lewej stronie. Fakt ten jest odzwierciedlony jak na ryc. 22,6 i na kolejnych podobnych rysunkach.

Wady metody: 1) jeśli w jakiejś iteracji liczba R 0 staje się równe zero, wówczas generator ulega degeneracji, dlatego ważny jest prawidłowy wybór wartości początkowej R 0 ; 2) generator powtórzy sekwencję M N wkracza najlepszy scenariusz), Gdzie N cyfra numeru R 0 , M podstawa systemu liczbowego.

Na przykład na ryc. 22,6: jeśli liczba R 0 będzie reprezentowane w systemie liczb binarnych, a następnie sekwencja liczby pseudolosowe powtarza się w 2 4 = 16 krokach. Należy pamiętać, że powtórzenie sekwencji może nastąpić wcześniej, jeśli numer startowy zostanie wybrany źle.

Opisana powyżej metoda została zaproponowana przez Johna von Neumanna i sięga 1946 roku. Ponieważ metoda ta okazała się zawodna, szybko ją porzucono.

Metoda środkowego produktu

Numer R 0 pomnożone przez R 1, z uzyskanego wyniku R 2 środek jest wyodrębniony R 2 * (jest to kolejna liczba losowa) i pomnożona przez R 1. Wszystkie kolejne liczby losowe są obliczane według tego schematu (patrz ryc. 22.7).

Metoda mieszania

Metoda shuffle wykorzystuje operacje do cyklicznego przesuwania zawartości komórki w lewo i w prawo. Idea metody jest następująca. Niech komórka przechowuje numer początkowy R 0. Przesuwając cyklicznie zawartość komórki w lewo o 1/4 długości komórki otrzymujemy nową liczbę R 0 * . W ten sam sposób zmieniasz zawartość komórki R 0 w prawo o 1/4 długości komórki, otrzymujemy drugą liczbę R 0**. Suma liczb R 0* i R 0** daje nową liczbę losową R 1. Dalej R Wpisano 1 R 0 i cała sekwencja operacji jest powtarzana (patrz ryc. 22.8).

Należy pamiętać, że liczba wynikająca z sumowania R 0* i R 0**, może nie zmieścić się całkowicie w komórce R 1. W takim przypadku dodatkowe cyfry należy odrzucić z wynikowej liczby. Wyjaśnimy to na ryc. 22.8, gdzie wszystkie komórki są reprezentowane przez osiem cyfr binarnych. Pozwalać R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 , Następnie R 0 * + R 0 ** = 100110010 2 = 306 10 . Jak widać liczba 306 zajmuje 9 cyfr (w systemie liczb binarnych), a komórka R 1 (tak samo jak R 0) może zawierać maksymalnie 8 bitów. Dlatego przed wprowadzeniem wartości do R 1, należy usunąć jeden „dodatkowy”, skrajny lewy bit z liczby 306, w wyniku czego R 1 nie będzie już należeć do 306, ale do 00110010 2 = 50 10 . Należy również pamiętać, że w językach takich jak Pascal „przycinanie” dodatkowych bitów w przypadku przepełnienia komórki odbywa się automatycznie zgodnie z określonym typem zmiennej.

Liniowa metoda kongruencji

Liniowa metoda kongruencji jest jedną z najprostszych i najczęściej stosowanych obecnie procedur symulujących liczby losowe. Ta metoda wykorzystuje mod ( X, y) , która zwraca resztę z dzielenia pierwszego argumentu przez drugi. Każda kolejna liczba losowa jest obliczana na podstawie poprzedniej liczby losowej według następującego wzoru:

R I+ 1 = mod( k · R I + B, M) .

Nazywa się ciąg liczb losowych otrzymany za pomocą tego wzoru liniowa sekwencja zgodna. Wielu autorów nazywa liniową sekwencję przystającą kiedy B = 0 multiplikatywna metoda kongruencji, i kiedy B ≠ 0 — metoda mieszana kongruentna.

Aby uzyskać generator wysokiej jakości, należy wybrać odpowiednie współczynniki. Konieczne jest podanie numeru M był dość duży, gdyż okres nie może mieć więcej M elementy. Z drugiej strony dzielenie stosowane w tej metodzie jest operacją dość powolną, dlatego w przypadku komputera binarnego logicznym wyborem byłoby M = 2 N, ponieważ w tym przypadku znalezienie reszty dzielenia jest zredukowane w komputerze do binarnej operacji logicznej „AND”. Powszechnym jest również wybieranie największej liczby pierwszej M, mniej niż 2 N: w literaturze specjalistycznej udowodniono, że w tym przypadku cyfry niższego rzędu wynikowej liczby losowej R I+ 1 zachowują się tak samo losowo jak starsze, co pozytywnie wpływa na cały ciąg liczb losowych jako całość. Przykładowo jeden z Liczby Mersenne’a, równe 2 31 1, a zatem, M= 2 31 1 .

Jednym z wymagań dotyczących liniowych ciągów zgodnych jest możliwie najdłuższy okres. Długość okresu zależy od wartości M , k I B. Twierdzenie, które prezentujemy poniżej, pozwala nam określić, czy możliwe jest osiągnięcie okresu maksymalna długość dla konkretnych wartości M , k I B .

Twierdzenie. Liniowy ciąg zgodny określony liczbami M , k , B I R 0, ma okres długości M wtedy i tylko wtedy gdy:

• liczby B I M stosunkowo proste;
• k 1 razy P dla każdej liczby pierwszej P, który jest dzielnikiem M ;
• k 1 jest wielokrotnością 4, jeśli M wielokrotność 4.

Na koniec zakończmy kilkoma przykładami wykorzystania metody liniowej zgodności do generowania liczb losowych.

Ustalono, że ciąg liczb pseudolosowych wygenerowany na podstawie danych z przykładu 1 będzie się powtarzał M/4 cyfry. Numer Q ustalany jest arbitralnie przed rozpoczęciem obliczeń, należy jednak mieć na uwadze, że szereg sprawia w zasadzie wrażenie losowego k(i dlatego Q). Wynik można nieco poprawić, jeśli B dziwne i k= 1 + 4 · Q w tym przypadku wiersz będzie powtarzany co M liczby. Po długich poszukiwaniach k badacze ustalili wartości 69069 i 71365.

Generator liczb losowych korzystający z danych z Przykładu 2 wygeneruje losowe, niepowtarzalne liczby z okresem 7 milionów.

Multiplikatywną metodę generowania liczb pseudolosowych zaproponował D. H. Lehmer w 1949 roku.

Sprawdzanie jakości generatora

Od jakości RNG zależy jakość całego systemu i dokładność wyników. Dlatego losowa sekwencja generowana przez RNG musi spełniać szereg kryteriów.

Przeprowadzane kontrole są dwojakiego rodzaju:

• sprawdza równomierność dystrybucji;
• testy niezależności statystycznej.

Sprawdza równomierność rozkładu

1) RNG powinien dawać w przybliżeniu następujące wartości parametrów statystycznych charakterystycznych dla jednolitego prawa losowego:

2) Test częstotliwości

Test częstotliwości pozwala sprawdzić, ile liczb mieści się w przedziale (M R – σ R ; M R + σ R) , czyli (0,5 · 0,2887; 0,5 + 0,2887) lub ostatecznie (0,2113; 0,7887). Ponieważ 0,7887 · 0,2113 = 0,5774, wnioskujemy, że w dobrym RNG około 57,7% wszystkich wylosowanych liczb losowych powinno mieścić się w tym przedziale (patrz ryc. 22.9).

Należy również wziąć pod uwagę, że liczba liczb mieszczących się w przedziale (0; 0,5) powinna być w przybliżeniu równa liczbie liczb wchodzących w przedział (0,5; 1).

3) Test chi-kwadrat

Test chi-kwadrat (test χ 2) jest jednym z najbardziej znanych testów statystycznych; jest to główna metoda stosowana w połączeniu z innymi kryteriami. Test chi-kwadrat został zaproponowany w 1900 roku przez Karla Pearsona. Jego niezwykłe dzieło uważane jest za podstawę współczesnej statystyki matematycznej.

W naszym przypadku testowanie przy użyciu kryterium chi-kwadrat pozwoli nam dowiedzieć się, jak bardzo prawdziwy RNG już blisko Standard RNG, to znaczy, czy spełnia wymóg równomiernego rozkładu, czy nie.

Wykres częstotliwości odniesienie RNG pokazano na ryc. 22.10. Ponieważ prawo dystrybucji odniesienia RNG jest jednolite, wówczas (teoretyczne) prawdopodobieństwo P I wprowadzanie liczb I interwał (wszystkie te interwały k) jest równe P I = 1/k . I tak w każdym z k interwały będą uderzać gładki Przez P I · N liczby ( Nłączna liczba wygenerowanych numerów).

Prawdziwy RNG będzie generował liczby rozłożone (i niekoniecznie równomiernie!) w poprzek k interwały i każdy interwał będzie zawierał N I liczby (w sumie N 1 + N 2 + + N k = N ). Jak możemy określić, jak dobry jest testowany RNG i jak blisko jest do referencyjnego? Całkiem logiczne jest rozważenie kwadratów różnic między wynikową liczbą liczb N I i „odniesienie” P I · N . Dodajmy je i otrzymamy następujący wynik:

χ 2 eksp. = ( N 1 P 1 · N) 2 + (N 2 P 2 · N) 2 + + ( N k – P k · N) 2 .

Z tego wzoru wynika, że ​​im mniejsza jest różnica w każdym z wyrazów (a zatem i mniejsza wartośćχ 2 eksp. ), im silniejsze prawo rozkładu liczb losowych generowanych przez prawdziwy RNG, zwykle jest jednolite.

W poprzednim wyrażeniu każdemu z terminów przypisano tę samą wagę (równą 1), co w rzeczywistości może nie być prawdą; dlatego w przypadku statystyk chi-kwadrat konieczna jest normalizacja każdej z nich I wyraz, dzieląc go przez P I · N :

Na koniec napiszmy wynikowe wyrażenie bardziej zwięźle i uprośćmy je:

Otrzymaliśmy wartość testu chi-kwadrat dla eksperymentalny dane.

W tabeli Podano 22,2 teoretyczny wartości chi-kwadrat (χ 2 teoretyczne), gdzie ν = N 1 to liczba stopni swobody, P jest to poziom ufności określony przez użytkownika, który wskazuje, w jakim stopniu RNG powinien spełniać wymagania jednolitego rozkładu, lub P — jest prawdopodobieństwem, że wartość eksperymentalna χ 2 exp. będzie mniejsza niż tabelaryczna (teoretyczna) χ 2 teoretyczna. lub mu równy.

Uznane za akceptowalne P od 10% do 90%.

Jeśli χ 2 exp. znacznie więcej niż teoria χ 2. (to jest P jest duży), następnie generator nie zadowala wymóg równomiernego rozkładu, ponieważ obserwowane wartości N I za bardzo odchodzić od teorii P I · N i nie można ich uważać za przypadkowe. Innymi słowy, jest zainstalowany tak duży przedział ufności, że ograniczenia dotyczące liczb stają się bardzo luźne, a wymagania dotyczące liczb stają się słabe. W takim przypadku zostanie zaobserwowany bardzo duży błąd bezwzględny.

Nawet D. Knuth w swojej książce „The Art of Programming” zauważył, że posiadanie χ 2 exp. dla małych w ogóle też nie jest dobrze, chociaż na pierwszy rzut oka wydaje się to cudowne z punktu widzenia jednolitości. Rzeczywiście, weź serię liczb 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, 0,7, 0,8, 0,9, 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, są one idealne z punktu widzenia jednolitości i χ 2 eksp. będą praktycznie zerowe, ale jest mało prawdopodobne, że rozpoznasz je jako losowe.

Jeśli χ 2 exp. znacznie mniej niż teoria χ 2. (to jest P mały), następnie generator nie zadowala wymóg losowego rozkładu równomiernego, ponieważ obserwowane wartości N I zbyt blisko teorii P I · N i nie można ich uważać za przypadkowe.

Ale jeśli χ 2 exp. leży w pewnym przedziale pomiędzy dwiema wartościami teorii χ 2. , które odpowiadają np. P= 25% i P= 50%, to możemy założyć, że losowe wartości liczbowe generowane przez czujnik są całkowicie losowe.

Ponadto należy pamiętać, że wszystkie wartości P I · N musi być wystarczająco duża, na przykład większa niż 5 (znaleziona empirycznie). Dopiero wtedy (przy odpowiednio dużej próbie statystycznej) warunki eksperymentu można uznać za zadowalające.

Zatem procedura weryfikacji jest następująca.

Testy niezależności statystycznej

1) Sprawdzenie częstotliwości występowania liczb w ciągu

Spójrzmy na przykład. Liczba losowa 0,2463389991 składa się z cyfr 2463389991, a liczba 0,5467766618 składa się z cyfr 5467766618. Łącząc ciągi cyfr otrzymujemy: 24633899915467766618.

Oczywiste jest, że prawdopodobieństwo teoretyczne P I strata I Th cyfra (od 0 do 9) jest równa 0,1.

2) Sprawdzenie wyglądu serii identycznych liczb

Oznaczmy przez N L liczba serii identycznych cyfr w rzędzie długości L. Wszystko trzeba sprawdzić L od 1 do M, Gdzie M jest to liczba określona przez użytkownika: maksymalna występująca liczba identycznych cyfr w serii.

W przykładzie „24633899915467766618” znaleziono 2 serie o długości 2 (33 i 77), czyli N 2 = 2 i 2 serie o długości 3 (999 i 666), tj N 3 = 2 .

Prawdopodobieństwo wystąpienia szeregu długości L jest równe: P L= 9 10 L (teoretyczny). Oznacza to, że prawdopodobieństwo wystąpienia ciągu o długości jednego znaku jest równe: P 1 = 0,9 (teoretycznie). Prawdopodobieństwo pojawienia się ciągu dwóch znaków wynosi: P 2 = 0,09 (teoretyczne). Prawdopodobieństwo pojawienia się ciągu trzech znaków wynosi: P 3 = 0,009 (teoretycznie).

Na przykład prawdopodobieństwo wystąpienia serii o długości jednego znaku wynosi P L= 0,9, ponieważ na 10 może być tylko jeden symbol, a w sumie jest 9 symboli (zero się nie liczy). Natomiast prawdopodobieństwo, że dwa identyczne symbole „XX” pojawią się w rzędzie wynosi 0,1 · 0,1 · 9, czyli prawdopodobieństwo 0,1, że symbol „X” pojawi się na pierwszej pozycji, jest mnożone przez prawdopodobieństwo 0,1, że ten sam symbol pojawi się na drugiej pozycji „X” i zostanie pomnożony przez liczbę takich kombinacji 9.

Częstotliwość występowania szeregów oblicza się za pomocą wzoru chi-kwadrat, który omówiliśmy wcześniej, korzystając z wartości P L .

Uwaga: Generator można testować wielokrotnie, jednak testy nie są kompletne i nie gwarantują, że generator wygeneruje liczby losowe. Przykładowo generator generujący sekwencję 12345678912345 zostanie podczas testów uznany za idealny, co oczywiście nie jest do końca prawdą.

Podsumowując, zauważamy, że trzeci rozdział książki Donalda E. Knutha The Art of Programming (tom 2) jest w całości poświęcony badaniu liczb losowych. Studiuje różne metody generowanie liczb losowych, statystyczne testy losowości i konwersja liczb losowych o równomiernym rozkładzie na inne typy zmienne losowe. Prezentacji tego materiału poświęcono ponad dwieście stron.