Wikipedia : Mersenne Twister
The Search for Randomness (1:00:12) by
Jean Bourgain (IAS, 2009年03月25日).
Probability, symmetry, linearity
[1,
2,
3,
4,
5,
6]
Mikhail Gromov (IHES, 2014).
Persi Diaconis :
How random is a coin toss?
|
Should you catch a tossed coin?
|
Extra footage
Lisa Goldberg :
Hot hand in basketball?
|
Extra footage
Yes, this sequence is very special and can't be called "random" in any absolute sense... Just like any other finite sequence of digits.
Actually, we have to look at it backwards: Unless the decimal expansion of p is not "normal" a finite sequence like this does occur in it infinitely often...
A decimal sequence is said to be normal (which really means it's not special) if and only if any subsequence of length k occurs in it with probability 10-k.
You have a radioactive source with a Geiger counter which send clicks to your computer at random intervals, according to a Poisson process of activity l (which is to say that the probability of a click in a infinitesimal interval dt is equal to l dt ). What's an optimal way to obtain from that a stream of very random bits at a very fast rate?
Well, there's clearly a tradeoff between the speed of the stream and the randomness of the bits in it. If the ouput stream is so fast that no clicks are received during the ouput of many bits, then the computer can do no better than issue "pseudorandom" bits according to a deterministic algorithm. To a synchronized observer (another computer sharing the same clock) which correctly guesses the algorithm, the output stream will not look random at all.
For the sake of simplicity, we may as well assume that the computer merely decides to issue either a 1 or a 0 according to the time (t) elapsed since the last request for a random bit (this need not be a constant interval) and the number of clicks (n) received during that time. The probability that n clicks have been received is:
Pn = exp(-lt) (lt) n / n!
At the very least we want to derive the flip of a fair coin from that distribution... This is to say that we'd like to have a subset of the natural integers whose probability is exactly ½ according to the above Poisson distribution.
This is rarely possible if we limit ourselves to a single event, but we may involve previous random events to reach stochastic perfection as fast as possible. Count the parity of the previous m events...
Here's how to obtain with equal probability any nonnegative integer below n:
Let m be the bit length of n-1 (i.e., the least m such that n < 2m ).
By fetching m random bits from our stream, we obtain a random integer below 2m . If that integer is below n, it will be any number less than n with probability 1/n and we may take it as our result. Otherwise, we just discard all the fetched bits and start again with fresh ones, having "wasted" m bits with a probability smaller than 50%. The expected number of random bits used by this procedure to obtain a valid resilt is less than:
m / 2 + 2m / 4 + 3m / 8 + 4m / 16 + ... = 2 m
We could be slightly more frugal by fetching the most significant bits first and aborting the operation as soon as we know that we can't possibly obtain a number less than n.
"Burning" is the time-honored practice of discarding one or several card for the top of a deck of playing cards before dealing them.
Burning cards does not help randomize the deck but it helps protect the unpredictability of the deal by preventing the use of distinct signs at the back of the deck.
[画像: Come back later, we're still working on this one... ]
Fisher-Yates shuffle (1938)
The computer version was introduced by Richard Durstenfeld in 1964
and popularized by Knuth.
This was actually done by Brad Arkin, Frank Hill, Scott Marks, Matt Schmid & Thomas John Walls. They documented the details on Developer.com (September 1999) under the title: "How We Learned to Cheat at Online Poker: A Study in Software Security".
