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
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    Fourier analysis
    0 references
    discrete Fourier analysis
    0 references
    Random number generators
    0 references
    0 references
    0 references