Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

This is a follow up to Period of linear congruential generator .

How can you calculate the probability distribution of the period length of a general congruential generator? That is $X_{n+1} = \sum_{i=0}^k a_i X_n^i \bmod m$ where the $a_i \in \mathbb{Z_m}$ are chosen uniformly at random, $k>1$ is a fixed integer and $m$ is a fixed prime. Take $X_0$ to be some arbitrary value from $\{0,\dots, m-1\}$.

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

share|improve this question
Do I understand correctly that you want $X_{n+1}=bX_n$, with $b=\sum_{i=0}^ka_i^i$ (where the superscript denotes the $i$-th power?), so the question is basically asking for the probability that $b$ is $0$ or $1$ if the $a_i$ are uniformly distributed? – joriki Nov 27 '12 at 14:56
@joriki. Typo, sorry. Fixed. – ArtM Nov 27 '12 at 15:07

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.