Náhodná čísla a třída Random

Třída Random

Třída Random je tu s náma už od verze .NET frameworku 1.1., nicméně použitelná tak jak ji zhruba známe je od verze 2.0. Technicky se jedná o generátor pseudo-náhodných čísel. Algoritmus napsal prof. D. E. Knuth z Harvardu a je založen na principu lineárního kongruenčního generátoru. Ten tvoří náhodná čísla na základě vzorce s pomocí modulo a dalších zvolených konstant. Obecný předpis takového generátoru je:

x_i+1 = ax_i+c (mod m)

Algoritmus D. E. Knutha používá pro konstanty různá magická čísla. Jedním z nich, které můžeme v implementaci najít je například poměrové číslo označované jako Golden Ratio, česky "Zlatý řez". Algoritmem se nemá smysl dále zabývat, jelikož je důkladně popsán v příručce The Art of Computer Programming, Volume 2: Seminumerical Algorithms

Instance třídy

Třída Random má dva konstruktory. Obvykle vývojář použije ten bezparametrický, který implicitně použije hodnotu Environment.TickCount a předá ji jako hodnotu do druhého konstruktoru Random(int seed). Environment.TickCount vrací čas v milisekundách od spuštění systému. Pokud bychom si nechali v cyklu vypsat hodnotu této property, zjistíme, že cyklus je tak rychlý, že property bude vracet na konzoli často stejná čísla. A to dokonce s použitím uspání vlákna, např.:

for (int i = 0; i < 20; i++)
{
    Thread.Sleep(1);
    Console.WriteLine("{0}: {1}", i, Environment.TickCount);
}

To má za následek fakt, že pokud bychom měli potřebu generovat náhodná čísla bez udání seedu pomocí dvou generátorů, jako nevhodná implementace se jeví:

Random random1 = new Random();
Random random2 = new Random();

S vysokou pravděpodobností takto vytvoříme dva generátory, které mají stejný seed. Správné řešení je použití vlastního seedu, například s pomocí Guid.

Random random = new Random(Guid.NewGuid().GetHashCode());

Seed je defacto nějaký výchozí prvek, od kterého jsou náhodná čísla deterministicky generována. Jinými slovy, pokud vytvoříme instanci třídy Random a předáme jako seed například číslo 99, vždy se bude generovat stejná číselná řada (za předpokladu stejného intervalu při opakovaném volání metody Next(int, int)).

Pro zajímavost (a z logiky věci) - pokud bychom se stejným seed generovali čísla o vyšším rozsahu ale s minimálním rozdílem horní hodnoty, získali bychom dvě velmi podobné řady náhodných čísel. Např.:

Random random1 = new Random(99);
Random random2 = new Random(99);

for (int i = 0; i < 10; i++)
{
    Console.WriteLine("R1: {0}", random1.Next(1,500));
    Console.WriteLine("R2: {0}", random2.Next(1,501));

    Console.WriteLine();
}

Nakonec ještě poznamenám, že vložené číslo seed není konečné, právě toto číslo je dále dopočítáno s pomocí Golden Ratio.

Next(int, int)

Volání metody Next(int minValue, int maxValue) vrátí další náhodné číslo ve stanoveném rozsahu. Zajímavé je, že hodnota maxValue udává ve skutečnosti horní hranici o jednotku menší, tedy maxValue - 1.

Náhodné nebo ne?

Stále jsme se nedostali k tomu, zda jsou generované řady náhodné. Mohl bych napsat ano, stejně jako je to uvedeno v MSDN nebo v práci prof. D. E. Knutha ale pro zajímavost můžeme udělat pár testů. Aby byl test objektivní, je ideální pracovat s 1000 náhodnými čísly a vyzkoušet různé hodnoty pro seed. Tu práci jsem si již dal, proto jen demonstruji výsledky například na seed = 99 a pro interval <0;50>. Testy nebudu popisovat a opět jen odkážu na zdroje.

Kolmogorov-Smirnov test

Kritická hodnota pro test při hladině významnosti 0,05 pro 1000 prvků je 0,0430. Generovaná řada byla seskupena dle četností a testové kritérium D_n = 0,024. Protože testové kritérium nedosáhlo kritické hodnoty, nezamítáme nulovou hypotézu o shodě prvků a lze říct, že generovaná řada náhodných čísel splňuje podmínky pro statistickou náhodnost na hladině významnosti 0,05.

