Random walks arising in random number generation
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.
- Random processes of the form \(X_{n+1}=a_ n X_ n+b_ n\pmod p\)
- An optimal random number generator on \({\mathbb{Z}}_ p\)
- Structural Properties for Two Classes of Combined Random Number Generators
- On the adequacy of pseudy-random number generators (or: How big a period do we need?)
- Uniform random number generation
- Asymptotic behavior of an affine random recursion in \(\mathbf Z_p^k\) defined by a matrix with an eigenvalue of size 1
- A random walk model of digit comparison
- An optimal random number generator on \({\mathbb{Z}}_ p\)
- An affine walk on the hypercube
- Moderate growth and random walk on finite groups
- Random walks supported on random points of Z/nZ
- Random random walks on the integers mod \(n\)
- A note on various holding probabilities for random lazy random walks on finite groups
- Efficiency test of pseudorandom number generators using random walks
- Random walks on rings and modules
- Correction to: ``Speeding up Markov chains with deterministic jumps
- Mixing time of fractional random walk on finite fields
- Cut-off phenomenon for the ax+b Markov chain over a finite field
- Practical product proofs for lattice commitments
- Accelerating abelian random walks with hyperbolic dynamics
- Markov chains on finite fields with deterministic jumps
- A multiplicatively symmetrized version of the Chung-Diaconis-Graham random process
- The-square-and-add Markov chain
- Random motion on finite rings. I: commutative rings
- Speeding up Markov chains with deterministic jumps
- On a lower bound for the Chung-Diaconis-Graham random process
- Abrupt convergence and escape behavior for birth and death chains
- Mixing time of the Chung-Diaconis-Graham random process
- A lower bound for the Chung-Diaconis-Graham random process
- Some things we've learned (about Markov chain Monte Carlo)
- A Sampler of Randomness
- Local characteristics of smoothing properties of endomorphisms of finite abelian groups
- On the Lehmer conjecture and counting in finite fields
- Random sequences of the form \(X_{t+1}=a_1X_t+b_t\) modulo \(n\) with dependent coefficients \(a_t, b_t\)
- Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
- Random walks on the circle and Diophantine approximation
- On the multiplicative Chung-Diaconis-Graham process
- Using Bernoulli maps to accelerate mixing of a random walk on the torus
- Nash inequalities for finite Markov chains
- Random Lie bracket on \(\mathfrak{sl}_2 (\mathbf{F}_p)\)
- Spectral gap of nonreversible Markov chains
- Random sampling of contingency tables and partitions: two practical examples of the Burnside process
- A random polynomial with multiplicative coefficients is almost surely irreducible
- A random walk approach to Benford's law in rational stick fragmentation
- Generating uniform random vectors in \(\mathbb Z^k_p\): the general case
- Generating random vectors in ( Z/ p Z)^d via an affine random process
This page was built for publication: Random walks arising in random number generation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091018)
