Real Random number generation....

Jorge P

A few months ago, I was thinking about how computers/microcontrollers generate random numbers. Most use a seeding value based off of a system clock. I knew that US State lottery systems would not want something that is not realy a real random number so I wrote an email to Lottery headquarters to see if they could tell me how they generate random numbers for the US lotteries quick pick tickets.

A few weeks ago I got a reply stating

Lottery Headquarters said...

I am not aware of any legal issues relating to persons who wish to sell number selection software or devices.

We do not allow use of our logo without compensation. We’ve spent millions of dollars to make the logo and brand able to attract people’s attention. That benefit is for us alone.

We write our own number picker software here, using radio-active material and a Geiger counter to produce true random numbers.

Now, I had a smoke detector with a carbon monoxide detector built into it a few years ago, I was curiouse as to how it worked and started taking it appart, Inside I found a small can style component that had a radiation warning label. Can a component like that be used to make a hardware random number generator, like the kind that the lotteries use to generate quick pick numbers, and smoke detectors use, for gaming on the hydra???

It would be neet to understand how this works a bit more, especialy with the Propeller and Stamp, and how to make a real random number generator for our little microcontrollers. It would take the Hydra to a new gaming level with real random number generation and make gameplay never result the same or repeated actions that rely on random numbers.

This type of device would be a sensor, wouldn't it??

Please help me understand this a bit better, thanks in advance.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
---
http://WhatsAvailable.org Software and Gadgets for Windows 7.

pmrobert

If you Google for "radioactive random number generator" and then "ionization smoke detector" you'll find everything you want to know then some. Please don't open the ionization chamber - there is only a small amount (< 0.5 ug ) of americium-241 and with a 400+ yr. half-life it's not all that active BUT it is an alpha emitter and if ingested by any means all of the emitted energy is absorbed with the first couple of mm of tissue it's in. It's pretty well encapsulated but this needs to be mentioned.

Leon

Many lotteries and on-line gaming companies use this quantum RNG:

www.idquantique.com/true-random-number-generator/products-overview.html

They aren't expensive.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM

pmrobert

And, if you wanted to fool with a DIY deal, ebay has quite a few old-school CDV-700 geiger counters available. I had one somewhere, found it (after it being stored for 10 years or so), put batteries in it and it works nicely. A bonus is that they have a check source attached (usually) to the side of it so you don't have to fool with safely obtaining a source of radioactivity. I *think* the check sources were DU (depleted uranium) so they should be good to go for a few hundred thousand years. Theunits also have a "phone" output which I seem to recall sent audible "clicks" to headphones every time the GM tube triggered. This possibly could be used as an output.

Chris Savage

I've always felt my own random routines were sufficient because they incoporated a human element. That is...in my programs where a random number was to be generated I would shuffle the random seed continuously within the main loop so that when the button was pressed for the random number, it would not be certain how much the seed had been randomized. Of course this only works when a human inputs a time-independant signal at some point, however for your application I think that the fact that you're requesting the values implies this will work for you.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chris Savage

Parallax Engineering
·

ElectricAye

I'm not sure if it matters or not. I guess that depends on what you're trying to do with your random numbers.
As for a reference, consider the history of RAND's Million Random Digits. As I recall, they used some kind of quantum based system (radioactive decay?) only to find that a pattern had developed in the digits. They had to "purify" their results several times.

The eternal problem, as I recall, has to do with the detector threshold circuitry. Even if you are monitoring physical events that are purely quantum mechanical in nature, your detection equipment, which establishes the threshold, is a non-quantum mechanical system, which therefore has harmonics, oscillations, etc. Given enough time, these harmonics will show up in your mass of random numbers. In other words, because of harmonics, etc. in the detector circuitry, the threshold will move up and down as it observes a quantum mechanical system. This movement of the threshold therefore creates a bias in the data, and this, by definition, is not truly random.

It's weird when you think about it. We accept that we live in a cosmos that has randomness as its background, but that very same randomness appears to be completely inaccessible.

www.americanscientist.org/issues/pub/randomness-as-a-resource/1

Old comments extracted from here:

http://forums.parallax.com/showthread.php?p=639978

PJAllen

"We accept that we live in a cosmos that has randomness as its background..."

I hereby except myself from we.· Periodicity is everywhere, sometimes you have to wait for it longer than you'd prefer.

Jorge P

