4
$\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.)

Improve this question
$\endgroup$
3
  • $\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, 2014 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, 2014 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, 2014 at 20:06

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ "...an extractor such as..." What are the others please? $\endgroup$
    – Paul Uszak
    Sep 8, 2015 at 12:51
  • $\begingroup$ TCS conferences such as STOC and FOCS contain many papers exhibiting extractors. $\endgroup$
    – Yuval Filmus
    Sep 8, 2015 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, 2015 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, 2015 at 21:54
  • 1
    $\begingroup$ But there were others, as I have explained. They just have no practical significance. $\endgroup$
    – Yuval Filmus
    Sep 10, 2015 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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