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
9 February 2005
0 references
random sequence
0 references
Mises-Church random sequence
0 references
Kolmogorov-Loveland random sequence
0 references
0.8975971341133118
0 references
0.8614609837532043
0 references
0.8561972975730896
0 references
0.8443813920021057
0 references
0.8441283702850342
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