Random walks arising in random number generation (Q1091018)

Random number generators often work by recursively computing \(X_{n+1}\equiv aX_ n+b(mod 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_ n\) to become random. For example, if \(a=1\) and \(b=0\), 1, or -1 each with probability 1/3, then \(cp^ 2\) 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 log log 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\({}_ 2p\) steps are enough.