Toevalsgenerator
Een toevalsgenerator is een methode om zgn. toevalsgetallen te produceren. Met toevalsgetal bedoelt men een willekeurig getal tussen twee grenzen, waarbij de term willekeurig niet alleen doelt op de onvoorspelbaarheid van het te produceren getal, maar ook op de eigenschap dat in een lange reeks van zulke getallen elk mogelijk getal ongeveer even vaak voorkomt en er verder ook geen systeem in de reeks te ontdekken valt. Een toevalsgenerator is de realisatie van 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 is tamelijk moeilijk een reeks toevalsgetallen te laten maken door een proefpersoon. Deze zal zich al snel laten leiden door een gevoel voor regelmaat, of juist door een drang naar perfectie. Als gevolg worden reeksen als '2 2 2 2' '1 2 3 4' al snel vermeden, terwijl deze ook kunnen komen. Daarom zoekt men een mechanisme of een algoritme, dat zich niet zulke subjectieve overwegingen laat leiden.
Inhoud |
[bewerk] Pseudo-toevalsgetallen
Een belangrijk aspect aan toevalsgetallen is dat men voor sommige toepassingen "echte" toevalsgetallen wenst, zoals in geluksspellen, maar voor ander toepassingen pseudo-toevalsgetallen nodig heeft. Dat zijn reeksen getallen die wat diverse criteria betreft niet van echte te onderscheiden zijn, maar desondanks toch reproduceerbaar.
[bewerk] 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. Beie leveren in het algemeen echte toevalsgetallen.
[bewerk] Hoge hoed
De hoge hoed met lootjes is het klassieke voorbeeld van een eerlijke lotingsmethode. Varianten spreken over een doos, vaas of urn met knikkers of ballen e.d. Een tegenwoordig overbekende vorm is de trekking van de lotto-getallen.
[bewerk] 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 absoluut zuivere worp 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 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 volstrekt eerlijk.
[bewerk] Toeval m.b.v. 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 kwantum effecten zoals 'elektronische ruis' waarvan de theorie zegt dat deze volslagen willekeurig zijn. Een sensor meet deze effecten en genereert hiermee willekeurige getallen.
[bewerk] 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.
[bewerk] 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.
[bewerk] 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
[bewerk] Lehmer-congruentie
De tegenwoordig meest gebruikte en goed onderzochte methode is de congruentiemethode van Lehmer, korweg Lehmer-congruentie genoemd. Bij deze methode wordt elk volgend getal verkregen door het vorige met een vast getal A te vemenigvuldigen en daarna modulo een getal M te reduceren. Door geschikte keuze van A en M kunnen zeer goede toevalsgeneratoren ontstaan.
.
[bewerk] 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 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.
[bewerk] Toepassingen
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.
