sciencetalk

Ik had onlangs een idee voor een random number generator. Nu vraag ik me af in welke mate de gegenereerde nummers echt willekeurig zijn. Als er sprake is van echte willekeurigheid lijkt dit interessant, anders niet.

Hieronder drie voorbeeldjes van 100 nummers tussen 0 en 63 (incl.):

Code: Selecteer alles

45 40 58 17 8 41 56 8 43 4 43 29 44 44 58 46 30 58 53 20 53 12 42 40 8 47 40 30 20 28 41 55 23 19 19 27 9 53 20 42 51 7 10 34 13 54 47 21 21 16 55 42 16 35 50 0 25 25 43 10 51 60 61 22 47 43 49 60 59 56 30 2 59 24 21 27 23 46 61 26 6 48 30 50 38 43 51 11 38 47 10 52 25 40 50 44 19 42 38 20

Code: Selecteer alles

49 8 32 59 17 9 41 20 23 21 21 61 23 43 29 13 30 5 38 44 26 11 63 55 61 30 22 61 54 6 54 5 53 53 26 58 42 62 42 57 42 3 41 36 23 37 29 23 22 43 46 12 20 8 33 21 9 13 59 45 29 7 22 42 37 10 40 46 45 15 22 20 38 47 37 58 54 61 38 57 39 55 30 56 42 48 63 50 57 36 54 48 49 7 54 50 59 42 36 29

Code: Selecteer alles

44 33 4 10 42 58 48 42 38 48 33 50 63 38 53 5 53 57 52 17 3 40 30 42 59 34 57 43 10 40 38 12 43 43 6 41 19 27 19 29 36 52 58 17 22 34 47 53 15 44 43 41 15 53 5 21 21 48 35 35 57 43 13 30 42 41 10 27 54 31 12 21 33 45 9 59 5 22 39 20 50 63 44 61 47 37 41 40 14 47 3 4 5 30 19 26 41 44 31 54

Principe kort uitgelegd: twee threads checken constant een boolean variabele, wanneer die op true wordt gezet, geeft één van de twee threads een waarde aan een getal en zet de boolean variabele weer op false. Zo geeft bijvoorbeeld de ene thread waarde 1 en de andere thread waarde 0. Op die manier genereer je een rij van nullen en eenen die je decimaal kan voorstellen.

Code in Java:

Spoiler: [+]

Code: Selecteer alles

public class RandomNumber {

static boolean assign=false;
	static boolean kill=false;
	static int number=2;
	static int decNumber=0;
	static int binairySize=6;
	static int[] binairyList=new int[binairySize];

static Thread t0=new Thread(){

public void run(){

while(!kill){

if(assign){

assign=false;

number=0;

try {sleep(1);} catch (InterruptedException e) {}

}

}

}
	};

static Thread t1=new Thread(){

public void run(){

while(!kill){

if(assign){

assign=false;

number=1;

try {sleep(1);} catch (InterruptedException e) {}

}

}

}
	};

static void generateNumber(int amount){

for(int a=0;a<amount;a++){

//genereer nummer

for(int i=0;i<binairySize;i++){

assign=true;

try {Thread.sleep(10);} catch (InterruptedException e) {}

binairyList[i]=number;

}

//print decimale vorm

decNumber=0;

for(int j=0;j<binairySize;j++){

decNumber+=binairyList[j]*(int)Math.pow(2, binairySize-j-1);

}

System.out.print(decNumber+" ");

}
	}

public static void main(String[] args) {

//start de twee threads

t0.start();

t1.start();

try {Thread.sleep(10);} catch (InterruptedException e) {}

//genereer en print 100 nummers

generateNumber(100);

//stop de twee threads

kill=true;
	}

}

Hoe test ik het best op willekeurigheid? Zijn er manieren te voorspellen welke thread (en dus processor) het getal uiteindelijk een waarde geeft?

Wat is de bron van je randomness?

Gebruik je nou de executietijd als basis daarvoor of begrijp ik niet helemaal wat je doet?

ik heb dit wel eens gedaan door bijvoorbeeld een random generator, getallen te laten produceren tussen bijvoorbeeld 0 en 100,
gedurende enkele uren of dagen, en van deze getallen te plotten in een grafiek hoe vaak ze voorkomen tijdens de meting.

Wat ik vaak kreeg was een soort ruis grafiek, met vrijwel geen uitschieters, of in ieder geval weinig verschil tussen
de meest voorkomende getal en de minst voorkomende waarde gedurende de meting.

vond het wel grappig om het te zien ontstaan, bij een slechte random generator kreeg je interessante uitschieters.

Dat geeft te denken over wat je denkt dat random is, en wat daadwerkelijk random is. Als je een miljoen keer kop of munt gooit is de kans aanzienlijk dat er een sequentie van 20 keer het een of het ander achter elkaar in voor komt.

