Kybernetika 28 no. 5, 383-391, 1992

On pseudo-random sequences and their relation to a class of stochastical laws

Ivan Kramosil and Jan Šindelář

Abstract:

A finite sequence is complex in the sense of Kolmogorov complexity approach if the length of its shortest generating program is greater than a prescribed lower bound. Infinite sequences, almost all initial segments of which are complex in this sense with lower bounds depending on the length of these segments, will be investigated in this paper. The case of interest is that one when such an infinite sequence satisfies some stochastical law depending on a function defining the lower bounds in question. Having a finite or countable collection of stochastical laws and corresponding collection of functions defining lower bounds one could be interested whether there is some other function defining lower bounds and characterizing, in a sense, simultaneously all stochastical laws from the given collection. Existence of such a function is proved and its properties are analyzed. The case of constructive functions defining lower bounds is investigated as well.

Classification:

03D15, 60A99, 68Q30