# Is it possible to determine if a process is random

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)?

• Are we at least to assume that the numbers generated (if random) are independent and of the same distribution? Jun 24, 2015 at 15:37
• Of the same distribution - yes. Independent - yes and no :) - what will be the difference between the two situations?
– xaxa
Jun 24, 2015 at 15:39
• 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. Jun 24, 2015 at 19:03
• 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? Jun 24, 2015 at 19:06
• @dsaxton good point! It seems then that there is actually no way to define "randomness" for any finite sequence...
– xaxa
Jun 24, 2015 at 19:51