2
$\begingroup$

Let's suppose to have sequence like "10 1 2 4 5 3 2 1 2 3 10 1" and so on... It is possible to understand if it has been generated randomly (by a program) or by a human? Do they correspond to a kind of distribution?

$\endgroup$
4
  • 1
    $\begingroup$ Try stackexchange math it's a better for you $\endgroup$ Jun 3, 2017 at 22:37
  • $\begingroup$ There's a curious phenomenon, the name of which I can't recall, that can be used to detect when someone has cooked the books. Real financial data and transactions exhibit a different pattern than a human tends to create. The leading digit in particular, as I recall, tends be significantly less randomly distributed than might be expected. $\endgroup$ Jun 4, 2017 at 0:13
  • 3
    $\begingroup$ @zibadawatimmy You seem to be referring to Benford's law, en.wikipedia.org/wiki/Benford%27s_law. $\endgroup$ Jun 4, 2017 at 0:16
  • 3
    $\begingroup$ Although the question might indeed be posed in a naive way, there is an underlying very-substantial issue here... as in @JoelDavidHamkins' answer below, and also mine... $\endgroup$ Jun 4, 2017 at 0:27

3 Answers 3

6
$\begingroup$

Despite the comments, your question sits at the entryway to what has become an exciting new field of research.

In classical probability theory, if one were to flip a coin a certain number of times, then any two particular patterns of flips would be equally likely, and so in this sense, it doesn't make sense to say that one sequence is more random than another, or that any particular sequence is "random."

Yet, we seem to have an intuitive sense that some sequences look more random than others.

The subject known as algorithm randomness (see also Algorithmic Randomness and Complexity, Downey, Rodney G., Hirschfeldt, Denis R.) aims to give legs to that intuition, by identifying various criteria of randomness that a particular (infinite) sequence may or may not exhibit.

For example, an infinite binary sequence is said to be generic, if it is a member of every computable co-meager set. A sequence is random, if it is an element of every suitably computable measure-one set. And so on for many notions of randomness that have been proposed. The subject is concerned with sorting out the relations between these various randomness notions.

$\endgroup$
4
$\begingroup$

Recapping some aspects of @Joel David Hamkins' answer: "probability" by itself is not enough to explain "randomness", as it turns out. After all, all possible sequences of 100 heads-or-tails are equally likely, but some would be more suspect of being due to an unfair coin or other human intervention. To my perception, the issue is not about probability, but about "complexity" (e.g., Kolmogorov-Solomonov-Chaitin notions...).

An approximation to what "complexity" is about can be modeled by "compressibility", namely, if a thing admits a description much smaller than itself, it is not "random". Of course, the notion of "description" is context dependent, etc. But at least the intuitive notion of this seems (to me) to exactly address the true notion of "randomness".

So, if a file is not compressible by the standard compression algorithms, it is likely that it is either already compressed or is well-encrypted, for example. Indeed, one might appraise the quality of an encryption scheme by trying to compress the ciphertext: if it does not compress well, it is (at a low level) perceived as "random", which is desirable.

$\endgroup$
1
$\begingroup$

If you know the distribution of the random number generator, you can compute the p-value of your sequence for the Kolmogorov-Smirnov test on that distribution (e.g., ks.test on R). The closer the p-value is to 1, the more likely the data is from a generator. If you don't know the distribution but do know that the generator is independent across elements, you can compute the p-value for that assumption (e.g., Pinkse, 1998; Kulperger and Lockhart, 1998; Ghoudi and Kulperger, 2001). Basically, if you know any other characteristics of the generator, you can compute the p-value for those characteristics.

Alternatively, if you have tons of example sequences created by humans and generators, you can make a neural network learn to distinguish them (e.g., with Tensorflow on Python).

$\endgroup$
2
  • 1
    $\begingroup$ I'm not sure the K-S test does what you want. My understanding is that it only tests a sequence of values, and the ordering of the values doesn't matter. So for instance it would say the sequence 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 was likely generated by a random uniform 1-10 generator. $\endgroup$
    – Will Sawin
    Jun 4, 2017 at 0:15
  • $\begingroup$ Good point. If you do not consider the sorted array to be generated randomly but rather by a human, then the K-S test does not work. My unexplained assumption here was that a "human-generated" sequence (whatever that means) should not satisfy what you know about the random generator. If this is the case, the K-S still works. $\endgroup$
    – user108
    Jun 4, 2017 at 6:18

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