Je hebt bijvoorbeeld (hardware) pseudorandom generators die netjes een sequentie doorlopen die alle statussen aandoet (behalve alle bits 0), opgebouwd uit schuifregisters en XOR gates. Als je een 16-bits exemplaar maakt lijkt het de eerste 65535 keer volledig random te zijn, maar daarna begint de exacte sequentie opnieuw.

Overigens is de frequentie van nummers plotten een heel slechte methode om randomness te meten. Als ik een stukje code schrijft met outputs die oplopen van 1,2,3...98,99,100,1,2,3,... dan plotten die perfect vlak in de methode die jij gebruikt.

Maar wat is dan de definitie van perfect random...??

als alle random getallen evenveel random voorkomen, perfecte chaos dus, er mag
dan geen enkele vorm van clustering voorkomen...of herkenbare vorm in voor komen

volgens mij is dan perfect random een soort ruis..

ik mat dat door alle getallen te noteren die voorkwamen en hoe vaak een zelfde getal langs kwam.
dan zou je het met een oneindige reeks moeten doen , dan mag een getal nooit twee keer voorkomen.

Wil je het echt random hebben, dan moet je een bron hebben die echt random is. Een vriend van mij postuleerde ooit het idee dat je voltages van de voeding kan uitlezen als basis voor een RNG. Er zal altijd witte ruis op de lijnen zitten en die is inherent random.

Electrische ruis kan inderdaad een bron zijn, al moet je oppassen dat er geen patroon in zit.

In bijvoorbeeld Intel processors zit een hardware random generator. Heel veel entropie komt daar niet uit, maar genoeg om wat cryptografisch werk te doen (al zijn er mensen die eraan twijfelen).

Er zijn heel veel manieren om randomness te testen, en het hangt er vaak ook vanaf waar je het voor wil gebruiken. Dit is een vakgebied op zich in de wiskunde. Begin bijvoorbeeld eens op Wikipedia bij Randomness tests of Statistical randomness, en er zal wellicht een wereld voor je open gaan. Of je die wereld ook daadwerkelijk in wil gaan, is weer een ander verhaal...

Er zijn inderdaad specifieke tests, maar ook een vrij eenvoudige waarmee je geen randomness kunt bewijzen, maar wel vrij zeker kunt vinden dat iets niet random is:

Schrijf de random bytes naar een bestand. Als je op die manier een aantal MB's maakt kun je proberen het bestand te comprimeren (bijvoorbeeld met 7 zip, maximum compression). Daadwerkelijke random data vast niet te comprimeren (minder dan 1% in de praktijk), niet-random data comprimeert meestal wel. Uiteraard zijn er uitzonderingen op die test, zoals reeds gecomprimeerde bestanden en dergelijke.

Benm schreef:Wat is de bron van je randomness?

Gebruik je nou de executietijd als basis daarvoor of begrijp ik niet helemaal wat je doet?

Uiteindelijk komt het daar op neer. Twee threads werken afzonderlijk van elkaar, kleine variaties in executietijd zorgen ervoor dat je niet kunt voorspellen welke thread de number variabele (zie code uit openingsbericht) een waarde geeft. Dat is althans de opzet.

WillemB schreef:ik heb dit wel eens gedaan door bijvoorbeeld een random generator, getallen te laten produceren tussen bijvoorbeeld 0 en 100,

gedurende enkele uren of dagen, en van deze getallen te plotten in een grafiek hoe vaak ze voorkomen tijdens de meting.

Zoals Benm aangeeft kan dit niet als bewijs voor randomness tellen. Ik heb dit nu wel gedaan omdat het wel als tegenbewijs kan dienen. Hieronder de resultaten, 64000 getallen van 0 t.e.m. 63:

Spoiler: [+]: 0:1237

1:1177

2:989

3:926

4:1123

5:1030

6:970

7:881

8:1015

9:1041

10:910

11:995

12:874

13:986

14:911

15:952

16:1205

17:1104

18:1079

19:950

20:1073

21:973

22:1026

23:973

24:920

25:954

26:1070

27:1036

28:847

29:894

30:995

31:1040

32:1107

33:1035

34:889

35:829

36:981

37:997

38:1033

39:943

40:966

41:991

42:1029

43:1038

44:955

45:977

46:1071

47:1144

48:987

49:887

50:896

51:881

52:978

53:937

54:1049

55:970

56:886

57:977

58:1041

59:1132

60:925

61:981

62:1153

63:1179

Ziet er dus niet zo goed uit, ik ga eens zoeken waar ik de code kan verbeteren en de test herhalen. Als ik dan betere resultaten verkrijg probeer ik het comprimeren zoals Benm voorstelt. Enkele MB's genereren zal wel enkele uren duren.

Hoe bepaal je eigenlijk of het 'beter' is? Die verdeling ziet er prima uit, maar zoals gesteld is dat geen bewijs van randomness.

