How random is RANDOM

[Christian.Arvai]

Just for fun testede jeg lige præcisionen på Random i bash med en terning 1.000.000 gange. Det ender faktisk rimeligt random:

Kode: Vælg alt

chr@chr:~$ /home/chr/die.sh


ones =   166607
twos =   165683
threes = 166465
fours =  166924
fives =  166912
sixes =  167409

chr@chr:~$ 

Jeg prøver lige at se om min pc koger af, hvis at jeg prøver med 1.000.000.000

[Christian.Arvai]

MAXTHROWS=10000000

Kode: Vælg alt

chr@chr:~$ /home/chr/die.sh


ones =   1666619
twos =   1665531
threes = 1667795
fours =  1667018
fives =  1666097
sixes =  1666940

chr@chr:~$ 

[AJenbo]

Pas på du ikke forveksler statistisk med tilfældig.

[Christian.Arvai]

Pas på du ikke forveksler statistisk med tilfældig.

Ægte tilfældighed kan aldrig laves med en Random, hverken i Bash, Java eller andre programmeringssprog. Man kan så lave en tilfældighedsgenerator som rammer ret tæt på, men stadigt er dette ikke en tilfældighed (ægte random), da jeg jo har programmeret den til dette før kørsel.

Output er i dette tilfælde statistik over de genererede værdier (slag med en terning 1-6). Sådan set kan jeg også få den til at smide hver enkelt slag. Det vil så fylde ret meget i CLI.

Så vidt at jeg ved, er den eneste rigtige måde at lave fuldstændig tilfældighed, at sætte udstyr op som måler svingninger i atomer, og derefter omsætter disse svingninger til værdier. Det er så DTU vi skal have fat på

[Christian.Arvai]

Jeg smider lige scriptet og kildeangivelse til forfatteren op, og så flytter jeg indlægge til Sandkassen. Der kunne jo være folk som gerne vil se koden

[Christian.Arvai]

Kilde: http://www.tldp.org/LDP/abs/html/randomvar.html
Forfatter: Bill Gradwohl

Example 9-15. Rolling a single die with RANDOM

Kode: Vælg alt

#!/bin/bash
# How random is RANDOM?

RANDOM=$$       # Reseed the random number generator using script process ID.

PIPS=6          # A die has 6 pips.
MAXTHROWS=600   # Increase this if you have nothing better to do with your time.
throw=0         # Number of times the dice have been cast.

ones=0          #  Must initialize counts to zero,
twos=0          #+ since an uninitialized variable is null, NOT zero.
threes=0
fours=0
fives=0
sixes=0

print_result ()
{
echo
echo "ones =   $ones"
echo "twos =   $twos"
echo "threes = $threes"
echo "fours =  $fours"
echo "fives =  $fives"
echo "sixes =  $sixes"
echo
}

update_count()
{
case "$1" in
  0) ((ones++));;   # Since a die has no "zero", this corresponds to 1.
  1) ((twos++));;   # And this to 2.
  2) ((threes++));; # And so forth.
  3) ((fours++));;
  4) ((fives++));;
  5) ((sixes++));;
esac
}

echo


while [ "$throw" -lt "$MAXTHROWS" ]
do
  let "die1 = RANDOM % $PIPS"
  update_count $die1
  let "throw += 1"
done  

print_result

exit $?

#  The scores should distribute evenly, assuming RANDOM is random.
#  With $MAXTHROWS at 600, all should cluster around 100,
#+ plus-or-minus 20 or so.
#
#  Keep in mind that RANDOM is a ***pseudorandom*** generator,
#+ and not a spectacularly good one at that.

#  Randomness is a deep and complex subject.
#  Sufficiently long "random" sequences may exhibit
#+ chaotic and other "non-random" behavior.

# Exercise (easy):
# ---------------
# Rewrite this script to flip a coin 1000 times.
# Choices are "HEADS" and "TAILS."

[Christian.Arvai]

MAXTHROWS=100000000 (100 millioner)

Kode: Vælg alt

chr@chr:~$ /home/chr/die.sh


ones =   16673196
twos =   16666886
threes = 16663910
fours =  16666540
fives =  16668407
sixes =  16661061

chr@chr:~$ 

[Christian.Arvai]

MAXTHROWS=1000000000 (1 milliard)

Kode: Vælg alt

chr@chr:~$ /home/chr/die.sh


ones =   166678171
twos =   166690535
threes = 166667649
fours =  166667478
fives =  166660405
sixes =  166635762

chr@chr:~$ 

Det må vist være nok

