How can you calculate the probability distribution of the period length of a linear congruential generator? That is $X_{n+1} = (aX_n + c) \bmod m$ where $a$ is chosen uniformly at random from $\{1,\dots, m-1\}$ and $c$ is chosen uniformly at random from $\{0,\dots, m-1\}$ and $m$ is a fixed prime. Take $X_0$ to be some arbitrary value from $\{0,\dots, m-1\}$.

If it is hard to do exactly, is it possible to give good bounds for the cdf?


This may not address the question exactly, but the results derived indicate that the final answer may depend on the factors common to $a-1$ and $m$.

A preliminary lemma and theorem

Lemma: Suppose $p$ is prime and $j\ge2$. Then, unless $p=j=2$, $$ p^k\,|\,n\implies\left.p^{k-j+2}\,\middle|\,\binom{n}{j}\right.\tag{1} $$ Furthermore, $$ 2^k\,|\,n\implies\left.2^{k-1}\,\middle|\,\binom{n}{2}\right.\tag{2} $$

Proof: Unless $p=j=2$, $j\lt p^{j-1}$. Thus, $j$ has at most $j-2$ factors of $p$. Then $(1)$ follows from the binomial identity $$ \binom{n}{j} = \frac nj\binom{n-1}{j-1} $$ $(2)$ follows from $$ \binom{n}{2}=\frac n2(n-1) $$ $\square$

Theorem: Suppose that $$ \begin{align} &\text{(a) for all primes $p$, }p\mid m\implies p\mid a-1\\ &\text{(b) }4\mid m\implies4\mid a-1 \end{align} $$ Then, $$ \left.m\,\middle|\,\frac{a^n-1}{a-1}\right.\implies m\,|\,n $$

Proof: Assume $\left.m\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. For simplicity of notation, let $r=a-1$. Then $$ \frac{a^n-1}{a-1}=\sum_{j=1}^n\binom{n}{j}r^{j-1}\tag{3} $$ For any odd $p\,|\,m$, assume that $p^k\,|\,n$ and $\left.p^{k+1}\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Using $(3)$, we get $$ n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{p^{k+1}}\tag{4} $$ The Lemma and the assumption that $p\,|\,m\implies p\,|\,r$ says that $p^{k-j+2}p^{j-1}=p^{k+1}$ divides each term in $(4)$. Thus, $p^{k+1}\,|\,n$. Bootstrapping, we get that for any odd $p\,|\,m$, $$ \left.p^k\,\middle|\,\frac{a^n-1}{a-1}\right.\implies p^k\,|\,n\tag{5} $$ If $2\,|\,m$, then $\left.2\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Using $(3)$, we get $$ n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{2}\tag{6} $$ The assumption that $p\,|\,m\implies p\,|\,r$ says that $2$ divides each term in $(6)$. Thus, $2\,|\,n$; that is, $$ \left.2\,\middle|\,\frac{a^n-1}{a-1}\right.\implies2\,|\,n\tag{7} $$ If $4\,|\,m$, then assume that $2^k\,|\,n$ and that $\left.2^{k+1}\,\middle|\,\dfrac{a^n-1}{a-1}\right.$. Using $(3)$, we get $$ n\equiv-\sum_{j=2}^n\binom{n}{j}r^{j-1}\pmod{2^{k+1}}\tag{8} $$ The Lemma and the assumption that $4\,|\,m\implies4\,|\,r$ says that $2^{k-j+1}4^{j-1}=2^{k+j-1}$ divides each term in $(8)$. Since $j\ge2$, we have $2^{k+1}\,|\,n$. Bootstrapping, we get that $$ \left.2^k\,\middle|\,\frac{a^n-1}{a-1}\right.\implies 2^k\,|\,n\tag{9} $$ $(5)$ and either $(7)$ or $(9)$ show that $$ \left.m\,\middle|\,\frac{a^n-1}{a-1}\right.\implies m\,|\,n\tag{10} $$ $\square$

Suppose the sequence $x_k$ is defined by the recurrence $$ x_{k+1}=ax_k+b\tag{11} $$ then, inductively, we have $$ x_k=a^kx_0+\frac{a^k-1}{a-1}b\tag{12} $$ Multiplying by $a-1$ and adding $1$ yields $$ \frac{a^{k_1}-1}{a-1}\equiv\frac{a^{k_2}-1}{a-1}\pmod{m}\implies a^{k_1}\equiv a^{k_2}\pmod{m}\tag{13} $$ Therefore, to investigate the periodicity of $x_k$, we look at the periodicity of $\dfrac{a^k-1}{a-1}\bmod{m}$.

To maximize the range of $x_k$ ,we will assume that $(a,m)=(b,m)=1$. This implies $$ \begin{align} \frac{a^{k_1}-1}{a-1}\equiv\dfrac{a^{k_2}-1}{a-1}\pmod{m} &\implies\frac{a^{k_1-k_2}-1}{a-1}a^{k_2}\equiv0\pmod{m}\\[6pt] &\implies\frac{a^{k_1-k_2}-1}{a-1}\equiv0\pmod{m}\tag{14} \end{align} $$ That is, the period of $x_k$ is the smallest positive $n$ for which $$ \frac{a^n-1}{a-1}\equiv0\pmod{m}\tag{15} $$ By the theorem above, $m\,|\,n$ and since there are only $m$ residue classes $\bmod{\,m}$, we must have $n=m$. Thus,

Theorem: Suppose $$ \begin{align} &\text{(a) for all primes $p$, }p\mid m\implies p\mid a-1\\ &\text{(b) }4\mid m\implies4\mid a-1\\ &\text{(c) }\gcd(b,m)=1 \end{align} $$ Then the modular sequence defined by $$ x_{n+1}\equiv ax_n+b\pmod{m} $$ has period $m$.


There's not much of a distribution there. The period is $1$ if $a=1$ and $c=0$ or if $a\ne1$ and $X_0=c/(1-a)$; otherwise it's $m-1$.

  • $\begingroup$ Is $c/(1-a)$ uniformly distributed? $\endgroup$ – ArtM Nov 27 '12 at 13:32
  • $\begingroup$ @ArtM: Yes, it's just $(1-a)^{-1}$ times $c$, so it takes all $m$ values as $c$ ranges over all $m$ values. $\endgroup$ – joriki Nov 27 '12 at 13:42
  • $\begingroup$ @ArtM: You're welcome! $\endgroup$ – joriki Nov 27 '12 at 14:01
  • $\begingroup$ @ArtM: Sorry, there was a mistake; the period is otherwise $m-1$, not $m$. $\endgroup$ – joriki Nov 27 '12 at 14:59
  • $\begingroup$ @joriki, how about $a=6$, $c=3$, $m=7$ and $X_0 = 1$. This has period $2$ doesn't it? I.e. the sequence $1,2,1,2,1,\dots$. $\endgroup$ – Raphael Nov 27 '12 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.