Of drift tussen twee oscillators ECHT random resultaten geeft is lastig te zeggen, het is geen geheel onvoorspelbaar process. Ik heb het wel eens geimplementeerd gezien in bijvoorbeeld een arduino waar de watchdog timer (op de interne RC clock) wordt vergeleken met de hoofdklok (op een kristal).

Hoeveel bits dit precies oplevert is niet echt bekend, maar het is genoeg om de pseudorandom te seeden als je geen enkele andere bron van entropie hebt. Als je bijv een random getal wilt maken als iemand op een knop drukt kun je gebruik maken van de tijd voordat er op de knop gedrukt werd, hoe lang die druk aanhoudt, contact bounce etc - genoeg om het praktisch on-repeteerbaar te maken.

Benm schreef: Hoe bepaal je eigenlijk of het 'beter' is? Die verdeling ziet er prima uit, maar zoals gesteld is dat geen bewijs van randomness.

Ik zou minder grote schommelingen verwachten. 0 komt bvb. 1237 keer voor, toch wel een groot verschil met de verwachtte 1000. Heb de test nog eens herhaald:

Spoiler: [+]: 0:1194
1:1047
2:1079
3:1015
4:990
5:898
6:904
7:903
8:1001
9:1016
10:946
11:986
12:896
13:966
14:923
15:1061
16:1040
17:897
18:1030
19:911
20:995
21:927
22:990
23:1042
24:992
25:999
26:962
27:1078
28:878
29:1066
30:954
31:1223
32:1006
33:910
34:935
35:902
36:952
37:959
38:860
39:950
40:995
41:910
42:895
43:1008
44:947
45:1130
46:979
47:1220
48:955
49:853
50:975
51:970
52:1019
53:1079
54:1024
55:1183
56:941
57:853
58:978
59:1103
60:1001
61:1236
62:1112
63:1351

63 komt hier 1351 keer voor. Lijkt me wat veel voor toeval of niet?

Tja.. lastig met random is dat uitschieters erbij horen. Ik heb een plaatje gemaakt met de (absolute) afwijking van 1000 in jouw serie. Die lijkt een beetje skewed te zijn, maar de dataset is klein. Probeer het eens met bijv getallen 0-1000 en dat een miljoen keer (als het kan). Wellicht trekt het dan een beetje recht.

Dit wil overigens niet zeggen dat het niet behoorlijk random is, normaliter haal je zoiets nog door een bitshifter heen om de verdeling netjes te krijgen.

Dat alle getallen evenveel voorkomen is niet voldoende voor (uniform) random. Zoals het voorbeeld 1, 2, 3, ..., 98, 99, 100, 1, 2, etc. aantoont.

Ik bedoel, misschien heb je wel een generator waarin het getal 34 opvallend vaak na het getal 22 komt. Wie weet.

Alle N rijtjes van lengte 1 moeten frequentie 1/N hebben.

Alle N^2 rijtjes van lengte 2 moeten frequentie 1/N^2 hebben.

Alle N^3 rijtjes van lengte 3 moeten frequentie 1/N^3 hebben.
Etc. Oftewel:

Alle N^m rijtjes van lengte m moeten frequentie 1/N^m hebben.

Volgens mij is het voldoende voorwaarde voor uniform random als dit geldt voor alle m.

Dit kun je pas goed testen als je hele grote hoeveelheden getallen produceert. Met 64 getallen zijn er 262.144 mogelijke rijtjes van lengte 3. Je zou een miljoen getallen kunnen genereren en kijken of de rijtjes van lengte 3 een beetje uniform verdeeld zijn.

Verder, om te zien of je steekproef van 64.000 getallen duidt op uniforme willekeurigheid, zou je de frequenties moeten vergelijken met de frequenties van een uniforme rij. Daarmee bedoel ik, je weet dat de frequenties ongeveer 1.000 moeten zijn. Maar hoe ongeveer? Is 1.010 normaal? Is 1.100 normaal? Is 1.400 normaal?

Het aantal keer dat je een zeker getal trekt, volgt een binomiale verdeling met 64.000 trekkingen en p = 1/64. Wat is de standaarddeviatie van die kansverdeling? En wat is de standaarddeviatie van jouw 64 frequenties?

Erik Leppen schreef:
Ik bedoel, misschien heb je wel een generator waarin het getal 34 opvallend vaak na het getal 22 komt. Wie weet.

Dat is een eigenschap van pseudorandom generators. Zoiets produceert een op het oog random reeks getallen, maar die is altijd in dezelfde volgorde. De lengte van die reeks varieert naargelang constructie, 2^16, 2^24 of zelfs 2^32 zijn best praktische waardes. Maar telkens zal, bijvoorbeeld, na 18381 een reeks als 121, 43498, 55173.. volgen.

De onvoorspelbaarheid wordt vergroot door daadwerkelijk random een beginpunt te kiezen. Hiervoor heb je eenmalig 16 a 32 bits random nodig, in plaats van zoveel entropie voor ieder getal.

sciencetalk

Pseudorandom of niet?

Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?

Re: Pseudorandom of niet?