• Tips gratefully accepted here. Thanks!:

  • Recent Comments

    Ivory Bill Woodpecke… on Perspective.
    Ivory Bill Woodpecke… on Perspective.
    Ivory Bill Woodpecke… on Perspective.
    thewizardofroz on Perspective.
    riverdaughter on Perspective.
    James Bowater on Perspective.
    Ivory Bill Woodpecke… on In spite of it all…
    Ivory Bill Woodpecke… on In spite of it all…
    Ivory Bill Woodpecke… on Happy Thanksgiving!
    Ivory Bill Woodpecke… on Happy Thanksgiving!
    Ivory Bill Woodpecke… on Happy Thanksgiving!
    Ivory Bill Woodpecke… on Happy Thanksgiving!
    Ivory Bill Woodpecke… on In News: GA SOS thrown under b…
    Ga6thDem on In News: GA SOS thrown under b…
    William on In News: GA SOS thrown under b…
  • Categories

  • Tags

    abortion Add new tag Afghanistan Al Franken Anglachel Atrios bankers Barack Obama Bernie Sanders big pharma Bill Clinton cocktails Conflucians Say Dailykos Democratic Party Democrats Digby DNC Donald Trump Donna Brazile Economy Elizabeth Warren feminism Florida Fox News General Glenn Beck Glenn Greenwald Goldman Sachs health care Health Care Reform Hillary Clinton Howard Dean John Edwards John McCain Jon Corzine Karl Rove Matt Taibbi Media medicare Michelle Obama Michigan misogyny Mitt Romney Morning Edition Morning News Links Nancy Pelosi New Jersey news NO WE WON'T Obama Obamacare OccupyWallStreet occupy wall street Open thread Paul Krugman Politics Presidential Election 2008 PUMA racism Republicans research Sarah Palin sexism Single Payer snark Social Security Supreme Court Terry Gross Texas Tim Geithner unemployment Wall Street WikiLeaks women
  • Archives

  • History

  • RSS Paul Krugman: Conscience of a Liberal

  • The Confluence

    The Confluence

  • RSS Suburban Guerrilla

  • RSS Ian Welsh

    • Happy Thanksgiving
      Be happy and be well. Please be careful about Covid. Viral load matters for infection, spending hours in a house with people is a great way to get infected. Feel free to use comments to discuss topics unrelated to recent posts. I’m doing my annual fundraiser. If you like my writing and can afford to, […]
  • Top Posts

Taking a Gambol with Monte Carlo

ronkseattle left this lttle easter egg in the comments:

Speaking of the pull-tabs, we have fresh Monte Carlo estimates from Hominid Views.

Hillary, 78.8% probability of beating McCain, with 278 mean EV.

Obama? 40.6%, 263.

The narrowness of the margins would suggest this is a “swing” contest, not a “map changer” cycle.

As we’re all shouting “Yeah!” many of us are scratching our heads thinking, “WTF is he talking about?” Well, as a geek who has a working knowledge of this stuff, let me sketch out the basics of the Monte Carlo agortihm, er, without the nasty math.

Ok, I lied, there is a little bit of math involved. Some problems have many answers. It’s not just that there are many ways to solve the problem, it’s that there are many solutions using the same problem solving techniques. The branch of math that deals with these kinds of problems is called heuristics. An example of these kinds of problems is called the Travelling Salesman problem.

Here’s how it goes: let’s say you were a salesman and you have to hit 4 cities in a givien period of time. What is the order of cities that you would visit in order to optimize the time you have and minimize the distance you travel? Well, you’d get out your map and your list of contacts and your budget for the visits and you’d sit down and calculate several different routes. After working on it for some time, you will come to an answer that is called the “global minimum” which is the absolute optimum route that maximizes the number of cities with the minimum amount of travel over the specified period of time. But you may *not* find a global minimum. Instead, you may find severl local minimum, all of them having roughly the same amount of optimization but taking different routes. So, in this case, you have a problem that has several different answers. If you’re wondering how this applies to real life, think back to when you last had a major appliance delivered to your house and the customer service rep gave you a four hour “window” that ruined your day. At her end, she is setting up deliveries and loading the truck so that the maximum number of deliveries can be made using the shortest route in a given period of time. Airlines work this way too with seating. And the stock market uses similar problem solving.

Now we come to something called Monte Carlo. Monte Carlo algorithms allow for these kinds of calculations to be carried out on massive scales usning multiple parameters. The problem with a problem with multiple parameters is that they’re difficult to do in your head and the range of answers is very large. If the problem is VERY large, it becomes difficult to know whether you’ve found the global minimum because there are so many possible answers and calculations can run for days, weeks, months. So, instead of running these things forever and filling up scads and scads of disk space with answers, you can try a sampling technique like a Monte Carlo simulation. AMonte Carlo simulation is a stochastic method because there is no guarantee that you will find the global minimum, though if you run it long enough and generate enough random starting points, you will have covered most, if not all of your solution space.

