1
$\begingroup$
  1. Imagine the following experiment: someone is sitting behind the screen and calls out a sequence of numbers: "1! 3! 5! 3! 4! ...". Let's say he/she and I agreed beforehand that all numbers are integers from 1 to 6. Can I find out if to generate these numbers he/she is using a truly random process (like throwing an ideal die or performing quantum-mechanical experiment) or he/she just has a sophisticated pseudo-random algorithm?
    Note, that we haven't agreed about a particular probability distribution, so it is up to my opponent to choose it. Therefore I can't use $\chi^2$-test (or can I?).

  2. A related question, because I expect the answer to the first one is "No". Imagine the same setup as above, but now it is me who chooses the probability distribution. Are there any distribution such that my opponent wouldn't be able to deduce a pseudo-random algorithm to mimic it. Or it will be very hard (slow convergence)?

$\endgroup$
  • $\begingroup$ Are we at least to assume that the numbers generated (if random) are independent and of the same distribution? $\endgroup$ – Hagen von Eitzen Jun 24 '15 at 15:37
  • $\begingroup$ Of the same distribution - yes. Independent - yes and no :) - what will be the difference between the two situations? $\endgroup$ – xaxa Jun 24 '15 at 15:39
  • $\begingroup$ A $\chi^2$ test would be a test about what distribution is being used if you can already assume randomness, but it would be useless in checking if a sequence is actually random. For example, you could check if a distribution is uniform over {1, 2, ... , 6}, but then the sequence 1, 2, 3, 4, 5, 6, 1, 2, 3, ... is perfectly consistent with this distribution while being entirely non-random. $\endgroup$ – dsaxton Jun 24 '15 at 19:03
  • $\begingroup$ Also, it seems to me that deciding whether or not a sequence is random is something that should be provably impossible in general. That would basically amount to saying that no deterministic process generated the sequence, but if you have a finite sequence how do you know it wasn't generated by an algorithm that just repeats that sequence ad infinitum? $\endgroup$ – dsaxton Jun 24 '15 at 19:06
  • $\begingroup$ @dsaxton good point! It seems then that there is actually no way to define "randomness" for any finite sequence... $\endgroup$ – xaxa Jun 24 '15 at 19:51
2
$\begingroup$

See e.g. Cryptographically secure pseudorandom number generator. A high-quality pseudorandom generator will be extremely difficult to distinguish from random. However, in principle, if you are lucky enough to guess which algorithm your opponent is using (including the size of the seed), and have a lot of time on your hands, you could try all possible seeds, and after observing enough output you could tell which seed is being used and then be able to predict with certainty the output from then on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.