So how do they do it? In the old days, there used to be 49 balls in a
tumbler, one would fall out, then another, then another, then another
until there were six. In fact, I seem to recall seeing on TV some of
the televised American lotteries where the same methods were employed.
If you wanted to simulate that, you would need an array of 49 numbers,
then pick a number at random, drop that number out of the array, shrink
it by one and then pick 1 - 48, then 1-47 etc. I guess the issue here
isn't the way that the picking is simulated, but the way that the
randomness is implemented. Is there any computer language, or program
or whatever that is capable of true random number selection based on
"statistically proven techniques" or is everything we consider to be
random just a close approximation?
I think you're right, the more important issue is the source of the
randomness. That's not to say that the question which you posed was not
an interesting programming problem. I think that Patricia's solution is
particularly elegant (once I switched on my brain and understood why she
was doing it that way).
This article
(
http://www.cigital.com/papers/download/developer_gambling.pdf) is an
interesting story of how flaws in random number generation and shuffling
algorithms allowed the authors to exploit an online poker site.
I'm not sure what you mean by "statistically proven techniques" for
generating random numbers. There are however several tests that can be
applied to a sequence of numbers in order to obtain a measure of "how
random" the sequence is (or more correctly, a measure of how confident we
should be that the sequence is truly random, since the statistics don't
actually *prove* anything about the sequence). The most well-known of
these tests is the Diehard suite (
http://stat.fsu.edu/pub/diehard/).
java.util.Random performs poorly on the Diehard suite, whereas
java.security.SecureRandom performs well. I would imagine that the
revelant gaming authorities have tested the performace of the lottery
machines, using Diehard or similar, before awarding a licence in order to
satisfy themselves that the outcomes are sufficiently random.
People who are seriously interested in good quality, unpredictable random
numbers (i.e. cryptographers and online gaming operators) will typically
use hardware devices that extract entropy from physical processes such as
radioactive decay or electronic noise. The random bits from these devices
(which are invariably slow) are often used as a seed for a PRNG with known
statistical properties rather than relied upon in their own right.
A cheaper variation on this theme is to rely on sources of randomness that
are already present in the computer hardware. The Solaris kernel, for
example, extracts entropy from I/O timings in order to provide random
numbers via /dev/random.
Are you interested in lotteries just as a programming exercise or are you
seriously hoping to find a way to beat the system?
If you are interested in this kind of thing, maybe you should consider
other types of gambling (i.e. roulette, blackjack, poker). For a start,
the expected return on the lottery is abysmal (only about 50% of the money
staked goes into the prize pool). So you have to have a huge edge in
order to overcome the inherent disadvantage of playing the game in the
first place. Blackjack on the other hand has an expected return of
somewhere in the region of 99.4% (depending on the exact rules in use).
In other words, if you play optimally (and it's not difficult to learn to
do so), on average you will only lose 3 cents for every $5 you stake.
This is still a losing proposition in the long-run, but you'd only need to
find a slight edge to turn it around. Traditionally professional gamblers
found this edge by card-counting, but the casinos have since introduced
measures to prevent this such as using more decks and a continous
shuffling machine.
The book "Fortune's Formula", by William Poundstone, is a good read.
Among other things, it discusses money-making systems that have been used
for Roulette, Blackjack and the stock market and looks at the ideas behind
them, dating back to Shannon's work on information theory in the 1940s.
Dan.