2
$\begingroup$

This is a cross-post of the unanswered question (the given answer turned out to be incorrect) https://math.stackexchange.com/questions/245591/period-of-linear-congruential-generator .

How can you calculate the probability distribution of the period length of a linear congruential generator? This is $X_{n+1} = (aX_n + c) \bmod m$ where $a$ and $c$ are chosen uniformly from $\{0,\dots, m-1\}$ and $m$ is a fixed prime. Take $X_0$ to be an arbitrary integer from $\{0,\dots,m-1\}$.

If it is hard to do exactly, is it possible to give good bounds for the cdf?

$\endgroup$

1 Answer 1

1
$\begingroup$

Kurlberg, Pär, and Carl Pomerance. "On the period of the linear congruential and power generators." arXiv preprint math/0405120 (2004).

$\endgroup$
2
  • $\begingroup$ @Igor, Thank you for the reference. I am not sure that it deals with the problem of determining a probability distribution when $a$ and $c$ are chosen at random does it? $\endgroup$
    – ArtM
    Dec 5, 2012 at 21:09
  • $\begingroup$ It studies the statistical properties of such generators, which is why I suggested. $\endgroup$
    – Igor Rivin
    Dec 5, 2012 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.