Programming error invalidates US Diversity Visa lottery results

http://www.dvlottery.state.gov/

by troydavis • 15 years ago

52 65 15 years ago

dvlottery.state.gov

troydavis• 15 years ago

Posted results have been rescinded and the lottery is being redone. state.gov site links to video with more info: http://link.brightcove.com/services/player/bcpid1857622883?b...

Groxx4• 15 years ago

Important bit that's in the video but not on the page:

>"...[a programming error had caused] more than 90% of the selectees to come from the first two days of the registration period ..."

The registration period was 30 days, and had "many" entries each day. That's... shockingly bad.

hugh32• 15 years ago

Would be much more interesting if we knew how the results wound up nonrandom.

cosgroveb• 15 years ago

Maybe something like the following?

  randWinnerID = (int) Math.random();

rorrr• 15 years ago

It was much worse, all the "winners" were the people who submitted their applications in the first 2 or 3 days.

chernevik2• 15 years ago

Crucial, actually. They should provide enough transparency to assure that "not random" != "favored persons not selected".

hugh32• 15 years ago

That's a bit conspiracy-heavy for my tastes. If someone in a position of power in the State Department wants to give a particular individual a greencard there are easier ways than keeping on re-running the greencard lottery 'til they get one.

jey• 15 years ago

Why will it take two months to randomly select entries from a list?

guan• 15 years ago

They probably want to make extra sure that there are no errors this time.

cypherpunks01• 15 years ago

That's the problem with randomness, you can never be sure.

giberson2• 15 years ago

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/

rbanffy2• 15 years ago

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

aramadia2• 15 years ago

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.

giberson2• 15 years ago

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".

nwhitehead• 15 years ago

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

smhinsey• 15 years ago

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

coin• 15 years ago

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

scott_s4• 15 years ago

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.

vitalysh• 15 years ago

uh, imagine if you are one of the winners :/

Groxx4• 15 years ago

>The results were not valid because they did not represent a fair, random selection of entrants, as required by U.S. law.

How does one get so bad at using random numbers? Surely selecting random entries from a list isn't hard. `entries[rand*entries.count]`

hvs• 15 years ago

If "rand" is generated by a computer and not from a stochastic process, it's not technically random.

Groxx4• 15 years ago

I'm fairly sure other, accepted government tasks have used PRNGs. So there would be precedence for doing so.

If not, I'd roll a 10,000 sided die, and type it in by hand. (edit: or cow pie bingo. That has a long tradition of unbiased results.)

brianr• 15 years ago

Could've been a bad shuffle implementation. There are lots of ways to do that: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Im...

jemfinch2• 15 years ago

As another poster stated, the drawing pulled 90% of the applicants from the first two days of the application period.

Perhaps the bug was something like "bool choose_this_applicant = random() < 1/total_applicants_received_so_far". It would have similar behavior, might appear correct at first glance (at least to the sort of programmer who settles for a government job) and would be utterly, completely wrong.

ubasu• 15 years ago

Have they used the same software in prior years also, or is this because of a new software?

SeoxyS3• 15 years ago

Good: I got rejected, I get a second shot.

Bad: How can the State Department be so incompetent as to fuck this up? Also, why does it take months to generate this? I could do it with 15min and a simple script. Granted, any code generator is never truly random (Newtonian laws of physics pretty much forbid randomness,) but for all intents and purposes they're more than capable of handling a simple lottery.

aramadia2• 15 years ago

Uhh, Newtonian laws have really nothing to do with this. Its more information theory, you can't get more entropy from what you put in. Also, it is clear now that the Newtonian model is not an accurate view of the universe, and that there are fairly random events such as radioactive decay.

SeoxyS3• 15 years ago

There's an interesting article on random.org that talks about just that. http://www.random.org/randomness/

This is dwelling into philosophy, but some argue that the universe is deterministic. With absolute knowledge of every particle in the universe, you could predict the entire course of everything that would happen in the future.

The key is not to find true true randomness, which can reasonably be argued not to exist, but rather to find a system that is chaotic enough to be beyond control or predictability, and use that to generate random numbers. Weather systems, radioactivity, etc. are examples of this.

