A nifty little election time dynamic program

[ru_linux_geek]

Take a look at xkcd's election predictor. It scrapes a bunch of election outcome probabilities per state from intrade and uses them to provide a prediction for the overall election. It does so by using a Monte Carlo simulation, given the probabilities, it runs a mock election assuming each state outcome is independent a whole bunch of times with

Comments

Randall Monroe?

[anonymous]

His name is Munroe. Randall Monroe is the guy in the Geek Hero Webcomic http://geekhero.iovene.com/

Nitpickery

[mgedmin]

list objects do not have a 'sorted' method in Python. You want sorted(l).

The original code tried to put the largest number first. Your code puts it last. You want sorted(l, reverse=True).

Re: Nitpickery

[ru_linux_geek]

Nice catch, and I thought I tested it before submitting! I shouldn't edit code in the LJ interface.

[malaprop]

There are not 50 races in the electoral college, there are 57. You've both left out DC and the fact that Maine and Nebraska split up their electoral votes.

If you're interested in solid Monte-Carlo analysis, you probably can't do better than 538.

[ru_linux_geek]

I read 538 often. There is another high quality electoral analysis site here, http://election.princeton.edu/.

This site uses an algorithm similar to the one I described, but (maybe?) a bit faster and more complicated. From their FAQ.

In general, the probability distribution for all possible outcomes is given by the coefficients of the polynomial

((1 - P1) + P1 * x^EV1) * ((1 - P2) + P2 * x^EV2) * … * ((1 - P51) + P51 * x^EV51)

[malaprop]

Right, this is a standard application of generating functions.

-Chris

[larrytc]

This is a 250 in TC. Haha.

[ru_linux_geek]

They have 250s with DP and probability now? I think it would be more like a 500.

[larrytc]

It's gotten harder and harder.. =P

[larrytc]

Oh ya, as a side note, once on an interview a few years ago, I was given a simple problem to solve. Right off the bat, I knew the answer, so I was like "ya, so you would use dynamic programming on this one". To which the interviewer replied "so, how would you program this dynamically?"

Go figure.