And here’s how it works: Let’s say that you are trying to figure out who has the best chance of winning an election. You have the red team, the blue team and the green team. And let’s say you have some data based on demographics, population, past voting habits, party affiliation and primary results. These are your parameters. The first thing you do is randomly generate a map where the teams are scattered all over the place in different states. Your goal is to determine the solutions where the blue team beats the red team in electoral college votes. (you can do a subsequent calculation with Green vs Red) Then you begin the simulation. The outcome of the first random scattering is calculated and out comes an electoral college vote prediction of the Blue team versus the Red team. Then another random scattering is made and the electoral college prediction is made again. If the second prediction is better than the first one, it is retained. provided it meets a certain threshold. If it’s worse, then you compare it to a threshold value, like, Blue needs 270 votes to win the whole shebang. So, if the first prediction is 283 Blue, 245 Red, you keep it, If the second one is 276 Blue, 254 Red, you keep it and add it to your minima. If the second one is 254 Blue, 270 Red, you discard it. You can let this calculation run for x number of steps, say 5000. Then you look at the minima. The minima should fall into families, like, the Blue team can only win if you include Florida and Ohio. Or the Green team can’t win without Michigan and New Jersey. The outcome can look something like this.

Ok, now tell me I just wasted my lunch hour on this post.

13 Responses

  1. Riverdaughter –

    What an excellent explanation of Monte Carlo algorithms. I particularly liked your explanation of what is considered an “Accepted” step. See, in molecular simulations, we put all these parameters in and look at the energy of a system. If the energy is lower, that steps “accepted” and becomes your new starting point. If it’s higher, it doesn’t mean you reject it, but you compare it to a threshold and if it’s below the threshold, then you keep it (even though it has a higher energy).

    Isn’t a Monte Carlo algorithm just a description of our everyday lives? We want to achieve good things in life and make progress, but sometimes we have to take the bad to achieve a the good… Here I am trying to illerately wax philosophical……

  2. “Heuristics” is from the Greek word, “heureo, heurein” which means, “to cut.” A heuristic method cuts through the morass to get at something. I find that the morass that is Obamaphilia requires as many heuristic techniques as we have at hand. Thanks, riverdaughter.

  3. Jersey5555: You were supposed to tell me to get back to work.
    Good answer.

  4. I will leave it up to you math geeks to decipher this; I hated stats! You guys are so far above me in this arena that I bow to your interpretation. Now if you could just promise me a win I will be forever grateful.

  5. Pat: you should check out that homind site. They did 10,000 steps of simulation for each candidate vs McCain. It’s pretty cool and it shows all of the minima in a graph. It looks like when the simulation is run for Clinton, you get many more minima above 270 Eletoral college votes (EV). When the same simulation is run for Obama, you get many fewer over 270 EV’s. The maps show you which states they are most like to carry and need to win consistently from minimum to minimum. And there was no math involved.

  6. rd – In this application, there’s no minima-seeking (as there are in many more strenuous applications – see Darryl’s FAQ). Just brute-force statistical scatter, which the Central Limit Theorem drives to a Damn Good Estimate. (See the Bootstrap.)

    It’s the best published use of current polls to project November results. (One could construct an even more acute Futurescope by considering a vast array of interstate correlations, but one’d have to feed the hungry devil scads of debatable parametric assumptions in the process.)

  7. ronk: Yep, I’m just using minima as an example because that’s what I typically look for. But really, what we’re talkin about here is sets of solutions with the desired outcome.

  8. Oh, my aching head. Keep up the good work.

  9. This is way over my poor head! But it’s quite interesting.

    Riverdaughter should contact Obama and explain to him what “the math” really is.

  10. http://www.nytimes.com/2008/05/02/opinion/02krugman.html?_r=1&oref=slogin

    Must read Krugman today.

    Why does Obama love those ReThug ideas — even to the extent of crediting them with things they didn’t do?

    …both Democratic candidates have been saying things they shouldn’t; Hillary Clinton shouldn’t have endorsed the bad idea of a gas tax holiday.

    But I think Mr. Obama is doing much more harm to the Democratic cause by echoing Republican attack lines on such issues as insurance mandates and Social Security. And now he’s demonstrating his post-partisanship by giving Republicans credit for good ideas they never had.

  11. RD,

    Thanks for the excellent logical explanation. I am somewhat math phobic, though not as much so as I used to be since I got into psychology. I really enjoy statistics. I seem to do better with math when I can see a real-world reason for using it.

    When making predictions in politics, I tend to go with my intuition, informed by data. I’ve always been pretty good at picking winners. My gut tells me that Hillary is a winner. I’ve thought that for awhile, as my comments have indicated. As time goes on, I am more and more sure that I’m right.

  12. But what if the polls have a systematic bias? Presumably that would not be taken into account?

    For example, just suppose married women say one thing when the husband is within earshot, do something different alone in the voting booth?

    HRC seems to beat her polls pretty frequently – NH, CA, OH, TX, PA come to mind.

    Even if there were such an effect, it presumably would be different HRC/McO than HRC/BO.

  13. This is so cool! Thanks, RD!

Comments are closed.

%d bloggers like this: