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

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Listing Jun 22 '11 at 19:38
  • 3
    $\begingroup$ If you search on testing random number generators you can find a lot of information. It is a large and complicated topic. $\endgroup$ – Ross Millikan Jun 22 '11 at 20:14
  • 1
    $\begingroup$ This is complicated topic indeed. For one thing: would you say that the digits of PI are random? $\endgroup$ – leonbloy Jun 22 '11 at 20:22
  • 1
    $\begingroup$ @Hernan - You might want to look up Kolmogorov complexity, which looks at randomness from a computational viewpoint. $\endgroup$ – Unreasonable Sin Jun 22 '11 at 20:44
  • $\begingroup$ @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 possible $\endgroup$ – Hernán Eche Jun 22 '11 at 20:52
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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 en.wikipedia.org/wiki/Algorithmic_information_theory and is the deeper thing I have read about randomness $\endgroup$ – Hernán Eche Jul 1 '11 at 19:43
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

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.

|cite|improve this answer
$\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.