Now that you've seen the pretty pictures in the previous post, it should be intuitively clear how many bits of information are lost when one iterates a uniformally distributed random number through a Marsaglia oscillator an infinite number of times (and, I think, at most twice). In simple terms, we lose the dark region shown in the images. How many bits is that worth?
Consider S, the seed of cycle 2:
S=((A-1)*(2^N))+((2^N)-1)
Recall that S iterates back to itself. I strongly suspect that every integer greater than S is in the dark region. It seems intuitive if not obvious, and agrees with my observations, but I admit that I don't have a proof. [EDIT: Now I do.] This all looks to be quite simple, but perhaps we have another Riemann Hypothesis on our hands. (I doubt it, but arrogance makes fools of mathematicians.)
If you accept this, then it's easy to calculate the average information loss L, in bits, of starting with a randomly chosen seed (x, c) and then iterating the oscillator until it hits a limit cycle (including the trivial cycles 1 and 2):
L=log2((all possible seeds)/(all residual seeds))
L=log2(2^(2N))-log2(S+1)
L=2N-log2(A*(2^N))
L=N-log2(A)
To the extent that (2^(N-1)) <= A < (2^N), then we have 0 < L <= 1. Since L is independent of N, this means that we can render the loss negligible by setting N sufficiently large. All this seems to be a reasonable compromise in light of the apparent quality of randomness provided.
No comments:
Post a Comment