Toevalsgenerator

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

Een toevalsgetal is een aselect getal getal tussen twee grenzen, waarbij ieder getal tussen die grenzen een evengrote 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[bewerken]

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. Voor 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[bewerken]

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.

Hoge hoed[bewerken]

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.

Dobbelsteen[bewerken]

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[bewerken]

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 kwantum effecten, zoals witte ruis, waarvan de theorie zegt dat deze volslagen aselect (at random) zijn. Een sensor meet deze effecten en genereert hiermee aselecte (random) getallen.

Algoritmen[bewerken]

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[bewerken]

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[bewerken]

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[bewerken]

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[bewerken]

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

  • Tippet-table (1927), met 41600 cijfers uit statistieken
  • Fisher-Yates (1938): 15000 cijfers verkregen als 15e-19e decimalen uit de "Logarithmica Brittanica" van Thompson
  • Kendall-Babington Smith (1939): 100.000 cijfers, geproduceerd door een machine
  • Rand Corporation (1955): 1.000.000 cijfers, geproduceerd door een elektronisch apparaat.

Toepassingen[bewerken]

Toevalsgeneratoren worden gebruikt in programma's die steeds anders moeten reageren, zoals simulatiemodelen, 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.