Transcript Using random numbers

Using random numbers
• Simulation: accounts for uncertainty:
biology (large number of individuals),
physics (large number of particles,
quantum mechanics), human behavior,
etc.
• Testing (large number of cases)
• Monte Carlo evaluation
• Run experiments with humans
• “Anyone who considers arithmetical
methods of producing random digits is, of
course, in a state of sin.”
--- John von Neumann (1951)
What did von Neumann mean?
• Distinguish between “random” and
“pseudorandom”
• Big advantage of pseudorandom:
repeatability
• Big disadvantage: not really random
Sources of “randomness”
• “Digital Chaos”: Deterministic, complicated.
Examples: pseudorandom RNGs in code,
cellular automata
(http://en.wikipedia.org/wiki/Rule_30),
digital slot machines.
• “Analog Chaos”: Unknown initial conditions.
Examples: roulette wheel, dice, card shuffle,
analog slot machines.
• “Truly random”: Quantum mechanics (the world
works microscopically).
Real-time Prediction of sectors in roulette
The Eudaemons were a small group headed by graduate physics students
J. Doyne Farmer and Norman Packard at the University of California Santa
Cruz in the late 1970s.
...
It took two years to develop the computerized system. By 1978 it was
working and the group went to Las Vegas to make money at it. Eventually
the system was split between two persons: an observer
and a bettor. The observer would tap input signals with the foot, the
bettor would receive output signals underneath his/her shirt. The average
profit was 44% for every dollar. However, there were problems: in one
case the insulation failed and the bettor received electric shocks from
the solenoids. But she kept placing bets, so the observer, who in this
case was Farmer, left the table, so that the bettor would be forced to
leave as well. Afterwards it turned out that the solenoid had burned a
hole into her skin. Some members of the group had already left because
of trouble juggling the academic schedule with the Eudaemonics, but the
burning incident caused the two leaders to disband the group
Collectively they had managed to make about $10,000.
http://en.wikipedia.org/wiki/Eudaemons
Linear Congruential Generator
• Most common and
popular --- simple,
fast, pretty good most
of the time
X  aXn  1  c (mod M )
Xn / M
approx. unif. distr. in [0,1)
Xn /( M  1) approx. unif. distr. in [0,1]
Choosing good a, c, M
• [Tez95] gives nec. And suff. Conditions for
LCG to have maximal period, M
• This means we get all the integers in
{0, 1, …, (M-1)} in some order before
repetition, then periodic
• But there are dangers lurking, more later
Using RNGs
• Choose an integer i between 1 and N
randomly
• Choose from a discrete probability
distribution; example: p(heads) = 0.4,
p(tails) = 0.6
• Pick a random point in 2-D: square, circle
• Shuffle a deck of cards
• “Random number generation is too
important to be left to chance.”
--- Robert R. Coveyou (1969)
Danger and Caveats
• M, typically MAXINT, too small. For example,
if
15
M  2  1  32,767
In a million calls the sequence will be
repeated about 30 times!
• Don’t use low-order bits!
• Points tend to be serially correlated
• “Random numbers fall mainly in the
planes.” --- George Marsaglia (1968)
• “Every random number generator will fail
in at least one application.” --- Donald
Knuth (1969)
Quick summary of some probability
theory
• Discrete vs. continuous
• Probability density function f (pdf)
• Cumulative distribution function F (cdf)
x
F ( x) 
 f ( y) dy  prob{ y  x}

f ( x)  dF ( x) / dx
Generating other distributions
• Generate uniformly distributed x
• Then compute y = g(x), where g( ) is
monotically increasing and differentiable
• Then pdf of y is
1
f ( x) | dg ( x) / dx |
Important example
• Exponential distribution
g ( x)  
1

f ( x)   e
ln x
 x
Generating a Gaussian:
Box-Muller method
• Generate
x1 and x2 uniform
• Then
y1   2 ln x1 cos(2 x2 )
y2   2 ln x1 sin( 2 x2 )
are independent, Gaussian, zero mean,
variance 1
Neave effect
• Tails of Box-Muller may be bad
H. R. Neave, “On using the Box-Muller
transformation with multiplicative
congruential pseudorandom number
generators,” Applied Statistics, 22, 92-97,
1973.