Na dalším obrázku je vidět rozložení odchylek pro všechny hodnoty v generovaném intervalu (jako absolutní číslo).

Pro zajímavost, podobně dopadly i testy pro další zvolené hodnoty pro seed.

					D  0.043
seed    5			Dn 0.025
seed    99			Dn 0.024
seed    256			Dn 0.021
seed    314			Dn 0.028
seed    1024		Dn 0.017
seed    102254		Dn 0.030
seed    256345		Dn 0.028
seed    256346		Dn 0.018
seed    256347		Dn 0.018
seed    999999		Dn 0.018

Chí-kvadrát test (shoda rovnoměrného rozd.)

Opět je nalezena kritická hodnota testu pro k-1 prvků (četnosti 0-50). D = 46,214 a dopočteno je testové kritérium D_n = 37,034. Opět testové kritérium nedosáhlo kritické hodnoty a můžeme tedy učinit stejný závěr jako v předchozím případě (stejná hladina významnosti). Pro zajímavost jen výsledky pro další seed hodnoty:

					D  37,034
seed	5			Dn 52,538
seed	99			Dn 37,034
seed	256			Dn 40,910
seed	314			Dn 56,720
seed	1024		Dn 44,378
seed	102254		Dn 50,192
seed	256345		Dn 48,254
seed	256346		Dn 53,558
seed	256347		Dn 48,050
seed	999999		Dn 46,214

Další testy

Vynechal jsem lokální testy, které by měly ještě potvrdit náhodnost v případě rozdělení generované řady na menší části. Udělal jsem ale nad celou řadu i testy bodů zvratu a znamének diferencí. Výsledky dopadly dle očekávání:

Test bodů zvratu
n = 1000
P = 644 (počet diferencí)
U = 1,96
Un = -1,6015
U > |Un| (potvrzena náhodnost)

Test znamének diferencí
n = 1000
C = 496 (počet bodů růstu)
U = 1,96
Un = -0,38321
U > |Un| (potvrzena náhodnost)

Pár hodů kostkou

Nakonec jsem se rozhodl ještě vyzkoušet, jak třída Random obstojí pro simulaci hodu kostkou. Kdybychom měli teoreticky 100% vyváženou kostku a učinili bychom dostatečné množství pokusů (konečné číslo blízké ∞), prakticky by počet hodů každého čísla měl být velmi blízko teoretické hodnotě pravděpodobnosti. Pravděpodobnost, že padne jakékoliv číslo na kostce v rámci jednoho hodu je samozřejmě 1/6 (cca 0,166666...).

Generované rozsahy čísel odpovídaly předpokladu. Diference minimální a maximální hodnoty se pohybovala mezi 0,022 a 0,028 pro různě zvolené seed. Průměrná odchylka od očekávané hodnoty byla v rozmezí 0,0052222 a 0,010889. To všechno při 1000 iteracích (náhodných pokusech).

Následně jsem test provedl na 1 milionu iterací se zajímavými výsledky. Diference min a max hodnoty byla menší než 0,0014 a průměrná odchylka se od očekávané hodnoty zmenšila na cca 0,00024 až 0,00039 pro různé seed hodnoty. Se zvyšováním počtu iterací se tedy průměrná odychylka zmenšuje. Na obrázku níže můžete vidět závislost lineárně se zvyšujícího počtu iterací a chování průměrné odchylky pro počet iterací od 1000 do 1 mil.

Když vybereme větší kroky v počtu iterací, je zpřesnění zřejmé:

iterations	avg d.
10			0,116666667
100			0,015
1000		0,005055556
10000		0,002883333
100000		0,001390556
1000000		0,000240611
10000000	8,18E-05
100000000	2,34E-05

Závěry a shrnutí

V článku jsem nastínil jakým způsobem funguje třída Random. Splňuje základní předpoklady statistické náhodnosti, což jsme pro zajímavost otestovali několika testy na zvolené hladině významnosti. Pokud chceme třídu Random použít, je potřeba hlídat si horní hodnotu v metodě Next(int, int), která ve skutečnosti odpovídá max-1 (což je jeden z mála code smell ve třídě). Pro generování náhodných řad doporučuji používat vlastní seed, buď vytvořený náhodně pomocí hashe z Guid.NewGuid() nebo s vlastní hodnotou.