This is the authors' abstract. We don't add key points for this paper.
Random number generators often work by recursively computing Xₙ₊₁ ≡ aXₙ + b ( p). Various schemes exist for combining these random number generators. In one scheme, a and b are themselves chosen each time from another generator. Assuming that this second source is truly random, we investigate how long it takes for Xₙ to become random. For example, if $a = 1$ and $b = 0, 1$, or $-1$ each with probability 1/3, then cp² steps are required to achieve randomness. On the other hand, if $a = 2$ and $b = 0, 1$, or $-1$, each with probability 1/3, then c log p loglog p steps always suffice to guarantee randomness, and for infinitely many p, are necessary as well, although, in fact, for almost all odd p, 1.02 log₂ p steps are enough.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Chung et al. (1987) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: