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.

 

Comments are closed.