References for Randomness & Pseudorandomness

[svrphy]

I wish to understand something about randomness and Pseudorandomness. In particular, given a set of "seemingly-random" numbers, what can one do to analyse as to whether they are randomly generated numbers or just a pseudorandom sequence.
Can somebody point me to Good, pedagogical Referances in this regard.
(Books, online tutorials etc .. . )
P.S : something which is not too CS theory, but just makes you able to appreciate the difference well and apply the ideas might be highly appreciated.

 

[statdad]

"whether they are randomly generated numbers or just a pseudorandom sequence."

Technically any sequence you generate is pseudorandom.

 

[svrphy]

a) if it is, what kinds of tests will help demonstrate that ?
b) not all sequences generated are pseudorandom. Those generated by nuclear decay or similar quantum effects can be considered to be truly random.

 

[statdad]

"not all sequences generated are pseudorandom. Those generated by nuclear decay or similar quantum effects can be considered to be truly random."

The latter are not generated by any mechanism we create.

 

[hobbyist]

there is no difference, except that for pseudorandomness one with generator knowledge can predict the next value, for "truly random" nobody knows the generator.

 

[Kostas Tzim]

What pseudorandomness truly mean? What i want to tell is that with better technology there would be no random. Isn't randomnsess an invention of human? Are the quantum effects something to prove that random exists, or again the effects seem to be random due to our limited possibilities of our understanding? I'm a student by the way, sorry fopr interrupting, my math and physics knowledge haven't reached the level i want, yet

 

[Pejeu]

Well, intuitively, you'd want to check the frequency with which each value comes up as well as the range within which values come up, their average (which, after a long enough sequence, should tend toward the middle of the interval within which values come up) as well as their mean (which should tend to be equal to the average).

Additionally, for long sequences, you'd also want to check that multiples of two come up 50% of the time while multiples of three come up 33% of the time, multiples of 5 come up 20% of the time, multiples of 7 come up 14% of the time and so on.

Those are just basic, obvious evaluations you'd need to run.

 

[Aufbauwerk 2045]

I wish to understand something about randomness and Pseudorandomness. In particular, given a set of "seemingly-random" numbers, what can one do to analyse as to whether they are randomly generated numbers or just a pseudorandom sequence.
Can somebody point me to Good, pedagogical Referances in this regard.
(Books, online tutorials etc .. . )
P.S : something which is not too CS theory, but just makes you able to appreciate the difference well and apply the ideas might be highly appreciated.

I have a similar question. I think it is hardly a new question. Yet I have never found an answer which satisfies me.

Consider the following experiment. I am provided with a set of random number sequences. For example, I may be given 100 different sequences. I am told the following. Some of the sequences are "random" in the sense of coming from some natural process. The other sequences are each generated by some unspecified software random number generator and are hence "pseudo-random".

My job is to identify which of the sequences are random and which are pseudo-random. I must do this by applying some type of mathematical test.

Suppose I apply some tests for randomness and I can't detect which sequences are random and which are pseudo-random.

In that case should we apply Occam's Razor and say there is only one type of sequence? We understand how to generate pseudo-random numbers using a deterministic algorithm so we know such a sequence exists. How do we prove that the so-called "random" numbers are not generated by some deterministic algorithm used by nature which we do not understand? In other words, if we knew the initial conditions and the algorithm, and had the computational power, we could compute exactly what the random sequences would be.

Or is there a mathematical test which infallibly detects whether a sequence is random or pseudo-random? Or is there at least a test which does a fairly good job, even if it is not infallible?

Of course some may say "but we know that random sequences are generated by nature, therefore they are not pseudo-random." That argument does not satisfy me. It seems simpler to me to say that nature is running a deterministic algorithm which generates "pseudo-random" numbers but it is so complicated we can't figure it out.

 

[Svein]

Suppose I apply some tests for randomness and I can't detect which sequences are random and which are pseudo-random.

A pseudo-random sequence is usually characterized by

• The sequence eventually repeats (but it may take a long time to do so).
  
• One value (usually 0) is excluded.

The simplest pseudo-random value generator consists of a shift register and set of exclusive-or gates (LFSR). See https://www.maximintegrated.com/en/app-notes/index.mvp/id/4400.

 

[FactChecker]

In a pseudorandom sequence, you can sometimes see autocorrelations at particular lags when you apply Box-Jenkins time series analysis. As far as I know, that is the most sensitive test to try. If it doesn't show up there, I don't know if there is any better test. On the other hand, if it doesn't show up there, it is probably good enough for any realistic application.

In this discussion, I think you should specify that a time series of recorded data from a truly random process will be considered random, even if it is replayed later.

 

[jbriggs444]

Or is there a mathematical test which infallibly detects whether a sequence is random or pseudo-random? Or is there at least a test which does a fairly good job, even if it is not infallible?

For every finite sequence, there is a deterministic generator that generates that sequence. It follows that there is no possibility of an infallible detector.

Edit: It is also true that for every finite sequence generated by a deterministic generator, there is a finite probability that a random process would produce the identical sequence. This puts a bound on the maximum possible reliability of a randomness detector.

Edit: For an infinite sequence; a diagonalization argument demonstrates the existence of a deterministic generator which would defeat any given purported infallible detector.

 

[FactChecker]

My job is to identify which of the sequences are random and which are pseudo-random. I must do this by applying some type of mathematical test.

Not possible. The point of pseudo-random is to pass these tests. Some are better than others. There is no test that will catch them all and if there was, it would be possible to make a series that will fool the test.

Or is there a mathematical test which infallibly detects whether a sequence is random or pseudo-random? Or is there at least a test which does a fairly good job, even if it is not infallible?

The short answer is no. The most sensitive test that I know is to apply Box-Jenkins time series analysis and look for significant patterns. But there is a serious risk that a random series would have some type of pattern just by chance.