The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences (Q4650290)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2133236
Language Label Description Also known as
default for all languages
No label defined
    English
    The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences
    scientific article; zbMATH DE number 2133236

      Statements

      The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences (English)
      0 references
      0 references
      9 February 2005
      0 references
      random sequence
      0 references
      Mises-Church random sequence
      0 references
      Kolmogorov-Loveland random sequence
      0 references
      Intuitively, if we continuously flip a fair coin, then we get a (potentially) infinite binary sequence which is truly random. In traditional probability theory there is no way to say that an \textit{individual} random sequence is random, this theory only talks about properties of \textit{sets} of sequences. Clearly, for a truly random sequence, the frequency of 1s must tend to 1/2, and if we select a subsequence, then, within this subsequence, we should also get the limit frequency 1/2. In the 1920s, von Mises proposed this property -- that the limit frequency is 1/2 for all selected subsequences -- as a definition of a random sequence. In addition to selecting a fixed subsequence (like all bits at odd locations), he also allowed selecting a subsequence which follows a \textit{selecting rule} in which the location we select at the next step depends on the bits at the previously selected locations: e.g., if the first bit is 0, the next chosen bit is 2 else 4. In von Mises' scheme, the selecting rule should be \textit{monotonic} in the sense that the next selected location is always further away than all the previous locations. The original definition was not complete because it was not clear what a \textit{rule} is; when Church formalized the notion of a computable function, he proposed to restrict von Mises' idea to computable rules. Sequences for which the frequency tends to 1/2 for every subsequence obtained by a monotonic computable selection rule are called Mises-Church random. For such sequences, a computable subsequence is clearly also Mises-Church random. In the 1960s, Kolmogorov and Loveland proposed to use \textit{all} computable selection rules, not just monotonic ones. A natural question is: if a sequence is Kolmogorov-Loveland random, and we apply a nonmonotonic selection rule to it, will the resulting subsequence still be Kolmogorov-Loveland random? This has been an open problem for almost 40 years. The author solves this problem by providing an example of a resulting subsequence which is not Kolmogorov-Loveland random. Many previously known counterexamples can now be easily deduced as corollaries of this result: e.g., the fact that not every Mises-Church random sequence is Kolmogorov-Loveland random.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references