CODEWITHSUNDEEP
mathrandom
templatetypedef
templatetypedef

Reputation: 372972

Quantifying the non-randomness of a specialized random generator?

I just read this interesting question about a random number generator that never generates the same value three consecutive times. This clearly makes the random number generator different from a standard uniform random number generator, but I'm not sure how to quantitatively describe how this generator differs from a generator that didn't have this property.

Suppose that you handed me two random number generators, R and S, where R is a true random number generator and S is a true random number generator that has been modified to never produce the same value three consecutive times. If you didn't tell me which one was R or S, the only way I can think of to detect this would be to run the generators until one of them produced the same value three consecutive times.

My question is - is there a better algorithm for telling the two generators apart? Does the restriction of not producing the same number three times somehow affect the observable behavior of the generator in a way other than preventing three of the same value from coming up in a row?

Upvotes: 9

Views: 165

Answers (4)

Xodarap
Xodarap

Reputation: 11849

As a consequence of Rice's Theorem, there is no way to tell which is which.

Proof: Let L be the output of the normal RNG. Let L' be L, but with all sequences of length >= 3 removed. Some TMs recognize L', but some do not. Therefore, by Rice's theorem, determining if a TM accepts L' is not decidable.

As others have noted, you may be able to make an assertion like "It has run for N steps without repeating three times", but you can never make the leap to "it will never repeat a digit three times." More appropriately, there exists at least one machine for which you can't determine whether or not it meets this criterion.

Caveat: if you had a truly random generator (e.g. nuclear decay), it is possible that Rice's theorem would not apply. My intuition is that the theorem still holds for these machines, but I've never heard it discussed.

EDIT: a secondary proof. Suppose P(X) determines with high probability whether or not X accepts L'. We can construct an (infinite number of) programs F like:

F(x): if x(F), then don't accept L'
      else, accept L'

P cannot determine the behavior of F(P). Moreover, say P correctly predicts the behavior of G. We can construct:

F'(x): if x(F'), then don't accept L'
       else, run G(x)

So for every good case, there must exist at least one bad case.

Upvotes: 2

Nthalk
Nthalk

Reputation: 3833

Probably use ENT ( http://fourmilab.ch/random/ )

Upvotes: 0

PengOne
PengOne

Reputation: 48398

If S is defined by rejecting from R, then a sequence produced by S will be a subsequence of the sequence produced by R. For example, taking a simple random variable X with equal probability of being 1 or 0, you would have:

R = 0 1 1 0 0 0 1 0 1
S = 0 1 1 0 0 1 0 1

The only real way to differentiate these two is to look for streaks. If you are generating binary numbers, then streaks are incredibly common (so much so that one can almost always differentiate between a random 100 digit sequence and one that a student writes down trying to be random). If the numbers are taken from [0,1] uniformly, then streaks are far less common.

It's an easy exercise in probability to calculate the chance of three consecutive numbers being equal once you know the distribution, or even better, the expected number of numbers needed until the probability of three consecutive equal numbers is greater than p for your favourite choice of p.

Upvotes: 2

Howard
Howard

Reputation: 39207

Since you defined that they only differ with respect to that specific property there is no better algorithm to distinguish those two.

If you do triples of randum values of course the generator S will produce all other triples slightly more often than R in order to compensate the missing triples (X,X,X). But to get a significant result you'd need much more data than it will cost you to find any value three consecutive times the first time.

Upvotes: 1

Related Questions