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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\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
    Commented Dec 5, 2012 at 21:09
  • $\begingroup$ It studies the statistical properties of such generators, which is why I suggested. $\endgroup$
    – Igor Rivin
    Commented Dec 5, 2012 at 21:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .