References for Randomness & Pseudorandomness

In summary, there are various tests that can be applied to determine whether a sequence of numbers is truly random or just a pseudorandom sequence generated by an algorithm. These tests can include checking for frequency and range of values, as well as applying time series analysis techniques. However, there is no infallible test and it is possible for a truly random sequence to be generated by a deterministic process.
  • #1
19
0
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.
 
Mathematics news on Phys.org
  • #2
"whether they are randomly generated numbers or just a pseudorandom sequence."

Technically any sequence you generate is pseudorandom.
 
  • #3
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.
 
  • #4
"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.
 
  • #5
there is no difference, except that for pseudorandomness one with generator knowledge can predict the next value, for "truly random" nobody knows the generator.
 
  • #6
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
 
  • #7
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.
 
  • #8
svrphy said:
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.
 
Last edited by a moderator:
  • #9
David Reeves said:
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.
 
  • #10
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.
 
  • #11
David Reeves said:
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.
 
  • Like
Likes FactChecker
  • #12
David Reeves said:
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.
 
  • Like
Likes jbriggs444

1. What is randomness?

Randomness refers to a lack of pattern or predictability in a sequence of events. In other words, it is the quality of being unpredictable.

2. What is pseudorandomness?

Pseudorandomness refers to a sequence of numbers or events that appear to be random, but are actually generated using a deterministic algorithm. This means that while the sequence may appear random, it is actually following a specific pattern.

3. Why is randomness important in science?

Randomness is important in science because it allows for unbiased and unpredictable results. This is especially crucial in experiments and studies, as it ensures that any observed effects are not due to a predetermined pattern or bias.

4. How are random numbers generated?

Random numbers can be generated through various methods, such as using physical processes like coin flips or dice rolls, or through mathematical algorithms. These algorithms use a seed value, which is a starting point for the sequence of numbers, to produce a seemingly random sequence.

5. What is the difference between true randomness and pseudorandomness?

The main difference between true randomness and pseudorandomness is that true randomness is completely unpredictable and cannot be generated by any algorithm, while pseudorandomness is generated using a deterministic algorithm and therefore has a pattern or structure behind it.

Suggested for: References for Randomness & Pseudorandomness

Replies
4
Views
1K
Replies
2
Views
1K
Replies
1
Views
1K
Replies
24
Views
1K
Replies
7
Views
656
Replies
5
Views
176
Replies
9
Views
1K
Replies
2
Views
801
Replies
4
Views
548
Replies
37
Views
483
Back
Top