Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
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 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

share|cite|improve this answer

Your Answer


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