Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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$.

share|improve this answer

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$.

share|improve this answer
    
Is $c/(1-a)$ uniformly distributed? –  ArtM Nov 27 '12 at 13:32
    
@ArtM: Yes, it's just $(1-a)^{-1}$ times $c$, so it takes all $m$ values as $c$ ranges over all $m$ values. –  joriki Nov 27 '12 at 13:42
    
Thanks very much. –  ArtM Nov 27 '12 at 13:52
    
@ArtM: You're welcome! –  joriki Nov 27 '12 at 14:01
    
@ArtM: Sorry, there was a mistake; the period is otherwise $m-1$, not $m$. –  joriki Nov 27 '12 at 14:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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