Some properties of random number generators (Q1175846)

Consider some properties and characteristics of a binary words sequence generated by a pseudorandom number generator. The authors show in the framework of algorithmic probability theory that there exists a formal algorithm that generates a sequence \(\{x^ n\}\) of binary words (such that the limit of word lengths is infinity) which converges in a certain sense to the sequence \(\omega^ 1\). Note that the proposed algorithm does not compute fragments of the limiting sequence and suffers from some indeterminacy properties. The sequence \(\omega^ 1\) is defined inductively. The proof of the existence theorem utilizes Martin-Löf's construction and the method of cutting unnecessary branches in the tree of binary words. From the point of view of applied statistics the conditions imposed on random number generators are represented.