Worst TED talk ever?

Does the graph of 5 people, with 5 choose 2 = 10 connections bug you when he says 120? What about when he shows 10 people, with 10 choose 2 = 45 connections, and then says 10 factorial is approximately 3.6 million? Does it irk you that he never actually describes what an "interaction" is? Skip to 6 minutes and 30 seconds if you are lazy or bored.

A nifty little election time dynamic program

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 those probabilities and see what happens. In his code, he runs the simulation 100,000 times. On my laptop, this takes about 4 seconds and yields only an approximation with error of about .001. Aww, poor physicist, if only Randall was a computer scientist, maybe he'd see how to compute it exactly and much more quickly.

So, how can we compute this efficiently? The key to my program running quickly is that total number of electoral votes (538) is much smaller than the total number of possible election outcomes (2^50).

Imagine we have a partially computed an election in which k states have already voted, and that pk,i is the probability that the democrats have won exactly i electoral votes after the first k elections have run. Furthermore, let vk be the number of electoral votes for state k and ek be the probability state that state k elects a democrat.

How can we compute pk,i? Well, this simple little recurrence will do it.
pk,i = ek * pk-1,i - vk + (1 - ek) * pk-1, i. Basically, with probability ek the state votes democrat and has i - vk votes left, otherwise, with probability 1 - ek it votes republican (assuming two party system), and the democrat still has i votes left. For this problem, we only need about 539 * 51 table entries (we could even do something clever and push the needed space down to 539 entries, but I'll leave that as an exercise for the reader).

After I implemented this, the computation runs much more quickly than one second and provides an exact answer.

Looking at the code a bit more, I found a (slightly refactored) snippet of code like this. I assume the code is supposed to output the outcomes in order. Take a look at the comment, is it simpler than sorting? Is it even correct? I challenge both accounts.

def render_outcome(pdem, prep, ptie):
    dstring="Obama:  <span style=\"color: #0000FF\">"+str(round(pdem,1))+"</span>"
    rstring="McCain: <span style=\"color: #FF0000\">"+str(round(prep, 1))+"</span>"
    tstring="Tie: <span style=\"color: #888888\">"+str(round(ptie, 1))+"</span>"

    if pdem>prep and prep>ptie:
        return dstring+"\n"+rstring+"\n"+tstring
    if prep>pdem and pdem>ptie:
        return rstring+"\n"+dstring+"\n"+tstring
    #just in case ... (easier to do this than a sort)
    if pdem>ptie and ptie>prep:
        return dstring+"\n"+tstring+"\n"+rstring
    if prep>ptie and ptie>pdem:
        return rstring+"\n"+tstring+"\n"+dstring
    if ptie>pdem and pdem>prep:
        return tstring+"\n"+dstring+"\n"+rstring
    if ptie>prep and prep>pdem:
        return tstring+"\n"+rstring+"\n"+dstring
    return tstring+"\n"+rstring+"\n"+dstring

Here is my alternative implementation.

def render_outcome2(pdem, prep, ptie):
    dstring="obama:  <span style=\"color: #0000ff\">"+str(round(pdem,1))+"</span>"
    rstring="mccain: <span style=\"color: #ff0000\">"+str(round(prep, 1))+"</span>"
    tstring="tie: <span style=\"color: #888888\">"+str(round(ptie, 1))+"</span>"
    l = [(pdem, dstring), (prep, rstring), (ptie, tstring)]
    return '\n'.join(pair[1] for pair in sorted(l, reverse=True))

Mine definitely seems simpler. It relies on the natural sorting order of python tuples to get the messages sorted in the right order.

Is his implementation correct? Well.. notice all of those < operators (not <=). What happens with ties?

>>> print states.render_outcome(.4, .3, .3)
Tie: 0.3
McCain: 0.3
Obama:  0.4

Uh oh..

In all fairness, quoting the page, Randall says "I made this tool to help me understand the race, especially on election night." I am sure he just wanted to get things done, and not have some nerd nitpick at all of the code. The Monte Carlo simulation is a bit easier to code than the dynamic program I posted and it gets things done. His code basically works. I don't think he actually sucks at programming, I just wanted to put some blood on the pages for reddit. Furthermore, I was thinking about using this problem as an interview question, but after trying it on a few of my coworkers (who all have at least a BS in computer science from a nice university), I think it's a bit too hard.

TrainLogic, you suck

I was in New Brunswick and I wanted to know when the next train was this Sunday. As anyone with a blackberry knows, the New Jersey transit website sucks on the blackberry browser. So I install this blackberry app from TrainLogic that seems useful.

Wow, what a giant waste of time. Ugh. Installing it involves copying a serial number from the application onto an online form and solving a case sensitive captcha (this is miserable on the auto text completing blackberry). Don't worry, if you screw up a single input, your input will be erased and you will need to start over, painfully retyping that 10 character serial and inputting another the 5 character random captca. If you unlock the app this far it will finally tell you that it is "randomly changing the train times." You can go online again and give them $7 for 6 month access to a schedule. No thanks. I feel like I should be getting paid for dealing with so much bullshit. It took me about 15 minutes to get here. Miserable!

[Gamers-ny] Rob "Crackhead" Renaud Wins RftG World Championship, Positively Reinforces Addiction

Rob's reign as world-champion was, however, short-lived. Peter Schmitt, yesterday, with his masterful employ of the dreaded Galatic Federation / Trade League combo, served Rob a slice of humble pie. The price for this delicious mocel of baked good: Rob's RftG World Championship Belt. Down, but not out, Rob has pledged to remain addicted to RftG to the exclusion of his hair's kemptness.

Games Night. 6 PM. 5BB. RftG Intercontinental Championship up for grabs. No hitting other players with metal chairs please.

- Ross Fairgrieve

Of course, it wasn't a title match. For that, only next year's World Boardgaming Championship will suffice.