Now I don't know much about quantum physics, and I hear that that might be an alternative to that—but my point is that I don't think it matters. A generator doesn't have to be truly random, it should just be random enough.

PonyGumbo• 15 years ago

Clearly we need to import better programmers.

protomyth• 15 years ago

State is better than Interior, read some articles on their "use" of technology.

Someone• 15 years ago

According to dutch teletext, the error was a very simple one: not all applicants were entered into the draw. It does not give further details.

ez772• 15 years ago

I participated, and things looked bad enough when I saw that IE7 or lower was requiered... The Vista boot option, which I never use, alas did not help.

rubashov4• 15 years ago

The Visa Lottery is infuriating. It's almost as stupid as the family sponsorship driving our visa allocations.

The purpose of an immigration policy is to serve the citizenry. Only the most useful and "profitable" people should be let in, period.

kentrado• 15 years ago

Meanwhile, US foreign economic policies like free trade agreements displace people from their country into the US in order to survive, by becoming second class citizens and cheap labor for big corporations.

Meanwhile, red necks scream in anger, teir took uor jobs!!

Do you remember that time when the sons of immigrants (because in america everybody is the son or the grandson of a immigrant) were not angry at the newcomers? Neither do I, because it is always been this way.

hudibras• 15 years ago

So much for "All men are created equal," eh?

Over ten million people each year apply through this program for only 50,000 green cards. In a nation of 300 million people, I think we can manage this.

rubashov4• 15 years ago

Stop and think about how absurd this is. Ten million people apply and we pick randomly, rather than take the cream.

Is this not plainly insane?

jemfinch2• 15 years ago

All men (and women) are created equal, of course. What rubashov is talking about is what they do with their lives after they're created.

webspiderus2• 15 years ago

my mom won the green card lottery 10 years ago, when I was still young and surely wouldn't have been very useful or profitable. 10 years later, I'm getting my master's at one of the best universities I could've hoped for, and a pretty good chance of being able to do interesting work with competitive pay. I'm extremely grateful for the lottery, which is the one thing that made all of this possible.

my mom also got a chance to actually apply her computer science degree (which she couldn't do before because of the explicit sexism which meant women were generally employed as, perhaps glorified, receptionists), and now works as a senior software engineer at a large company. I imagine her true potential would also have been difficult to estimate prior to the move, as she'd done very little actual programming after college - but she effectively got a fresh start here, and was able to quickly advance in an environment which allowed her to be judged solely on technical competency.

rubashov4• 15 years ago

Good for you. Are the American people better off thanks to you and your mother's presence here? Or would they have got along just as well without you? That's the salient question.

huherto• 15 years ago

A point based system as the one used in other countries may be better. You get points for education, experience, financial status, family ties, age, origin, etc.

nabaraj• 15 years ago

They should have gave to those who were selected despite of non-random. Cmon they must be freaking depressed now!

alvarosm• 15 years ago

More importantly, for how many years has the selection process not been "truly random"? if it was really fucked up it could even mean some people could never be selected given their name and DoB.

inrev2• 15 years ago

BTW, if you win, you have to pay the Diversity Visa Lottery fee $440/person

kooshball• 15 years ago

If that's true, it would be a small price to pay for a green card.

raymondh• 15 years ago

My bet is that the problem was much worse and more subtle than the other commenter's have noted. They posit a slight imbalance to due to rounding or PRNG characteristics.

I suspect that is it like the problem of choosing values randomly from a sparse hash table. Choosing a random slot and scanning forward to the next empty slot results in a bias where closely spaced entries have a much lower chance of selection than entries preceded by a wider gap.

It is easy to make that same mistake when trying to pick a random record number when record numbers have been assigned in chunks (like social security numbers).

etureiab• 15 years ago

I was one of those picked and am really pissed. This is so screwed up! Does your employer ask you to pay the extra monthly salary back when they made a mistake in their system? "NO!". They should have made the exception to re-draw "randomly(!)" among the non winners and give them another chance. But do not take away what you promised because of your inaptitude!

Programming error invalidates US Diversity Visa lottery results

Related Stories