Steve entered the Western States 100 lottery after qualifying in January... They are limited to 369 runners each year, and it's a legendary race, so there's a lot of demand. They have an interesting lottery structure: every year that you qualify and enter the lottery, if you are not picked, you get twice the entry tickets the next year.

After some early morning text messages where I tried (and to be honest, failed miserably) to calculate his odds, I wrote a little program in C to do the calculation.

Then, because sometimes programming is fun, I decided to see what it would look like in Perl. I haven't written a ton of Perl, I usually lean towards PHP for this sort of thing, but I ported SWELL's resource-processor script to Perl a while back and enjoyed it, and having a simple task is good for learning.

The first pass I did used a builtin array shuffle module, which proved too slow, then I ended up simplifying it and got it significantly faster than the C version (which didn't reshuffle, but did end up with pointless memmove()s). Once I had it all working (using strict, e.g. you have to declare everything), I decided to see how small I could get it to be. Here's what I ended up with (you can pipe the table on their lottery entry page to it):

$nwin = 250;    # I think the lottery picked about 250-something winners last year, the rest were golden tickets and such
$nlot = 100000; # someone could quantify the margin of error based on this, with statistics you would oh look a bird

for ($pid = 0; <>; ) {
  ($nt, $np) = split(/\s+/, s/,//r);
  ($nt > 0 and $np > 0 and not exists $wcnt{$nt}) or die "invalid input: $_\n";
  $wbin{$pid} = $nt;
  $wcnt{$nt} = 0;
  push(@tk, ($pid++) x $nt) while ($np-- > 0);
}

printf("%d tickets for %d entrants, running %d lotteries for %d winners:\n", $tkcnt = @tk, $pid, $nlot, $nwin);

for ($x = 0; $x < $nlot; $x++) {
  %in = { };
  $in{$id = $tk[rand($tkcnt)]}++ == 0 and exists $wbin{$id} and $wcnt{$wbin{$id}}++ while (%in < $nwin);
}

printf("%d tickets: %.2f%% win\n", $_, $wcnt{$_} * 100.0 / $nlot) foreach (sort { $a <=> $b } keys %wcnt);

Here is the most recent input:

512	 	1	 	512
256	 	15	 	3,840
128	 	55	 	7,040
64	 	139	 	8,896
32	 	215	 	6,880
16	 	296	 	4,736
8	 	594	 	4,752
4	 	963	 	3,852
2	 	1,538	 	3,076
1	 	2,077	 	2,077

and here is the most output with that table:

45661 tickets for 5893 entrants, running 100000 lotteries for 250 winners:
1 tickets: 0.66% win
2 tickets: 1.29% win
4 tickets: 2.56% win
8 tickets: 5.08% win
16 tickets: 9.99% win
32 tickets: 18.98% win
64 tickets: 34.12% win
128 tickets: 56.51% win
256 tickets: 80.91% win
512 tickets: 96.24% win

So, Steve's odds as of this afternoon are about 0.66%, but that will almost certainly go down (there's still a month left of the lottery; it only opened yesterday). Interestingly, one entrant there has been turned down 8 times before -- they currently have a 96% chance of getting in. And those who have been turnwed down 6 times before are slightly more likely than not to get in.