So if I wanted to make my own lotto number generator, I should just get some ping pong balls and start writing numbers on them, throw them in a tank, stir them up with a leaf blower, and come up with a contraption to catch the balls one at a time till I have picked my set?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
---
http://WhatsAvailable.org Software and Gadgets for Windows 7.

Granz

One more, less expensive, alternative: Hook a carbon microphone to a 555 timer, run the output of that to a binary counter (4040 perhaps) and then to an n-bit latch (however many bits you wish to be able to read) - when you wish to read a random number, just strobe the counter into the latch and then read the output. You can even use that number as a seed for whatever random number generator you normally use.

A truly silent area is extremely rare and any background noise is usually constantly changing... City: car engines, motorcycles, sirens, dogs barking, people talking, planes, etc. Rural: animals, tractors, people talking/yelling, guns, etc. And the changing noise will constantly change the speed at which your counter increments. Thus you will have a fairly decent randomness in this simple circuit.

This was not my original idea, I got it from somewhere back in the seventies or maybe the early eighties. I think that it may have come from Byte, but it could have been from any of dozens of different magazines or hundreds of books which I have read over the years.

Art

Post Edited (Granz) : 6/10/2010 6:54:39 PM GMT

Jorge P

Granz said...
One more, less expensive, alternative: Hook a carbon microphone to a 555 timer, run the output of that to a binary counter (4040 perhaps) and then to an n-bit latch (however many bits you wish to be able to read) - when you wish to read a random number, just strobe the counter into the latch and then read the output. You can even use that number as a seed for whatever random number generator you normally use.

A truly silent area is extremely rare and any background noise is usually constantly changing... City: car engines, motorcycles, sirens, dogs barking, people talking, planes, etc. Rural: animals, tractors, people talking/yelling, guns, etc. And the changing noise will constantly change the speed at which your counter increments. Thus you will have a fairly decent randomness in this simple circuit.

This was not my original idea, I got it from somewhere back in the seventies or maybe the early eighties. I think that it may have come from Byte, but it could have been from any of dozens of different magazines or hundreds of books which I have read over the years.

Art

I also thought about wind speed sensor tied in with a wind direction sensor...

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
---
http://WhatsAvailable.org Software and Gadgets for Windows 7.

ElectricAye

Instead of radioactivity or some macroscopic natural event like the wind or northern lights, why not amplify the noise across a diode or something? Look up Johnson noise and random number generators. I'm sure something like that would work well enough for lottery level purposes. My only point about random number generation and the kinds of problems RAND had is that getting "true" randomness is much harder than most people suppose. And if you pay any attention to the offbeat work done at Princeton (see PEAR www.princeton.edu/~pear/0 well then you've got even more to worry about than just threshold oscillations: you've got those men who stare at goats.

Leon

The problem with Johnson noise is that it can be influenced by external factors such as temperature.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM

Post Edited (Leon) : 6/11/2010 4:04:11 AM GMT

cessnapilot

@Jorge P

You can make a True Random Number Generator with SPIN + Prop only. See

http://obex.parallax.com/objects/501/

The demo starts with that, as far as I remember. There was a long post dealing with the tests of true randomness with Prop. http://forums.parallax.com/showthread.php?p=839776. Some of the simple, but strong tests mentioned there was done. So far, so good.

Cheers,

Istvan

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


Intentionally Left Blank

Post Edited (cessnapilot) : 6/11/2010 5:44:09 AM GMT

Leon

That technique is OK for non-critical applications, but it will be subject to external influences.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Leon Heller
Amateur radio callsign: G1HSM

Markov

If you can achieve your goals, Jorge, you will have also developed the first perpetual motion machine at the same time!!!

Markov's musings on Randomness:

For Randomness to exist, it must always exist within something (which is to say a system). {So it is not exactly true to say that the "background" of the universe is 'Randomness' but rather as common sense that may be true (not a valuation but a recognition that "Common Sense" is no more than popularly held convictions but by mostly highly superstituous (random) carbon units.)} If you want to be precise: you might say something like: Randomness is inherent to the universe or you can think up your own analogies and metaphors (Socrates and Plato are exhausted).

Thus, it is not possible for Randomness to exist independent of a system as Randomness would be "Zero" which is not random at all--and indeed is the only state of being completely devoid of randomness. However, it turns out "Zero" is inherently the least stable state of all (number and anywhat number might represent.) So the existence of true "Zero" is first seen to be pragmatically impossible and otherwise its possibility approaches the limit of zero, as its statistical probability measured in time is derived as time approaches its limit as infinity approaches zero. That is, it is so instable that it could never 'Really' exist (of course not in this universe but also in whatever it wasn't before it (it's time)).

