I'm looking for informations about randomness and especially - random numbers. I found some about random number generators, but for now, the question, that concerns me is how statistically differ truly random and pseudorandom strings. For example, if I have 2 strings consisiting of 0 and 1, how can I find that one is generated by pseudorandom number generator and the other by truly RNG?
If someone could explain or find a url to useful info, I would appreciate it. Sorry if answer is easy to find but I'm not such good google user.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
This is a very broad area.
Statistical tests can only rule out strings on the basis that they are "statistically unlikely to have been generated by a true random generator". Some keywords are NIST Tests, DieHard tests. Look at the Crypto and/or Theoretical Computer Science stackexchange sites and there will be posts tagged randomness or randomness testing.
Clearly if the sequence has patterns, is compressible, is predictable, then there is a problem. In cryptographic applications, the issue of efficient testing also comes in, since if the test for ruling out randomness is exponential in complexity, then that test is not feasible anyway. Sometimes an assumption such as "factoring is computationally hard" is used to design generators where predicting the generator is equivalent to factoring a product of two very large primes, these days, each prime would be about 2000 bits in bitlength. Look under Blum Blum Shub for an example.
By the way, algorithmic randomness or Kolmogorov Complexity is a totally different approach, based on minimum program length for a Turing machine that would generate the string and halt. This quantity, unfortunately, is uncomputable in general.
-
$\begingroup$ Very nice answer! I would like to add : If too many tests are made with some concrete sequence, there is a high chance that the sequence fails some test, even it is truely random. So, careful analysis is needed rather than making tests and declare the sequence to be not random, if it has not passed some test. $\endgroup$– PeterCommented May 21, 2015 at 12:55
-
$\begingroup$ And it is even more difficult to be very sure that the sequence is random (a proof is virtually impossible, excluding very small sequences). So any conclusion is quite vague. $\endgroup$– PeterCommented May 21, 2015 at 13:02
-
$\begingroup$ @Peter, thanks, I should have made that clearer, left it implied. $\endgroup$– kodluCommented May 21, 2015 at 13:05
-
$\begingroup$ Thank you, I hope that it will be helpful. Meanwhile, I've someone told me, that maybe I should look for something with ergodicity, is that a good hint? I've never had to deal with ergodic theory, the name scares me a little... $\endgroup$ Commented May 21, 2015 at 16:17