Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
