DennisN said:
How the analyzing could be done? By using
Information Theory.
DennisN said:
a pseudo-random process can be identified by analyzing sufficiently long output sequences of the process.
This was fun to think about, so I've thought some more, and this is how I think it could be done:
Setup
We have two processes which will function as number generators, which then will produce long sequences of numbers which we later will perform statistical and information theoretical analyses on. The first sequence is produced by a quantum mechanical process, and the hypothesis Q is that this process is purely random due to quantum mechanics, so I call this sequence R. The second sequence is produced by a digital computer and is thus a pseudorandom process, and I call this sequence P.
For simplicity I choose the base 2 (binary) for the two sequences, which means we don't have to convert back and forth between bases when we talk about them.
R can be produced by any quantum mechanical process that has two outcomes with the equal probability 0.5.
As an example, assume we have a Stern–Gerlach apparatus with detects the spin of an atom in a vertical direction. If spin down is detected, this generates a 0 in the R sequence, and if spin up is detected, this instead generates a 1 in the R sequence. When n number of atoms have been analyzed we have a R sequence of length n.
P is produced by a reasonably good pseudorandom generator which outputs 0 or 1 with the equal probability 0.5, and we generate n numbers of bits in the P sequence.
Analysis
1. Repetition detection.
An algorithm which detects repetitive sequences of length r << n, analyzes the two sequences R and P. If our hypothesis Q is correct, the algorithm will detect a repetitive sequence in P of length r and never detect a repetitive sequence in R.
2. Information entropy
The maximum information entropy [itex]H[/itex] of a random (or pseudorandom) variable of base 2 is 1, so
[itex]0 < H(R) ≤ 1[/itex]
and
[itex]0 < H(P) ≤ 1[/itex]
(see e.g.
Information entropy - example)
Furthermore, if our hypothesis Q is correct, the information entropy of sequence P will be smaller than the information entropy of sequence R, so
[itex]H(P) < H(R)[/itex]
and together we get
[itex]0 < H(P) < H(R) ≤ 1[/itex]
Edit:
Also, if our hypothesis Q is correct, the information entropy of a sufficiently long sequence R should be very close to 1. More accurately, [itex]H(R)[/itex] should approach 1 when longer and longer sequences are analyzed.