Hacker News Reader

Comment by giberson | Hacker News Reader

Q: Why was it necessary to invalidate the names that were selected?

U.S. law requires that Diversity Immigrant visas be made available through a strictly random process. A computer programming error resulted in a selection that was not truly random.

They maybe should be careful with their wording, since "not truly random" would basically disqualify any code based random generator.

Overview of PRNG, TRNG for reading if you're unfamiliar: http://www.random.org/randomness/

View on HN

My guess is that there is a NIST definition of "truly random" which they failed to satisfy.

I doubt PRNG is the issue. PRNGs satisfy the criteria for equal likelihood of being selected which I believe is what they want. A truly stochastic process is not necessary.

I wasn't suggesting that it was the issue. I was pointing out their QnA section uses the phrase "truly random" to explain why that specific set wasn't valid. Which semantically, "truly random" disqualifies all of their previous sets and not just this one. Their QnA section probably should have been more along the lines of "not appearing random enough".

One issue with PRNGs used for lotteries like this is the seed size. For example, the law might say that every combination of 12 eligible people is equally likely to be selected for a jury. But the number of possible sets of 12 people can be very large, say 2^1024 for some population. If the initial seed of the PRNG only takes 320 bits, then it violates the law. There can only be 2^320 different combinations of 12 people selected, this means that by definition not all possible sets of the 2^1024 are equally likely (many have probability 0).

If the law had said instead that each PERSON must be equally likely to be selected for the jury, then the PRNG would have been fine since the number of people is much lower than the seed space.

I don't believe this was the issue here, but it's interesting.

Reference with more examples: http://portal.acm.org/citation.cfm?id=769827

"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin" - John von Neumann

I was about to ask how are they generating their random numbers now.

Further, a "truly random" process is not necessarily uniformly random - although the colloquial definition of "random" implies uniformly random, a number that comes from any arbitrary probability distribution is a random number.

Reply on news.ycombinator.com