Testning av slumpgeneratorer: Så bra (eller dåligt) slumpar de
En slumptalsgenerator är sällan en "äkta" källa till slumpmässighet. Istället använder datorer algoritmer för att generera tal som verkar slumpmässiga, men som egentligen följer en bestämd sekvens baserad på en initial siffra, kallad seed. Därför kallas de ofta pseudoslumptal.
Dessa algoritmer är deterministiska, vilket innebär att om man matar in samma seed får man alltid samma sekvens av tal. De används i en mängd olika tillämpningar, från kryptering till simuleringar och spel, men har begränsningar:
- Periodicitet : Eftersom sekvensen genereras med matematiska regler, upprepar den sig förr eller senare.
- Autokorrelation: Om en generator är dålig kan tidigare genererade tal påverka framtida tal på ett förutsägbart sätt.
- Snedfördelning: Vissa generatorer kan generera vissa tal oftare än andra, vilket leder till en snedfördelning.
- Mönster och bias : En svag algoritm kan producera sekvenser där vissa mönster förekommer mer än slumpen borde tillåta.
För att säkerställa att en slumptalsgenerator är bra måste man testa den på olika sätt.
Chi-två-test (χ²-test)
Detta test undersöker om de genererade talen är jämnt fördelade över ett visst intervall. Genom att dela upp intervallet i bin (t.ex. 10 stycken för tal mellan 0 och 1) och räkna antalet tal i varje bin, kan man jämföra den observerade fördelningen med den förväntade (om generatorn vore perfekt).
Om skillnaden mellan observerade och förväntade värden är stor, tyder det på att generatorn inte producerar jämnt fördelade tal.
En hög χ²-statistik innebär att det är mindre sannolikt att siffrorna är slumpmässigt genererade.
Gap-test
Detta test mäter hur länge det dröjer innan en viss siffra eller intervall återkommer. Om man till exempel testar slumpmässiga tal mellan 0 och 1 och letar efter hur många tal som genereras mellan två upprepningar av ett visst intervall (t.ex. 0,2–0,3), bör dessa gap följa en förväntad sannolikhetsfördelning.
En dålig generator kan ha för få eller för många korta/långa gap, vilket tyder på mönster i talserien.
Kupongtest
Detta test undersöker hur lång tid det tar att få alla möjliga utfall minst en gång. Ett klassiskt exempel är att samla alla olika samlarbilder i ett album genom att köpa slumpmässiga paket. I en väl fungerande slumpmässig generator borde det ta ungefär N log(N) steg för att få alla N möjliga utfall.
En dålig generator kan generera vissa utfall för ofta eller sällan, vilket gör att vissa värden är över- eller underrepresenterade.
Dessa tester ger en bra bild av hur bra en slumptalsgenerator är på att simulera äkta slump. I praktiken används ofta en kombination av flera tester för att säkerställa kvaliteten på en generator. Exempelvis används Diehard-testet och TestU01 i vetenskapliga sammanhang för att utvärdera och jämföra olika algoritmer.