Toevalsgenerator

Een toevalsgenerator is een instrument dat, of een methode die toevalsgetallen produceert.

Een toevalsgetal is een getal aselect gekozen tussen twee grenzen, zodanig dat ieder getal tussen die grenzen een even grote kans maakt te worden getrokken. Een toevalsgetal is dus onvoorspelbaar en in een lange reeks toevalsgetallen bestaat geen regelmaat of patroon en komt elk mogelijk getal ongeveer even vaak voor. Een toevalsgenerator produceert aselecte trekkingen uit een homogene kansverdeling, een kansverdeling op een eindig aantal mogelijkheden, met voor elke mogelijkheid dezelfde kans, waarbij de trekkingen onderling onafhankelijk zijn.

Het blijkt in de praktijk moeilijk een reeks toevalsgetallen te laten maken door een proefpersoon. Mensen hebben de neiging zich te laten leiden door ideeën over regelmaat en willekeur. Als gevolg daarvan worden reeksen als '2 2 2 2' en '1 2 3 4' al snel vermeden, terwijl in een reeks werkelijke toevalsgetallen ook dergelijke opeenvolgingen voorkomen. Een toevalsgenerator is een mechanisme of een algoritme dat zich niet door subjectieve overwegingen zoals willekeur laat leiden.

Pseudo-toevalsgetallen

Hoewel men voor sommige toepassingen, zoals kansspelen, echte toevalsgetallen wenst, zijn voor andere toepassingen zogenaamde pseudo-toevalsgetallen nodig. Dat zijn reeksen getallen die wat diverse criteria betreft niet van echte te onderscheiden zijn, maar desondanks toch reproduceerbaar. Er zijn verschillende methoden bedacht om zulke pseudo-toevalsgetallen te genereren. Vóór het computertijdperk waren dat voornamelijk lijsten met getallen. Met de komst van de computer werden algoritmen gebruikt om eenvoudig lange reeksen pseudo-toevalsgetallen te verkrijgen. De belangrijkste daarvan is Lehmer-congruentie. Een andere methode maakt gebruik van een maximum-lengtereeks, gegenereerd met behulp van een linear feedback shift register.

Mechanismen

Gebruikelijke mechanismen liggen aan de basis van de term "aselecte trekkingen". Ze kunnen samengevat worden met de term: hoge-hoedmethode. Andere zijn vergelijkbaar met de dobbelsteen. Beide leveren onder de juiste condities echte toevalsgetallen.

Soms wordt dat betwijfeld. Gooit men een dobbelsteen meerdere keren op precies dezelfde manier, waarbij alle externe invloeden, zoals de wind en trillingen van de aardbodem, worden uitgeschakeld, dan zou het resultaat in theorie altijd hetzelfde moeten zijn. In de praktijk zijn er echter altijd wel externe invloeden. Op kwantumniveau is dat anders, het gedrag van atomaire deeltjes is werkelijk onvoorspelbaar, en die onvoorspelbaarheid werkt in zeer geringe mate ook op het macroniveau door.

Hoge hoed

De hoge hoed met lootjes is het klassieke voorbeeld van een eerlijke lotingsmethode. Varianten zijn een doos, vaas of urn met knikkers of ballen. Een bekende vorm is de trekking van de lotto-getallen. Ook bij het afroepen van de getallen bij Bingo wordt deze methode gebruikt.

Dobbelsteen

Een goede mechanische toevalsgenerator is het gooien met een exact zuivere dobbelsteen: het resultaat van elke worp is onafhankelijk van de vorige worpen. Er is dus niets anders te voorspellen dan dat het nieuwe getal opnieuw zal liggen tussen de grenzen (1 en 6). Varianten zijn het werpen met een munt en het gebruik van dobbelstenen met andere aantallen zijden.

