3
$\begingroup$

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?

[1] George Marsaglia, "Seeds for random number generators." Communications of the ACM, 46(5):90–93, 2003 (ACM page.)

$\endgroup$
  • $\begingroup$ Is the Marsaglia article important to the question? I can't access it through the paywall even from my university computer. $\endgroup$ – David Richerby Dec 15 '14 at 18:11
  • $\begingroup$ I would not say that the Marsaglia article is critical to the question, except that I'm hoping to avoid answers that are redundant with his methods of seeding large period PRNGs. My question is about using von Neumann unbiasing as an alternative to having some robust seeding method. I am hoping to avoid lengthy discussions about alternative seeding methods themselves. $\endgroup$ – Mayur Patel Dec 15 '14 at 19:57
  • 1
    $\begingroup$ OK. I added "For example" to the question before Marsaglia's name, in the hope that people won't be put off trying to answer the question if they can't access that article. Please undo the edit if you feel that isn't an improvement. $\endgroup$ – David Richerby Dec 15 '14 at 20:06
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "...an extractor such as..." What are the others please? $\endgroup$ – Paul Uszak Sep 8 '15 at 12:51
  • $\begingroup$ TCS conferences such as STOC and FOCS contain many papers exhibiting extractors. $\endgroup$ – Yuval Filmus Sep 8 '15 at 13:00
  • $\begingroup$ Thanks. Do any of them feature some sort of computer code /algorithm? My research so far has found that all extractors are either theoretical, or their actual implementation is curiously omitted. $\endgroup$ – Paul Uszak Sep 9 '15 at 21:41
  • $\begingroup$ There is no practical use for these theoretical extractors. Practically, the problem is solved using a good hash function. $\endgroup$ – Yuval Filmus Sep 9 '15 at 21:54
  • 1
    $\begingroup$ But there were others, as I have explained. They just have no practical significance. $\endgroup$ – Yuval Filmus Sep 10 '15 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.