The Law of the Iterated Logarithm for p-Random Sequences
Yongge Wang · 1996
The stochastic properties of p-random sequences are studied in this paper. It is shown that the law of the iterated logarithm holds for p-random sequences. This law gives a quantitative characterization of the density of p-random sets. When combined with the invariance property of p-random sequences, this law is also useful in proving that some complexity classes have p- measure 0. 1 Introduction Random sequences were first introduced by von Mises [17] as a foundation for probability theory. Von Mises thought that random sequences were a type of disordered sequences, called "Kollektivs". The two features characterizing a Kollektiv are: the existence of limiting relative frequencies within the sequence and the invariance of these limits under the operation of an "admissible place selection". Here an admissible place selection is a procedure for selecting a subsequence of a given sequence ¸ in such a way that the decision to select a term ¸[n] does not depend on the value of ¸[n]. But ...