Mon 31 Jul 2006
Relative Frequencies in Infinite Sets
Posted by James Beebe under general
[23] Comments
I have a question about relative frequency for the formal epistemologists out there. I would like to know whether the following claim is true, given either von Mises’ or Kolmogorov’s definitions of randomness:
(RF) The limiting frequency of positive even integers in a randomly selected sequence of positive integers is 1/2.
Richard von Mises (Probability, Statistics and Truth, 1957, 24-25) defined a random sequence to be one where the limiting value toward which the relative frequency of the attribute in question converges “remain[s] the same in all partial sequences which may be selected from the original one in an arbitrary way.” Examples of the sort of subsequences he had in mind include those formed by all odd members of the original sequence or by all members for which the place number in the sequence is the square of an integer or a prime number. The Kolmogorov-inspired definition of randomness I had in mind was the following: a sequence is random if the shortest program that can generate it is no shorter than the one that simply lists the elements of the sequence one by one.
Note that the ordinary sequence of integers (1, 2, 3, 4,…) does not qualify as random on either conception of randomness. Nor do the other sequences commonly used to illustrate the importance of ordering when defining limiting frequencies in infinite sets (e.g., those in which the evens appear at every 3rd place or every 4th place, etc.). I have no clear intuitions about whether there would be a limiting frequency of positive even integers in the case I describe or, if there were, whether it would of necessity be the commonsensical limit of 1/2. Any formal intuitions or theoretical insights?