[NickyThomassen]

UNIX-baseret systemer har /dev/random, og i visse tilfælde også /dev/urandom. Fælles for dem begge, er at de samler støj fra computeren, deriblandt brug af tastaturet, som alt i alt må formodes at være tilfældigt. Ud fra støjen laves der så en pulje med adskillige kb tilfældige bits.

Disse bits kan bruges til at starte noget tilfældigt op, fx ved at erstatte PID som seed i terningsprogrammet. Serverprogrammer som web og mail bruger seeds fra /dev/random til at starte TLS-forbindelser.

Forskellen imellem /dev/random og /dev/urandom er, at /dev/urandom (u'et står for unblocking) bruger en algoritme, til at levere "tilfældige" bits i tilfælde af at systemet løber tør. Algoritmen er dog startet op med en eller flere bits fra støjen, så den burde køre semi-tilfældigt.

https://en.wikipedia.org/?title=/dev/random

[Christian.Arvai]

Scriptet virker tilsyneladende også med URANDOM. Jeg prøver lige at smide det på opgaven, og så kan vi sammenligne output.

[Christian.Arvai]

URANDOM

MAXTHROWS=10000000

Kode: Vælg alt

chr@chr:~$ /home/chr/die.sh


ones =   1666891
twos =   1668247
threes = 1665170
fours =  1666624
fives =  1667448
sixes =  1665620

chr@chr:~$ 

[AJenbo]

Tja det viser vist blot at dette ikke er en god måde at se om resultatet er tilfældigt

[Christian.Arvai]

Tja det viser vist blot at dette ikke er en god måde at se om resultatet er tilfældigt

Det giver ikke den store forskel på denne måde. Hverken Random eller Urandom har intet med ægte tilfældighed at gøre, som jeg også tidlige nævnte.

Test-metoden er sådan set god nok til dette formål. Man skulle så kører de samme scripts mange gange og sammenligne dem på den måde. Spredningen/tilfældigheden burde være større, hvilket at den givetvis også er på mindre antal Random, som fx i et dæk med kort der deles ud.

Jeg gider så ikke kører scripts på flere timer mange gange, og slet ikke at regne statistikken ud bagefter

[thj01]

Problemet med en en hvilken som helst random er, at den fungerer ud fra nogle principper. Derfor anvendte man før computeren store (MEGET STORE) bøger med tabeller over tilfældige tal.

Men man kunne lave det "mere" rigtigt ved at lave følgende procedure for terningkast

Indlæs en række random tal i et array/tabel (0-0,99999999999999 - vælg et decimaltal)
lad computeren udvælge en måde at inddele ovenstående område i f.eks. 60 (delbar med 6) forskellige segmenter - . skriv disse til arrays/tabeller og tæl antallet af elementer i hver.

summer tilfældigt 10 (da eksemplet er 60) af disse tal i 6 grupper og giv hver af disse grupper en terningværdi


Desværre tror jeg at du vil finde den perverse sammenhæng at der ingen signifikant forskel bliver mellem fordelingen af terningkast - men til gengæld har du lavet "blinde" udvælgelser af de værdier du får .

PS. Ovenstående kan garanteret skydes i sænk matematisk, men tilfældighed kan nu engang kun laves helt rigtigt ved gøre det analogt - og det er en ret træls proces

Og så kan du jo køre det i en lække igen og igen, og så summere op efter hver kørsel. Så hvis du tager på weekend kan du lade din maskine køre små kørsler hele tiden og kun forfine udfaldet hver gang. Men det er nok ret dyrt i strømforbrug at konkludere at der er 1/6 chance for hver terningværdi (ved en D6'er

[lath]

En Raspberry Pi har en rigtig(=læses som "ikke i software") tilfældighedsgenerator. En ægte tilfældighedsgenerator kaldes forkortet for en TRNG.
http://scruss.com/blog/2013/06/07/well-that-was-unexpected-the-raspberry-pis-hardware-random-number-generator/

/dev/hwrng er devicet for en Raspberry Pi´s TRNG.

En TRNG laves ved at i man gennemsnit genererer mere end 1 bit (f.eks. 1,4 bit tilfældighed), der så samples af en 1-bit A/D converter.
Det kan f.eks. laves fra en en PN overgang i en transistor som støjer. Den støj kan man forstærke, og så 1- bit A/D konvertere støjen.

En TRNG baserer sig på kvante fænomener der giver ægte tilfældighed.
Læs evt mere på: https://en.wikipedia.org/wiki/Hardware_random_number_generator

/Lars