Random walks arising in random number generation (Q1091018)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Random walks arising in random number generation |
scientific article |
Statements
Random walks arising in random number generation (English)
0 references
1987
0 references
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.
0 references
Fourier analysis
0 references
discrete Fourier analysis
0 references
Random number generators
0 references