Find all of the cycles of the following congruential generators. For each cycle identify which seeds $X_0$ lead to that cycle. $$(a). X_{n+1} = 9X_n + 3\mod 11$$ $$(b). X_{n+1} = 8X_n + 3\mod 11$$ $$(c). X_{n+1} = 8X_n + 2\mod 12$$
How can i choose the seed,$X_0$, at random ?
When will i stop to generate numbers ?
I supposed to draw $X_0$ at random from $0$ to $10$ [since $m=11$]and wrote R codes :
X<- 0
X[1]<-8 # seed ,Xo
for(i in 2:11){
X[i]<-(9*X[i-1]+3)%%11
cat("",9*X[i-1]+3,"",X[i],"\n")
}
X
How can i solve the problem ?
I will use $x(n)$ instead of $X_n$.
From $x(n+1) = 9x(n) + 3 \mod 11$, we see $x(n+1) -1 = 9x(n) +2 = 9(x(n) -1) \mod 11$. It is from $2 = -9 \mod 11$. So $(x(n) -1) = 9^n (x(0) -1 ) \mod 11$, $x(n) = 9^n(x(0)-1) +1 \mod 11$.
$9^n$ are $1, 9, 4, 3, 5, 1, \cdots \mod 11$ where $n = 0, 1, 2, 3, 4\cdots$, so in general length of cycle is 5. But if $x_0 = 1$, then $x(n) = 1 \mod 11$ for all $n\ge1$. Since 5 is prime, there could not be any other smaller cycle.
I don't know statistics or probability, but this problem seems to be solved like this way (number theorical way).
On (c), If the problem was not in modulo arithmetic but in real number system, $x(n+1) + \frac{2}{7} = 8(x(n) + \frac{2}{7})$. So, we need $7^{-1} \mod 12$.
Since 12 is not a prime, in general inverse could not exist; but $7\times 7 = 1 \mod 12$, number $7$ has its inverse in $\mod 12$, (c) also could be solved.