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