5
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

7
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Is $c/(1-a)$ uniformly distributed? $\endgroup$
    – ArtM
    Nov 27, 2012 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, 2012 at 13:42
  • $\begingroup$ @ArtM: You're welcome! $\endgroup$
    – joriki
    Nov 27, 2012 at 14:01
  • $\begingroup$ @ArtM: Sorry, there was a mistake; the period is otherwise $m-1$, not $m$. $\endgroup$
    – joriki
    Nov 27, 2012 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$
    – user35671
    Nov 27, 2012 at 20:17

You must log in to answer this question.

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