It is this inherent impossibility of Zero but its essential presence in the universe that leads some Astrophysicists to postulate the Big Bang {at the least, this will always happen as a matter of time (some statistical probability) and furthermore--it has to happen all at once (the system or universe is born as a BIG Bang not because the Titans are getting it on but because too once Zero is no more then the laws of thermodynamics become true and Randomness is born along with its identical twin Entropy.)} Some see Randomness and Entropy as "Evil" (anthropomorphizing abstractions inferring the concrete) but without 'these' --nothing would ever happen and thus nothing would exist, which is impossible--impossible to go back to Ground Zero as Ground Zero is essentially impossible. I think it was Mike Green who explained to someone that all energy conversion is inefficient which is just a way of stating the Second Law of Thermodynamics (because of Entropy,which the Second Law defines as the 'undefined' --it is a plug figure truely inexplicable and at least defies definition as much as "Justice.") Thus the universe is in a constant state of decay--which we generally take to be agonistic--but that is a personal assumption fallicious in general.

Furthermore, the sum of the universe from before the BigBang til the variable "Now", has not violated eighth grade algebra, and will not ever. It all adds up to zero still--only this zero is derived and more stable than the Absolute Zero that one might say was before the Big Bang {But you might start to suspect this time actually never happened (except as a theory or empty thought)}. For anything to move--requires energy and incurs entropy as something neccessarily leaks to the other side of the universe circut (i leakage. Randomness seems to prevail in the selection of i's contents.)

Now we can say something about the oxymoronic character of Randomness: For the same reasons: we know that the universe is "Self-Organizing" -- that is due to the instability of Zero, presence of Randomness and (it is not true to say that "it leads to" but you might more easily comprehend this better to think it this way) its logical involvement in the or any system. We are necessarily making rather abitrary divisions and definitions to comprehend this. Socrates (Plato) made a livelihood of the same impossibilties within the universe of language. We can postulate why of these, including why any particlular Random Generator fails as did Electric Eye.

But even when dealing with purely abstract quantities--number--patterns will eventually emerge in any seeming random string--no reason --it is just statistically bound to happen and, if you understand probablility--even the smallest concievable probability will eventually happen. If we have a physical system generating Randomness we can pinpoint a likely source but in better cases it really is not the source of error but inevitable (worse cases are obvious bad designs.)

So to do what you propose, Jorge, we would have to develop a Random Motor-Generator out of nothing which would remain nothing still (cannot have any system to it). The same for a perpetual motion machine-which requires that the machinbe must but cannot possibly exist at the same time. (THey would be the same although we take them to not be identical concepts).

The odd thing then is that we exist in a finite function of time and if we look toward the future--its endpoint is said to be infinity (it seems to approach infinity). The same applies looking toward the past--We know there was a Big Bang that happened at what appears to be infinitely small--b ut the Before cannot have existed. This (better stated of course) led Einstein (he really wasn't first to say this) to postulate that time had to be curved--and led to the quantification of Energy as an exponential function of time (curved).

'Things' like this is why so many mathematical minds are schizo -- or break and go crazy. Math geniuses as a group do their great work at any average of 25 years of age--by 30 a large number of them are nuts or dead. John Nash (The Movie: The Beautiful Mind) is one example. I believe it was the guy who proved 'fractals' that after presenting his thesis disappeared only to call a colleague at midnight to say they cut off his ears and cut out his tongue just before he commited suicide. On the other hand, we live in a universe populated by imaginary and irrational numbers as well as 'the more convenient.' It is said that the School of Protagoras murdered the ingenious mathematician who proved to them the existence of Irrational Numbers.

So you cannot by design, we could say, build a perfect random number generator. So what is done is to change the goal to "good enough" -- whether one uses some sort of timer and/or lookup table of some sort or if one purchases random numbers from Rand or say Markov or Parallax. It comes down to the intended use and economics.

Markov is AI drone named for Randomness--after person Markov who devoted life to studying randomness--developed what is known as :Markov Random Process Simulation Model.

Markov

In short:

Randomness is inherent to any system (along with Entropy) but can never be grasped but only simulated. No simulated system is perfect by definition.

"Good Enough"

'..." (how do you draw an ellipsis?)