Re: Challenge: Detecting sequences.

[davies]

Is the given period a Mersenne prime (if it's prime, it is a Mersenne prime) or a multiple of several small other primes?

If it is prime and any two numbers in the entire sequence are different, the prime is the period. Take two non-random sets of numbers. The first is 1, 2, 1 and the second 1, 2, 1, 2, 1. Even though these are apparently the same, they will give different sequences. The fifth number from the first set will be 2 and from the second 1. Compare this with non-prime sequences (1, 2 and 1, 2, 1, 2). The period of both of these is 2.

Next, let's imagine that the number generator uses two sets of numbers, drawing one alternately from each set. If the first two sets are used, the period will be 15 because both sets will have to reach the end at the same time before the sequence repeats.

Now, what is interesting is that using the second pair of sets in the way I have described gives a period of 4, not 2. But that isn't guaranteed. So if the period given is simply the lowest common multiple of the periods of the various PRNGs of shorter period, it might be more correct to say that the period is AT LEAST the number given. Alternatively, they might have been able to look at it in the same way as my second two sets of numbers, but if that is the case I'm afraid that the best explanation I can give is "they used maths".

Note that throughout this, I have not been testing for randomness but for period length. If you're testing a single prime sequence of this length for randomness you have to use sampling. But if you're testing a number of smaller sequences, each can be tested in its entirety using things like runs tests and chi squared. Note also that I am not a mathematician, so if anyone wants to tear my argument to pieces, I'd be very interested. I did check this logic with a mathematician once and he said that it was correct (a) if I remember what he said correctly and (b) if I explained it correctly. We'd both had a few beers.

Regards,

John Davies

Update: I think the period of my sequence based on the 3 and 5 period sequences is actually 30, not 15. This is because it needs to be multiplied by the number of sequences. But I'll check when I don't need my bed so badly. This might explain why the 2 and 4 number sequences give a combined period of 4.

[BrowserUk]

Is the given period a Mersenne prime

Yes (and thank you for your response). But ...

The value appears to be derived from the fact that the MT retains (and twists) 19937 bits of state: 624 x 32-bit words; of which 31-bits (which move with each iteration) are ignored.

I've read and re-read the descriptions of the MT (and its "proven" capabilities) many times over the years; but the process by which a periodicity of ~4e6001 can be proven escapes me. The various descriptions of the underlying basis of the proof -- a mechanism termed: inversive decimation -- go way over my head.

I was hoping, that the first part of my challenge would elicit a layman's description of it, but it seems that large numbers of the (self-proclaimed) mathematicians around here are only such in the same sense as my 9 y/o niece is a violin virtuoso. She can read the notion and play all (within the limitations of her small hands) the notes in time with the metronome, but she is neither Stephane Grappelli nor Yehudi Menuhin.

The second part of my challenge was actually of most interest to me. I suspect that the use of a Rabin–Karp style rolling checksum might be a practical approach for sequences up to say 1 or 2 billion in length; but I can't see an algorithmic approach that will get much beyond that in a realistic amount of time.

Hence the first part of my question. I was hoping that if I understood inversive decimation, it might be applicable to the non-deterministic generator I am playing with; but it seems (from the further reading I've done thanks to the links posted in this thread) that ID is only possible due to the special nature of the Mersenne prime bits of state.