home | index | units | counting | geometry | algebra | trigonometry & functions | calculus analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Randomness  &  Randomizing

Small compound bodies are set in perpetual motion
by the impact of invisible blows.

"De Rerum Natura"   Titus Lucretius Carus  (99-55 BC)

Entropy-based  True Random Number Generators  PCQNG 2.0 & J1000KU

Wikipedia :   Mersenne Twister

The Search for Randomness (1:00:12)  by  Jean Bourgain   (IAS, 2009-03-25).

Persi Diaconis :   How random is a coin toss?   |   Should you catch a tossed coin?   |   Extra footage

True Randomness and Randomizing Procedures

Paul Grover (2006-05-04)   "Normal" objects are truly "random" ones.
If the sequence  86201796873546873804 occurs at the bazillionth place in the decimal expansion of  p , isn't it less "random" than it looks?

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.

(2007-05-19)   Flipping a Fair Coin
The best way to build a fair coin from a true source of randomness.

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...

(2014-12-31)   Random integer between  0  and  n-1.
Obtaining equiprobable integers below n from a random stream of bits.

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 < 2).

By fetching  m  random bits from our stream, we obtain a random integer below  2.  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.

(2014-01-20)   Burning cards.

"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.

(2014-01-20)   Shuffling n cards.
Randomly choosing one of  n!  possible orderings.

Fisher-Yates shuffle (1938)
The computer version was introduced by  Richard Durstenfeld  in 1964 and popularized by Knuth.

(2014-01-20)   Cheating Legally at Online Poker
Synchronizing two pseudo-random number generators.

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".

(2006-05-06)   Probability Measure
The classical definitions apply to finite sets or  uncountable  ones.