Vermeldenswaard is de manier om met een willekeurige munt, waarvan dus nog niet zeker is of hij zuiver is, een worp met een zuivere munt te simuleren, bedacht door Von Neumann en onafhankelijk van hem later ook door de Nederlandse hoogleraar statistiek Hemelrijk. Men werpt steeds twee keer met de munt. Is de uitkomst eerst kruis en dan munt dan spreken we van succes, komt eerst munt en dan kruis dan noemen we het resultaat een mislukking. Leveren de beide worpen dezelfde uitkomst, dus kruis en kruis of munt en munt, dan werpen we opnieuw. Het kan even duren voor men eruit is, maar de loting is, ongeacht de onzuiverheid van de munt, volstrekt eerlijk.

Toeval met behulp van effecten uit de natuurkunde

De genoemde methoden zijn lastig te gebruiken in apparaten en systemen. Daarom wordt er bij het werken met toevalsprocessen in wetenschappelijk onderzoek wel gebruikgemaakt van het verval van (licht)radioactief materiaal of kwantumeffecten, zoals witte ruis, waarvan de kwantummechanica zegt dat ze volslagen aselect zijn. Een sensor meet deze effecten en genereert hiermee aselecte getallen.

Algoritmen

Ook vóór de komst van de computer zocht men al naar algoritmen om (pseudo-)toevalsgetallen te berekenen. Zo kende men de "mid-square-" en de "mid-product-"methode, die uiteindelijk naar de congruentiemethode van Lehmer leidden.

Mid-square

Van een startgetal van twee cijfers berekent men het kwadraat en schrijft dit op met vier cijfers en kiest de middelste twee cijfers als nieuw toevalsgetal. Bijvoorbeeld:

25       25 × 25 = 0625

62       62 × 62 = 3844

84       84 × 84 = 7056

05       05 × 05 = 0025

02       02 × 02 = 0004

00

Zo'n reeks wordt al gauw cyclisch, of loopt op 0 uit, zodat men een verbetering zocht in de mid-productmethode.

Mid-product

In plaats van een kwadraat berekent men het product van twee getallen, neemt de middelste twee cijfers en schuift de getallen door.

25       13       25 × 13 = 0325

13       32       13 × 32 = 0416

32       41

Lehmer-congruentie

De tegenwoordig meest gebruikte en goed onderzochte methode is de congruentiemethode van Lehmer, kortweg Lehmer-congruentie genoemd. Bij deze methode wordt elk volgend getal verkregen door het vorige getal met een vast getal A te vermenigvuldigen en daarna modulo een getal M te reduceren. Door geschikte keuze van A en M kunnen zeer goede toevalsgeneratoren ontstaan.

$x_{n+1}=A\,x_{n}\,(\mathrm {mod} \,M)\,$

Lijsten

Lange tijd behielp men zich ook met lijsten met toevalsgetallen. Eenmaal geproduceerd en daarna gepubliceerd in tabellen. Bekende lijsten zijn:

• Tippet-table (1927), met 41 600 cijfers uit statistieken
• Fisher-Yates (1938): 15 000 cijfers verkregen als 15e-19e decimalen uit de Logarithmica Britannica' van Thompson
• Kendall-Babington Smith (1939): 100 000 cijfers, geproduceerd door een machine
• Rand Corporation (1955): 1000 000 cijfers, geproduceerd door een elektronisch apparaat.

Toepassingen

Toevalsgeneratoren worden gebruikt in programma's die steeds anders moeten reageren, zoals simulatiemodellen, simulatoren en spellen. Zonder de generator zou, bij gelijke acties van de menselijke speler, een spel steeds identiek verlopen, waarna de uitdaging snel verloren is. Ook bij simulatie van fysische processen zoals radioactief verval worden ze gebruikt. In de parapsychologie zijn toevalsgeneratoren gebruikt om te trachten telekinetische beïnvloeding aan te tonen.

Donald Knuth heeft in zijn werk The art of Computer Programming een heel goede beschouwing gewijd aan het maken van toevalsgenerators; een behartigenswaardige opmerking die hij aan het begin maakt is dat wie zelfs maar overweegt een dergelijke generator te programmeren zich al in 'een staat van zonde' bevindt.

Toevalsgeneratoren kunnen ook gebruikt worden bij procedurele generatie van content van computerspellen of grafische computerprogramma's. Zie ook de lijst van toevalsgeneratoren voor een overzicht.