Large period PRNGs such as Mersenne Twister require good seeding otherwise the i

Question

Large period PRNGs such as Mersenne Twister require good seeding otherwise the initial output in the sequence may not seem to be high-quality, at least for the first few words (and in the way that is useful in production). For example, Marsaglia talked about seeding methods in his May 2003 Communications of the ACM article [1]. It feels like a chicken/egg situation. You need a source of high-quality random bits in order to seed your generator, so you can create a source of high-quality random bits.

I was wondering:

Is von Neumann unbiasing a legitimate way to defend against poor seeding of large-period PRNGs? In other words, if I apply von Neumann unbiasing to the bitstream output of Mersenne Twister, does the quality of the stream still depend on how I seeded it?

Explanation / Answer

Von Neumann unbiasing only works if the random source consists of independent samples. Otherwise it is not guaranteed to produce random bits. More generally, in theoretical computer science there exist objects called (randomness) extractors whose job is to extract random bits out of imperfect random sources. Usually they need access to a small number of "high quality" random bits.

In practice, seeding a PRNG is not difficult. There are many legitimate sources of randomness, and using an extractor such as a hash function, you can take a decently sized sample and extract a decently random seed. Once you have a handful of high quality random bits, you can use a PRNG to quickly extract many more seemingly random bits.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.