Analyzing Random numbers

Thread Starter

Wendy

Joined Mar 24, 2008
21,914
Randomness is all around us. an d yet it is surprisingly difficult to generate a truly random number electronically. Among the first projects I ever built were head/tails and dice, The heads tails was a flop. Doing a hundred tosses a definite bias appeared, it wasn't major but statistically noticeable. It was enough I scrapped the project. So if someone presents you with a table of random number how do you test them? distribution of number is one way, If you have a list of numbers between 1 and 6 (dice)then all of the numbers should show up 16.7 % 0f the time .This percentage is rounded, so there is an error right there. ( 100/6) Statistics can be tricky, it is an entire branch of math unto itself. But like I said, true randomness is very common and electronics can be used to take advantage of it to create a true random generator.

Of course, Chaos theory steps up to make things complicated where we were hoping for simplicity, but since I am no math whiz I choose to ignore it as inconvenient for now (just being smart enough to know my limitations.

In its simplest form a random generator cane be the simply a one or a zero (Heads/tails). You can check for bias by flipping it 1000 times, If it is truly random you wind up with 50%/50% distribution, you know it is bias free at that point, but what about other forms of distortion that means it is not truly random, There are names for them but I am too ignorant to know how to even describe them, how would you test for them and what are they? If someone gives you a list of 1 billion 1's and 0's claiming it is a truly random table you could chop it up into byte size chunks, throw away any numbers that are out of range and generate a table that can be used as you desire. How do you make sure this list is random? Distribution offers one cheap and dirty test, as I have talked about.

How to generate randomness

Electronic noise (AKA white noise) frequently used for S/N measurements. ideally it is random as it is a frequency band containing all the frequencies in a defined band. Precision notch a frequency out and feed this though an amplifier any noise introduced by an amplifier is a measurement of signal to noise. This offers a strong hint as to a source of white noise. Thermal noise is a random quantity in nature find a component that is noisy to generate whit noise and you have a potential white noise generator Yet the S/N test shows one of the distortions I am discuss int We are removing a specific component of the frequency distribution. So could some version of a spectrum analyzer be used to check our random generator source? Dang if I know.

Another natural source of randomness is radioactivity. I have repeatedly read that particle decay is statistically random in nature, There are plenty of mildly radioactive source available out there, Not so for particle detectors, Other than Geiger tubes I don't know of any solid state device that can detect a particle from a radioactive decay event. I would love to find an alternative.

So where am I going with this?

I am about to start a thread on possible ways to create a hypothetical 1Billion digit random binary number and am looking for ways to test it if I did. I was stuck on a long Taxi ride to nowhere and I was mulling this problem over in my head to keep me occupied. Yep I quite literally had too much time on my hand.

Discuss?
 
Last edited:

Thread Starter

Wendy

Joined Mar 24, 2008
21,914
At $53, not real high on my short list of WTB items, I suspected something like that is out there. Like said there is a whole realm of math I am barely aware of.

The S/N analogy does have a good comparison. I f you reduce or notch out a specific number It would only show up on the distribution chart. As a notch no less.
 
Last edited:

Thread Starter

Wendy

Joined Mar 24, 2008
21,914
Math is a subject that is always relevant, Kinda like Boolean algebra, which was invented long before computers. Sure came in handy later though. Wonder if Babbage used it?
 

Papabravo

Joined Feb 24, 2006
12,686
At $53, not real high on my short list of WTB items, I suspected something like that is out there. Like said there is a whole realm of math I am barely aware of.

The S/N analogy does have a good comparison. I f you reduce or notch out a specific number It would only show up on the distribution chart. As a notch no less.
Nobody said you had to buy a new one. The books were much cheaper when I purchased them. $20.00 for a used edition seems about right. If you want to do things on the cheap, be my guest, but your efforts may lack something in exchange for that economy.
 
If you consider the task,
possible ways to create a hypothetical 1Billion digit random binary number and am looking for ways to test it if I did.
How I think about this is as follows:

Each digit has a possible value of 0-9. The definition of randomness for this demonstration is that, for each digit, every possible value has an equal probability of occurrence.

It is not possible for any test to show that the sequence is truly random - agreed? We can, however, test the sequence for characteristics which we would expect to see if the sequence was random.
 

nsaspook

Joined Aug 27, 2009
6,579
There are many types of random number generators. Many can be statistically random by most tests but useless for cryptography or applications that require security by numbers. For that we need a generator with special characteristics.
https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
The requirements of an ordinary PRNG are also satisfied by a cryptographically secure PRNG, but the reverse is not true. CSPRNG requirements fall into two groups: first, that they pass statistical randomness tests; and secondly, that they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.
All computer algorithm generators are actually pseudorandom in some manner. For actual 'True' randomness we need something computers can't deliver.
https://en.wikipedia.org/wiki/Random_number_generation#"True"_vs._pseudo-random_numbers

https://www.technologyreview.com/s/418445/first-evidence-that-quantum-processes-generate-truly-random-numbers/
And yet this is at odds with another of the great challenges facing modern science: understanding the nature of randomness. While information can be defined as an ordered sequence of symbols, randomness is the opposite of order, the absence of pattern. One of the basic features of true randomness is that it cannot be produced by a computer, otherwise it wouldn’t be random and that sets up a mouthwatering problem.
https://arxiv.org/pdf/1004.1521.pdf

A simple source of randomness is the startup bit state of SRAM memory.
https://arxiv.org/pdf/1902.03031.pdf
 
Last edited:

Papabravo

Joined Feb 24, 2006
12,686
If you consider the task,


How I think about this is as follows:

Each digit has a possible value of 0-9. The definition of randomness for this demonstration is that, for each digit, every possible value has an equal probability of occurrence.

It is not possible for any test to show that the sequence is truly random - agreed? We can, however, test the sequence for characteristics which we would expect to see if the sequence was random.
Ah...binary numbers use only the values 0 and 1. Decimal numbers use the numerals from the the set {0,1,2,3,4,5,6,7,8,9}.

The tough question is: "What characteristics do you propose for a sequence that is random?"
 

Thread Starter

Wendy

Joined Mar 24, 2008
21,914
This started as an exercise fighting extreme boredom. There are times I indulge in mental exercises with no expectation of going any where with it. This thread is fair game for my fellow geeks,, I will be following with interest. I will design circuits though. Another time waster for a person with way too much time one their hands.

As for the base generator it all starts with one or a zero. from there any number can be made. Girl Geeks just wanna have fun.
 
Last edited:
Ah...binary numbers use only the values 0 and 1. Decimal numbers use the numerals from the the set {0,1,2,3,4,5,6,7,8,9}.
Yes, you are quite right and I am also sure that you can generalize the binary case to a decimal case and so on...each digit, 0 or 1, has an equal probability of being chosen.

Ordinarily, I would ask the question, what do you need the sequence for? But, if you want to just be theoretical, I would throw out a question that, more or less, appears in the TS's first post and it is also how many people think about testing random numbers.

If you generate two sequences (distributions) of 10000 decimal (0-9) digits, S1 and S2, does the mean value of the two sequences have to be equivalent if they are random.

If not, how different can they be before you say that they are not random?
 

Thread Starter

Wendy

Joined Mar 24, 2008
21,914
Good old coin toss. Cryptography is made complex wanting to calculate keys on both sides of computers. Popular Electronics had an excellent article on the subject before they shut down the first time. Exclusive ORing with a random number yields a pseudo random number out. Exclusive OR it with the same random number out pops the original number. Problem is giving the receiving side the key or random binary number. If it is put on the web it defeats the point. With thumb drives and SD cards it offers interesting possibilities. Such as good old postage mailing a Gigabyte or terabyte random number key to the would be receiver.

Note I reserve the right to edit my last post without notice...
 
Last edited:
@Wendy maybe you could add this one to your list of possible circuits. I have had a copy of this circuit article in a stack of papers for more than a year with the hope/idea of rebuilding it in a more modern and single voltage version.

https://archive.org/details/byte-magazine-1981-05/page/n460

Byte magazine available at the link above. Article (Technical Forum) begins on page 452, Build a Noise-Based Random Number Generator. Give it a look sometime, it is interesting. The same basic approach (using a zener or a portion of a transistor) has appeared in many forms.
 
Good old coin toss. Cryptography is made complex wanting to calculate keys on both sides of computers. Popular Electronics ha an excellent article on the suject before they shut down the first time. Exclusive Oring with a random number yields a pseudo random number out. Problem is giving the receiving side the key or random binary number. If it is put on the web it defeats the point. With thumb drives and SD cards it offers interesting possibilities. Such as good old postage.
So, you are getting at one of the characteristics of the PRNG that you might want. Difficulty to see any information that could aid in prediction.
Something that the history of IP has been rich with...predicting packet sequence numbers...https://pdos.csail.mit.edu/~rtm/papers/117.pdf and that was in 1985.
 

djsfantasi

Joined Apr 11, 2010
5,833
I had a thread about six years ago, discussing a technique used to code a PRNG many, many years ago. Statistically, it passed the distribution test mentioned by Wendy. It was a FORTRAN IV function and used in a hashing algorithm to generate keys for a database system we were developing at the time (mid-70s).

On another note, I recently mentioned Stephen Wolfram’s “A New Kind of Science”. In it he discusses the cellular automata defined by Rule 30 and proposed it as the basis for a PRNG. He analyzed this extensively in 1985 in the context of cryptography. As cellular automata can easily be realized in a computing environment.
 

Papabravo

Joined Feb 24, 2006
12,686
Yes, you are quite right and I am also sure that you can generalize the binary case to a decimal case and so on...each digit, 0 or 1, has an equal probability of being chosen.

Ordinarily, I would ask the question, what do you need the sequence for? But, if you want to just be theoretical, I would throw out a question that, more or less, appears in the TS's first post and it is also how many people think about testing random numbers.

If you generate two sequences (distributions) of 10000 decimal (0-9) digits, S1 and S2, does the mean value of the two sequences have to be equivalent if they are random.

If not, how different can they be before you say that they are not random?
When you say "equivalent"; what exactly does that mean? Whether the sequences are random or not there is no requirement that the means of the two populations must be equal. The more sequences you generate and compute the means for, the more likely those means are going to follow a normal distribution. That is to say the means will behave like a normally distributed random variable. Just so we are clear there is some small probability that the mean of a sequence of 10,000 digits could approach 0 or 9 or any other value in the range [0,..9]
 
When you say "equivalent"; what exactly does that mean? Whether the sequences are random or not there is no requirement that the means of the two populations must be equal. The more sequences you generate and compute the means for, the more likely those means are going to follow a normal distribution. That is to say the means will behave like a normally distributed random variable. Just so we are clear there is some small probability that the mean pf a sequence of 10,000 digits could approach 0 or 9 or any other value in the range [0,..9]
OK, so the mean of S1 does not have to equal the mean of S2. How different can they be? Or, if you would like, how different can they be if they "behave like a normally distributed random variable"?
 

Papabravo

Joined Feb 24, 2006
12,686
OK, so the mean of S1 does not have to equal the mean of S2. How different can they be? Or, if you would like, how different can they be if they "behave like a normally distributed random variable"?
As I said the difference can be as large as 9. That would be extraordinarily unlikely, but still possible.
 
Maybe I should just answer my own question to avoid seeming condescending or leading or something offensive...

OK, so the mean of S1 does not have to equal the mean of S2. How different can they be? Or, if you would like, how different can they be if they "behave like a normally distributed random variable"?
One common test (for the S1, S2 example) would be a simple Student's t. This will yield a value that is associated with the probability that the two sample distributions are different. Let's say, for example, the p that they are different is .05. Do we say that are our PRNG is no good, knowing that we can expect that kind of difference (or worse) 1/20 of the time (edit to add, that is, that they both come from the same population - in this case a population of truly random digits).
 
Last edited:

Glenn Holland

Joined Dec 26, 2014
681
I knew the owner of a pinball machine broker who told me how Bally Manufacturing Co. designed and built slot machines.

Gambling devices are a classic example of a random function generator.
 
Top