One of the most widely used types of pseudo-random number generator is the linear congruential sequence. These are defined by recurrence relations of the form \begin{equation}\label{eq:genrandnum_hull_dobell_01} x_{i+1} \ \equiv \ ax_{i} + c \quad (\operatorname{mod} m) \end{equation} where all the terms are non-negative integers. The usual terminology is that \(a\) is called the ‘multiplier’, \(c\) the ‘increment’ and \(m\) the ‘modulus’.
Any such sequence must be periodic since it contains at most \(m\) different numbers each of which is determined only by its predecessor. The period can therefore never exceed \(m\) but even that cannot be guaranteed. A long period is necessary but not sufficient for good pseudo-randomness, so it is important to understand the conditions that determine its length.
That is the objective of a paper published in 1962 by T. E. Hull and A. R. Dobell (Hull and Dobell, 1962). If you have read anything about the subject you have probably heard of something commonly referred to as ‘the Hull-Dobell theorem’. The paper actually presents two theorems, but it seems that only the first gets called ‘the’.
Considering them in reverse order, the second theorem is about sequences where \(c = 0\), i.e. ‘multiplicative’ ones. It makes use of some quite advanced number-theoretical concepts and even Hull and Dobell admit that:
‘The basic theorem for the multiplicative congruential methods is more complicated and more difficult than for the mixed congruential methods.’for which reason they present only a condensed proof, referring the reader to textbooks to flesh out the details.
The first theorem, on the other hand, is not so difficult, and Hull and Dobell present their proof in full. This theorem is about sequences where \(c \neq 0\), which H&D refer to as ‘mixed’. The theorem says that, in that case, a period of length \(m\) is achievable and will occur if:
\(c\) and \(m\) are coprime,
all the prime factors of \(m\) divide \(a-1\) and
if 4 divides \(m\), then 4 divides \(a-1\).
The proof, despite what H&D say, is not easy to follow, and their paper is a classic of ‘proof by intimidation’. Unpacking all the ‘it is easy to show that’s and all the ‘obviously’s took me weeks. I therefore thought I’d post my workings in case there is anyone out there who might like to see them. Maybe I might attempt the second theorem at some point in the future.
Read more