5
$\begingroup$

I have a sequence of sets of random numbers, with each set generated by an unknown random number generator. I am assuming that in the sequence, the random number generator is the same one for a certain duration, such that a few sets in a row are from the same random number generator. In essence the sequence looks like this

a1 a2 a3 b1 b2 c1 c2 c3 c4 a4 a5 b3 ...

where a, b and c are unknown random number generators. I am looking for a way to test if two sets of random numbers might be from the same random number generator with a certain level of confidence. For example test(a1, b1) = 0.0 while test(a1,a2) = 0.9

My goal is to be able to group the sets if they are from the same random number generator, such that I get a sequence like this

[a1 a2 a3] [b1 b2] [c1 c2 c3 c4] [a4 a5] [b3 ...

I am assuming that the random number generators stay the same (i.e. the seed is never changed).

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ What if the random number generator b is built just by randomly choosing whether it will generate random numbers like a or like c for any given stretch? Then I don't see how you could ever differentiate between a and b or b and c. I think it might be better to start with the case of two random number generators which are known to be distinct, so you can't have this kind of "strategy stealing". $\endgroup$
    – Steven Gubkin
    Commented Aug 1, 2012 at 13:40
  • 5
    $\begingroup$ It seems to me that if your (pseudo-)random number generators are similar enough to an actual random number generator then the answer to your question must be no. So if you want the answer to be yes, then you probably have to restrict your attention to the class of pseudo-random number generators with a certain type of flaw or limitation. Can you state precisely what this class might be? $\endgroup$
    – Trevor Wilson
    Commented Aug 1, 2012 at 13:56
  • $\begingroup$ @steven gubkin you can assume all random generators to be unique $\endgroup$
    – celine
    Commented Aug 1, 2012 at 18:28
  • $\begingroup$ @trevor wilson you can assume that these are pseudo random generators $\endgroup$
    – celine
    Commented Aug 1, 2012 at 18:30
  • $\begingroup$ @celine: "pseudo random generators" is still too big a class to do anything useful, I think. You might be able to do something with linear congruential generators. $\endgroup$
    – Robert Israel
    Commented Aug 1, 2012 at 19:31

3 Answers 3

Reset to default
5
$\begingroup$

Some non-trivial information may be acquired, especially with not-so-great pseudo-random number generators, by applying standard compression algorithms (e.g., gzip) to chunks of output. If the ratio of compressed to not-compressed are significantly different, one infers that the sources are different, etc. Obvious benchmarks can be obtained by running compression on old email (with or without headers), the output of linear congruential generators or other bad pseudo-random number generators, etc.

Improve this answer
$\endgroup$
5
$\begingroup$

If you could do that, you would be able to distinguish the output of a random number generator from a true random sequence. This is of course possible, but unless the random number generator is especially bad (as some historical generators were) it requires testing very large samples. If your generators are reasonably good, you won't be able to tell the difference.

This document describes some statistical tests known to catch some standard random number generators. See page D-5 for a list of failures.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks....reaching the conclusion that the sample is too small or that the generators are too random to determine anything is also valuable ... $\endgroup$
    – celine
    Commented Aug 1, 2012 at 18:32
  • $\begingroup$ I am a bit puzzled by the "this is of course possible" statement. Is there some algorithm which, given some large number $N$ of pseudo-random numbers, can return "pseudo" with high probability? $\endgroup$
    – Igor Rivin
    Commented Aug 1, 2012 at 19:13
  • 3
    $\begingroup$ The output of a pseudo-random generator whose state uses at most $m$ bits of memory is periodic after the first $2^m$ outputs, with period at most $2^m$, and this can be checked. $\endgroup$
    – Robert Israel
    Commented Aug 1, 2012 at 23:46
  • $\begingroup$ @Robert: Yes, and note that if the internal state was truly random it would repeat after about $2^{m/2}$ steps (birthday paradox). Most deterministic random number generators used in practice, except possibly for some very slow ones used for cryptographic applications, fail one of the many statistical tests when a huge but plausible amount of data is collected from them. $\endgroup$
    – Brendan McKay
    Commented Aug 2, 2012 at 2:29
  • $\begingroup$ @Brendan: I am well aware that most generators fail at least some of the tests. However, the "probably repeating after $2^{m/2}$ steps" statement is not so useful for $m=128,$ which is not such a big number. $\endgroup$
    – Igor Rivin
    Commented Aug 2, 2012 at 3:12
1
$\begingroup$

If you want to know whether two sequences are outputs of the same computer program with different seeds, then I doubt you can do much better than enumerating all computer programs and trying them. This can't be done in practice. Some preudo-random number generators work reasonably well with one seed, and terribly with other seeds, which means the same algorithm with different seeds can produce either a sequence which looks random or Bach's suites for solo cello.

Perhaps you want the idea of a randomness test, such as Marsaglia's Diehard tests. The reason there are so many, including many silly tests, is that pseudo-random numbers which appear uniform often fail catastrophically when they are used to generate a sequence of pseudo-random numbers.

Another possible interpretation is to say that you have a particular distribution, perhaps the uniform distribution. You can test whether a sample is consistent with that distribution, e.g., with the Pearson chi-squared test. If you have two samples, you can estimate a distribution from the first sample and test whether the second sample is consistent with this. Since you talk about identifying when you switch from one generator to another in a sequence, you may want to look at what is called "structural change" or "change points" in statistics. There are automated tests for this which assume that the generators are not even uniform.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .