# Behaviour of congruential generator

Define $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\}$. What is the mean cycle length?

-

$X_n = c/(1-a) + (X_0 - c/(1-a)) a^n \mod m$. The period is the order of $a$ mod $m$. For each $t$ dividing $m-1$, the number of $a$ with order $t$ is $\varphi(t)$. So the mean period is $$\frac{1}{m-1} \sum_{t | m-1} t \varphi(t)$$ See http://oeis.org/A057660 for that sum.

EDIT: This doesn't count the case $a=1$ properly: there we have $X_n = X_0 + c n$ and the period is $m$ (unless $c=0$ in which case the period is $1$). So the mean period for the case $a=1$ is $m - 1 + 1/m$ instead of $1$, and the correct mean period is $$\frac{m-1}{m} + \frac{1}{m-1} \sum_{t | m-1} t \varphi(t)$$ Thus for $m=7$, where $\sum_{t | 6} t \varphi(t) = 21$, the mean period is $\dfrac{6}{7} + \dfrac{21}{6} = \dfrac{61}{14}$.

-
You must be doing something wrong. For $m=2$ there are just two cases: $a=1, c=0$ (period $1$) and $a=1,c=1$ (period $2$). So the mean period is $1.5$. You can't possibly have a period greater than $2$ when there are only two possible values. –  Robert Israel Feb 6 '13 at 2:35
pastebin.com/KmUNkH0h has a complete enumeration of the $m=7$ case which gives the mean as exactly $4$. (The variable $b$ is the same as $c$ in the question.) Do you see why there is a discrepancy? –  user59560 Feb 8 '13 at 19:18
Yes, the problem is that I was taking the period of the function as a whole, neglecting the fact that (for $a \ne 1$) there is a fixed point $X_0 = c/(1-a)$. Taking this into account, the end result is that the mean period is $$1 + \frac{1}{m} \sum_{t | m-1} t \varphi(t)$$ This agrees with your results: $3/2$ for $m=2$, $2$ for $m=3$, $3.2$ for $m=5$, $4$ for $m=7$. –  Robert Israel Feb 8 '13 at 21:02
Perfect, thanks! –  user59560 Feb 8 '13 at 21:29

it is not a mean, it is a fixed number. there are many papers on this field

-