More on nonstandard random number generators

2013 March 11
by Daniel Lakeland

From information theory, suppose that there exists a bit stream (b_i) of nonstandard length LK such that for any nonstandard sample of M\ll L consecutive substrings of length K the sequence of MK bits has Kolmogorov complexity MK(1+\epsilon) bits in some simple restricted LISP like language, where \epsilon \cong 0. From the theory, this is near maximal complexity since every finite string has a complexity no more than some constant larger than that finite string, and our strings are finite but nonstandard.

Intuitively, we have a bit sequence which is very very long, and when we take very long samples of long bit strings, we can't compress those samples.

Such a bit stream is non-computable, and nonstandard. But does it exist? I don't know. By transfer, it would have to exist if for all standard values of L,K there is a sequence with prefix bitstring of length MK  with complexity MK+C for some constant C. So suppose it does exist. We can make a random number generator from this sequence easily, in a manner similar to what is done in a computer.

The function \xi^*(n) takes K=log_2(N)\cong \infty sequential bits starting at location nK and forms the number (b)/2^K \in [0,1) in other words interpret the bits (b) as an integer and divide by 2^K=N. This number will be a nonstandard rational number whose binary expansion has K bits (a nonstandard number of bits). The standard part of this number will in general be irrational.  The values of \xi^* all lie on a lattice whose lattice spacing is 1/N. The function \xi^*(n) is clearly a nonstandard function, but we can make it output standard values by taking the standard part of its output, then it will be a function \xi(n) = st(\xi^*(n)) : \mathbb N \rightarrow [0,1].

Now, we'd like to show that the nonstandard function \xi^* has the property of being "near-uniformly-distributed" on all micro-intervals [b,a] \subset [0,1] of sufficiently long but infinitesimal length. So we need a reasonable definition of "near-uniformly-distributed". Suppose that we take a nonstandard sample of M successive outputs of \xi^* and we count the relative frequency that the output is in any infinitesimal interval [a,b]\subset [0,1]. We require that this frequency be (b-a)(1+\eta) with \eta \cong 0. In other words, on any interval which includes a standard number of infinitesimal lattice points, we need to have near uniformity for large enough sample size M.

Suppose that \eta is positive and appreciable for some micro- interval. Then the output of the bit sequence produces numbers in that interval significantly more often than in other intervals. A compressor program for the original bitstring would be able to take advantage of this fact. In fact we could output the bitstring in chunks of length K followed by a 0 if we are going to output another chunk, or a 1 followed by the address within the micro-interval of the lattice point we're going to output. These addresses need to be of length K+\log_2(b-a) = K(1-\epsilon_K) so we save a lot of bits by knowing the micro-region we're going to output.

For M chunks of length K we could re-encode the stream as approximately M(1-(b-a)(1+\eta))(K+1) + M(b-a)(1+\eta)K(1-\epsilon_K) bits using this method. As a fraction of MK bits that's: 1-(b-a)(1+\eta) \epsilon_K. But (b-a) is infinitesimal and so we haven't saved much unless \eta is nonstandard. This shows that if we have a point mass component to the distribution that we can compress the original sequence. So we've shown that \xi(n) has a standard density on [0,1].

It'd be nice to take it further and show that this standard density is very close to uniform, perhaps I can do that or perhaps not. I'll make an effort next time.


No comments yet

Leave a Reply

Note: You can use basic XHTML in your comments. Your email address will never be published.

Subscribe to this comment feed via RSS