Randomness

Randomness is veel te belangrijk om aan het toeval over te laten. ;-)

Randomness genereren op een computer, hetgeen per definitie een zeer voorspelbaar en deterministisch systeem is, is zeer moeilijk. Gelukkig zijn er goede RNG's en PRNG's te vinden, maar meestal zijn het de developers van software die ervoor zorgen dat het uiteindelijke resultaat toch niet meer "random" is, of dat er gewoon een loopje genomen wordt met de logica.

Bijvoorbeeld:

De rand() functie in C.
Deze genereert een Random nummer tussen 0 en RAND_MAX waarde welke gedefiniëerd wordt in de stdlib.h library.

stdlib.h:

#define RAND_MAX 32767 

Dit kan natuurlijk verschillen van library tot library, maar hier is dit dus in weze 15 bits aan randomness. (0 - 32767)

Een random functie die "slechts" 15 bits randomness genereert, kan/mag je NIET gebruiken om meer randomness te maken, want dat gaat niet.
Het is cryptografisch een slecht idee om deze functie te gebruiken om bijvoorbeeld een key/wachtwoord van 32 bits te creëren. Je hebt dan wel een 32-bit key, maar deze heeft slechts 15-bit randomness.
Helaas is dit een veel gemaakte fout.

Nog een veel voorkomende fout is dat vaak de modulo functie gebruikt wordt om het resultaat van de random functie naar een bepaalde groteorde te schalen.
Dit hoeft niet noodzakelijk verkeerd te zijn, maar kan in bepaalde gevallen ervoor zorgen dat de uitkomst niet meer random is.

Bijvoorbeeld:

X = rand()%5;

Dit genereert dus een random nummer tussen 0 en 4 inclusief.
FOUT! Niet random!

Waarom niet?
Als we ervan uitgaan dat RAND_MAX nog steeds 32767 is, dan kan je vaststellen dat dat niet deelbaar is door 5.
Tot en met 32765 is alles OK, maar 32766%5 is 1, en 32767 is 2, m.a.w. statistisch gezien gaat X = 1 en X = 2 iets meer voorkomen dan de rest.
Het uiteindelijjke resultaat is dus niet meer random, omdat random namelijk wil zeggen dat iedere mogelijke uitkomst exact evenveel keer kan voorkomen.

Een oplossing is om eerst te kijken of rand() een waarde teruggeeft die groter is dan 32765 (in dit specifieke geval), en indien dit zo is, deze waarde negeren en opnieuw de rand() functie aanroepen.

Als je i.p.v. 5  een groter getal gebruikt, zal je zien dat er veel meer waardes zijn die vaker zullen voorkomen dan de rest.
Het bovenstaande samen met  een rand() functie die een kleinere maximale waarde teruggeeft, zorgt ervoor dat de kansen alleen maar groter worden voor een voorkeursgetallen.

En dan hebben wel het nog niet gehad over het randomizen of shufflen van een lijst.
Ik snap niet wat er moeilijk aan is, want "The Art of Computer Programming" van Donald Knuth is toch al enkele decenia oud, en daarin staat alles netjes uitgelegd.
Blijkbaar worden de mensen hoe langer hoe dommer of zo. ;-)

BTW: Om een lijst te randomizen gebruik je een Fisher-Yates shuffle.