3
$\begingroup$

Suppose that you has to guess given a set of numbers

  • If they are random.
  • The mathematical expectation

Is there a definition of randomness that allow this prove/test?

Is even possible? if so: How many value would be enough ?

Example:

If numbers come from a coin experiment, results could be coded as 0 or 1,

000100010110100011.....

Then how many "bits" are enough to "test" variable randomness?

According to the law of large numbers, the average of the results (adding the results and dividing by the number of trials) should become closer and closer to the expected value as more trials are performed.

But if we don't know where those numbers come from then we don't know what to expect!

What are the law of large numbers hypothesis?

Does the definition of random cointain a reference to average and to the expected value?

It is deeply confusing to me,

thanks in advance for any information

  • 0
    Random means that knowing the first $n$ terms of the sequence you cannot say anything about the $n+1$'th term at all besides that all possible combinations for that term to happen have the same probability.2011-06-22
  • 3
    If you search on testing random number generators you can find a lot of information. It is a large and complicated topic.2011-06-22
  • 1
    This is complicated topic indeed. For one thing: would you say that the digits of PI are random?2011-06-22
  • 1
    @Hernan - You might want to look up Kolmogorov complexity, which looks at randomness from a computational viewpoint.2011-06-22
  • 0
    @Ross Millikan thanks, as I see tests expects (or are aimed to) a certain distribution, it's like having a metadata about the data, as if randomness were not in a set of numbers, but in its interpretation @leonbloy it depends, if you already know numbers come from "PI" or from "a coin experiment" then that's not what I am asking about, because you have extra meta information about the data, the question is about the factibility of judge a set of data as "random", computable/non-computable random, is further discussion, but first I would like to know if e a definition of random is even possible2011-06-22
  • 0
    @Unreasonable Sin, yes there is a Kolmogorov randomness definition I am reading right now, thanks (perhaps the question itself could belongs to computational theory too)2011-06-22
  • 0
    @Unreasonable Sin if you put Kolmogorov complexity as an answer that will be the accepted one, thanks again2011-07-01

3 Answers 3

1

You may like to understand the randomness of you sequence heuristically as follows. This may help you to get more intuition.

Write favorite binary sequence you would like to test for randomness in a file and try to compress it (e.g. with zip, etc...).

Then take the ratio between the size of the compressed file and the size of the original one. If the ratio is close to 1, it means the sequence is quite random, and if the ratio is close to zero then it means that the sequence is not very random.

  • 0
    Yes this is the answer, as @Unreasonable Sin has comment, that's a Kolmogorov randomness definition, and that definition is really great, I have been reading Gregory Chaitin AIT http://en.wikipedia.org/wiki/Algorithmic_information_theory and is the deeper thing I have read about randomness2011-07-01
3

The randomness of a sequence, to use @Listing's definition, can be quantified by the entropy rate.

If the order of the numbers does not matter, you can use a statistical test for randomness.

3

I recommend reading Chapter 3.5 of Knuth, Seminumerical Algorithms (this book is Volume 2 of The Art Of Computer Programming). In fact, I recommend reading everything Knuth has ever written, but this chapter in particular, titled What is a Random Sequence, will help you clarify your concept of randomness.