Transcript CS 450 – Modeling and Simulation

CS 450 – Modeling and Simulation
Dr. X
Topics
•
•
•
•
What Does Randomness Mean?
Randomness in games
Generating Random Values
Random events in real life: measuring
randomness
What is Randomness?
• Unpredictability?
• Does it characterize a single event or a
sequence of events?
• From Wikipedia:
Randomness means lack of pattern or
predictability in events. Randomness suggests
a non-order or non-coherence in a sequence
of symbols or steps, such that there is no
intelligible pattern or combination.
Randomness in games
Probability 101
If you roll the dice twice, what is the probability
of rolling two sixes?
Probability vs odds
• Odds =
Favorable Outcomes / Unfavorable Outcomes
• Probability =
Favorable Outcomes / All Outcomes
Probability 101
If you toss two coins what is the probability of
HH?
Probability 101
• Independent events
• Logical relations:
– AND
– OR
Defining Randomness
• How can a computer generate random
numbers?
• Can we measure randomness?
Measuring Randomness
•
•
•
•
Runs Test
Frequency test
Autocorrelation test
Chi-square goodness of fit
Statistical Hypothesis test
• H0: Null Hypothesis, ex., a sequence of
numbers is random
• Hα: Alternative Hypothesis, ex., a sequence of
numbers is NOT random
Real Situation
Decision
H0 is not rejected
H0 is rejected
H0 is true
Valid
Type I Error
H0 is not true
Type II Error
Valid
Runs test
• Sequence of numbers X1, …, XN
• Subtract Xi+1 – Xi
• Collect only the signs of the subtraction
results
• Do the signs alternate ~50% of the time?
Frequency Test (Monobit test)
• Create a string Sn = X1 + X2 + … + Xn
• Calculate Sobs = Sn/n
• Calculate P-Value:
P-value = erfc(Sobs/2)
where erfc: complementary error function
• If P-value > 0.01 accept the null hypothesis
else reject
Autocorrelation Test
Intuition: if the sequence of bits in e is random,
then it will be different from another bit string
obtained by shifting the bits of e by d positions.
Chi-Square Goodness of Fit Test
• Intuition: test checks whether a sequence of
pseudo-random numbers in [0,1] are uniformly
distributed
• If you have n numbers and split them in k groups,
then if in the groups you have n/k numbers the
distribution is normal
• Compare all observed values fi inside your kth
group with the mean n/k
• If chi-square > theoretical x2 obtained from table
with k degrees of freedom, then null hypothesis
rejected
Generating Random Numbers
•
•
•
•
Congruential method
Tausworthe generators
Lagged Fibonacci generators
The Mercenne Twister
Congruential Method
xi+1 = axi + c (mod m)
• a, c, m: non-negative
• If m is large, period of number repetition is
large
• Conditions for full period:
– m and c have no common divisor
– a = 1 (mod r) if r is a prime factor of m
– a = 1 (mod 4) if m is a multiple of 4
Tausworthe generators
• Additive congruential generators
• Modulus m is equal to 2
• xi = (a1xi-1 + a2xi-2 + ...+ anxi-n) (mod 2)
where xi: 0 or 1
• Mod 2 is equivalent to XOR
Lagged Fibonacci Generators
• Based on Fibonacci series: xn = xn-1 + xn-2
• LFG: xn = xn-j O xn-k (mod m)
where O: addition, or subtraction, or
multiplication, or XOR
Mersenne Twister
xk+n = xk+m ⊕ (xku | xk+1k )A, k≥0
Where x is the block of numbers of w bits
References
• The Guide to Computer Simulations and
Games, By Katrin Becker and J.R.Parker, Wiley
(Chapter 6)
• Computer Simulation Techniques: The
Definitive Introduction, by Harry Perros,
http://www4.ncsu.edu/~hp/simulation.pdf
(Chapter 2)
CS 450
21