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
    @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.