Friday, November 30, 2012

Visiting Santa's Grave

I found out recently that Santa is buried in Ireland. No really he is and you can go visit his grave. Though a bonus, I didn't go to avoid having to get the sprog Christmas presents, I'm pretending to be Buddhist to do that.

Thomastown in Kilkenny is a funny town. It is beautiful looking and full of hippys but also has a rough edge to it. There are all sorts of art workshops and tea shops that the posh people run during the day and at night there is an air of menace and divilment about some of the pubs there.

John Martyn the towns most famous resident seems to also traverse these two characteristics. He has the hippy spirituality of his friend Nick Drake but also looked and acted like he was well up for a row.

It turns out that Thomastown may have always had the strange mixture of spiritual and hedonistic. Just outside the town is the famous Jerpoint Abbey and close to there is the newly rediscovered and Newtown.

The story of Newtown is that some Norman knights from Kilkenny headed off on the crusades in the 12 century. Taking religious relics was one of the major hobbies of the time like pokemon but with dead people. These two took back to Newtown what they claimed were Santa's bones and relics of St Nicholas. The story goes they got these in modern day Turkey. The aim of collecting these was possibly to create a tourist attraction to compete with other relics in Ireland. There is no way of telling at this remove that they were but contemporary accounts at least reveal that the people of the time believed they were.

The town thrived with these relics used as a draw for tourists and pilgrims. A three story church of St Nicholas was built.

A town developed around it including three mills. Eight pubs and a whore house the remains of which still exist. This was out of a total of 13 houses so pubs played a big role in the town. This shows religious pilgrimage may not have been so holy.
The town is at the last navigable point on the Nore, where it meets the Arygle.
These rivers powered the mills and allowed fish farming in the floodplain. Fish farming still takes place in the next door Goatsbridge farm which shows how little changes over time.

On the grave of Santa himself is the famous symbol of St Nicolas, the three figures.

These represent the three bags of gold Santa put down the chimney to pay the dowry of a poor mans three daughters. This both explains Santas chimney shimmying antics and the Pawn shop symbol. St Nicholas is the patron saint of pawn shops.
The guide explained the three heads on the gravestone as representing St Nicholas and the two crusaders who took his bones back to Ireland. The three figures symbol was generally thought to represent Jesus and Mary in medieval symbols.

The town was abandoned when the plague struck around 1346. Mills were havens for rats and towns were decimated while the more Gaelic countryside was much less effected. Monk John Clyn in nearby Kilkenny as the plague descended wrote the chilling 'so that the writing does not perish with the writer, or the work fail with the workman, I leave parchment for continuing the work, in case anyone should still be alive in the future and any son of Adam can escape this pestilence and continue the work thus begun'. The bridge over the river collapsed though the remains can still be seen. And the very existence of the town faded from memory to only recently be rediscovered. The stones from the houses were used in the railway bridge you can see form the ruins of Newtown.

The grave of St Nicholas is well worth a visit. The tour is informative and entertaining. The site is not over developed like some Irish tourist destinations. And the trip ends on the brilliant Father Ted touch of watching a sheep dog herd geese. Next time you are in Kilkenny head to Thomastown and Jerpoint and take the right lane up by the fish farm, it will at least save you money on Christmas presents.

Monday, November 05, 2012

Drawing the presidential Election

Finding all the ways the electoral college votes from each state can be added up to give both candidates 269 votes turns out to be really hard. Political pundits always bring up the spectre of a drawn presidential election.

What happens if the US election ends in a draw?

If There’s an Electoral College Tie, Things Will Get Even Crazier Than You May Know

Where both candidates get 269 of the electoral college votes.

The website 270towin calculates 32 practical combinations that could result in a tie and give the probability of one of these occuring given polling data at 0.2%.

The NYtimes here claims there are 5 practical ways a tie could result.

But how many possible drawing combinations are there in total, including implausible ones?

Elections are much closer than the set of all possible wins a candidate could have. Certain states are similar so tend to vote the same way so some divisions are far more likely than others. Also by the median voter theorem two competing parties will be as similar to each other as possible to get as much of the vote as they can. Roughly the Republicans will be as near the center as they can while getting all the right wing votes and the democrats as near the center while getting all the left wing votes.

But how many total ways are there that two candidates can win 50 states and one district? That is as, ColinTheMathmo pointed out, 2^51 as each state can go to either candidate. I want to find the number of allocations in this 2^51 that give each candidate 269 electoral college votes*.

2^51 is a big number. As Matthew Saltzman said the set partition is an NP-Complete problem and a 'Complete enum at 10M/sec, would take 7 years.'

But instead of complete enum we just want to see the cases where both candidates get 269. The code here calculates this. I took some Minizinc code from Hakan Kjellerstrand who pointed out an error in my previous reading of a result that would calculate all the allocations of states that give 269 electoral votes. The code is written in Minizinc as it can calculate all answers in a way GLPK** doesn't. Hakan also kindly pointed out some inefficiencies in my program so I am linking to his code.

Here are some of the many results it output

Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Montana Nevada 'New York' Ohio Pennsylvania 'South Dakota' Texas Utah 
----------
Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Montana Nevada 'New York' Ohio Pennsylvania Texas Utah Vermont 
----------
Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Montana Nevada 'New York' Ohio Pennsylvania Texas Utah Wyoming 
----------
Alaska California Delaware Florida Idaho Illinois Iowa Maine Michigan Mississippi Nevada 'New York' 'North Dakota' Ohio Pennsylvania 'South Dakota' Texas Utah 
My mac is 2.16 gz and has 2 gigs of RAM so it is not a fast machine. Still after three hours of running it ground to a halt. This means I have no answer for you. If I find out how many of the state allocations result in 269 votes I will let you know.

It is interesting that these sorts of difficult NP-Complete problems pop up in real life and getting solutions for them is not always easy.

* Actually Maine and Nebraska can give out votes proportionately so the search space is even larger than this

**Just in case someone can use it here is GLPK code that will work out one answer

/* sets */
set STATES;
set NEED;

/* parameters */
param VotesTable {i in STATES, j in NEED};
param Pop {i in STATES};
param Need {j in NEED};


/* decision variables: x1: alabama, x2: , x3: , x4:  x51: Wyoming*/
      var x {i in STATES} binary >= 0;

/* objective function 
          z: sum{i in STATES} VotesTable[i,j]*x[i];
     
/* Constraints */
s.t. const{j in NEED} : sum{i in STATES} VotesTable[i,j]*x[i] == Need[j];

/* data section */
data;

set STATES :=  Alaska Delaware "District of Columbia" Montana "North Dakota" "South Dakota" Vermont Wyoming Hawaii Idaho Maine "New Hampshire" "Rhode Island" Nebraska Nevada "New Mexico" Utah "West Virginia" Arkansas Kansas Mississippi Connecticut Iowa Oklahoma Oregon Kentucky "South Carolina" Alabama Colorado Louisiana Arizona Maryland Minnesota Wisconsin Indiana Missouri Tennessee Washington Massachusetts Virginia Georgia "New Jersey" "North Carolina" Michigan Ohio Illinois Pennsylvania Florida "New York" Texas California;
set NEED := Votes;

param VotesTable: Votes:=
 Alabama 9
 Alaska 3
 Arizona 11
 Arkansas 6
 California 55
 Colorado 9
 Connecticut 7
 Delaware 3
 "District of Columbia" 3
 Florida 29
 Georgia 16
 Hawaii 4
 Idaho 4
 Illinois 20
 Indiana 11
 Iowa 6
 Kansas 6
 Kentucky 8
 Louisiana 8
 Maine 4
 Maryland 10
 Massachusetts 11
 Michigan 16
 Minnesota 10
 Mississippi 6
 Missouri 10
 Montana 3
 Nebraska 5
 Nevada 6
 "New Hampshire" 4
 "New Jersey" 14
 "New Mexico" 5
 "New York" 29
 "North Carolina" 15
 "North Dakota" 3
 Ohio 18
 Oklahoma 7
 Oregon 7
 Pennsylvania 20
 "Rhode Island" 4
 "South Carolina" 9
 "South Dakota" 3
 Tennessee 11
 Texas 38
 Utah 6
 Vermont 3
 Virginia 13
 Washington 12
 "West Virginia" 5
 Wisconsin 10
 Wyoming 3;

param Need:=
Votes        269;

end;

Friday, November 02, 2012

Becoming President with 22% of the Votes

Political pundits talk about the possibility of winning the Presidential election with less votes than your opponent. Assuming only two candidates what is the lowest percentage of votes you could get and still win the election? In the case where everyone votes this becomes an interesting question. In America some states have a higher ratio of people to electoral college votes than others. If the ones that are preferentially treated banded together a small percentage of people could decide the election.

In my last post I created a program to work out in an overly complicated way what was the least amount of land a president could be elected from in the US. In this post I want to figure out the best states to win to get you 270+ electoral college seats using the smallest number of voters.

I got the estimated population in July 2011 from the census website here. Using this data in the glpk program below and got the result shown in this map. If everyone voted and the people who get the most power in votes all voted one way then the states on the winning side would have 135936335 voters to get 270 electoral college seats. The total population is 311591917 so 43.67% of the population

The winner would win 40 districts of the 51 states+dc and lose Virginia, Georgia, New Jersey, Michigan, Ohio, Illinois, Pennsylvania, Florida, New York, Texas, California.*

Now if the candidate in these states just squeaked a win by one vote and got zero votes in all the other states that means in a two party election you could win an election, where everyone voted, with under 22% of the vote. If you think of this happening in a senate election where each state has 2 senators (and DC none) then you could control 80% of the senate with under 22% of the vote.

There are all sorts of other questions similar to this. What is the smallest block where all the states touch? What is the shortest distance between all her state capitals a winner could have? I think some analysis that included Senate and Congress seats could be interesting. If you have any ideas please comment. * Thanks to Hakan Kjellerstrand who pointed out here I had read the solution file wrong and North Carolina was not present.

/* sets */
set STATES;
set NEED;

/* parameters */
param VotesTable {i in STATES, j in NEED};
param Pop {i in STATES};
param Need {j in NEED};


/* decision variables: x1: alabama, x2: , x3: , x4:  x51: Wyoming*/
      var x {i in STATES} binary >= 0;

/* objective function */
      minimize z: sum{i in STATES} Pop[i]*x[i];

/* Constraints */
s.t. const{j in NEED} : sum{i in STATES} VotesTable[i,j]*x[i] >= Need[j];


/* data section */
data;

set STATES :=  Alaska Delaware "District of Columbia" Montana "North Dakota" "South Dakota" Vermont Wyoming Hawaii Idaho Maine "New Hampshire" "Rhode Island" Nebraska Nevada "New Mexico" Utah "West Virginia" Arkansas Kansas Mississippi Connecticut Iowa Oklahoma Oregon Kentucky "South Carolina" Alabama Colorado Louisiana Arizona Maryland Minnesota Wisconsin Indiana Missouri Tennessee Washington Massachusetts Virginia Georgia "New Jersey" "North Carolina" Michigan Ohio Illinois Pennsylvania Florida "New York" Texas California;
set NEED := Votes;

param VotesTable: Votes:=
 Alabama 9
 Alaska 3
 Arizona 11
 Arkansas 6
 California 55
 Colorado 9
 Connecticut 7
 Delaware 3
 "District of Columbia" 3
 Florida 29
 Georgia 16
 Hawaii 4
 Idaho 4
 Illinois 20
 Indiana 11
 Iowa 6
 Kansas 6
 Kentucky 8
 Louisiana 8
 Maine 4
 Maryland 10
 Massachusetts 11
 Michigan 16
 Minnesota 10
 Mississippi 6
 Missouri 10
 Montana 3
 Nebraska 5
 Nevada 6
 "New Hampshire" 4
 "New Jersey" 14
 "New Mexico" 5
 "New York" 29
 "North Carolina" 15
 "North Dakota" 3
 Ohio 18
 Oklahoma 7
 Oregon 7
 Pennsylvania 20
 "Rhode Island" 4
 "South Carolina" 9
 "South Dakota" 3
 Tennessee 11
 Texas 38
 Utah 6
 Vermont 3
 Virginia 13
 Washington 12
 "West Virginia" 5
 Wisconsin 10
 Wyoming 3;

param Pop:=
Alabama 4802740
Alaska 722718
Arizona 6482505
Arkansas 2937979
California 37691912
Colorado 5116796
Connecticut 3580709
Delaware 907135
"District of Columbia" 617996
Florida 19057542
Georgia 9815210
Hawaii 1374810
Idaho 1584985
Illinois 12869257
Indiana 6516922
Iowa 3062309
Kansas 2871238
Kentucky 4369356
Louisiana 4574836
Maine 1328188
Maryland 5828289
Massachusetts 6587536
Michigan 9876187
Minnesota 5344861
Mississippi 2978512
Missouri 6010688
Montana 998199
Nebraska 1842641
Nevada 2723322
"New Hampshire" 1318194
"New Jersey" 8821155
"New Mexico" 2082224
"New York" 19465197
"North Carolina" 9656401
"North Dakota" 683932
Ohio 11544951
Oklahoma 3791508
Oregon 3871859
Pennsylvania 12742886
"Rhode Island" 1051302
"South Carolina" 4679230
"South Dakota" 824082
Tennessee 6403353
Texas 25674681
Utah 2817222
Vermont 626431
Virginia 8096604
Washington 6830038
"West Virginia" 1855364
Wisconsin 5711767
Wyoming 568158;

param Need:=
Votes        270;

end;

What is the least amount of land that will make you President?

Matthew Yglesias in the slate calculates what he thinks is the smallest area of land a candidate could win and still win this presidential election. Densely populated states will have more electoral college votes per square kilometer and so you can win the election while winning a relatively small surface area of America.
His reasoning is 'I started with a list of states in order of population density. So you have DC, then New Jersey, then Rhode Island, then Massachusetts, and so forth. Eventually you get a set that wins you the electoral college. Except the bloc of the 18 densest states gives you 282 electoral votes—way more than you need. Eliminate Michigan, the 18th densest, and you have 266 electoral votes. So then you can round things out with little New Hampshire's four electoral votes and you have your winning map'.

I checked this allocation with the GLPK program below. I used the electoral votes listed here and the state areas listed on wikipedia This gets 270 votes with an area of 1625012km². US states + DC is an area of 9826630km² so 16.54% of the US could win an election.

The states are Delaware, District of Columbia, Hawaii, New Hampshire, Rhode Island, Connecticut, Maryland, Indiana, Massachusetts, Virginia, New Jersey, North Carolina, Ohio, Illinois, Pennsylvania, Florida, New York, California. My map is here

Matthew Yglesias' map is the same so he did find the optimal solution by hand.

/*code to find the least land area to get 270 votes. Run with 'glpsol -m election.mod -o out'
*/
/* sets */
set STATES;
set NEED;

/* parameters */
param VotesTable {i in STATES, j in NEED};
param Cost {i in STATES};
param Need {j in NEED};


/* decision variables: x1: alabama, x2: , x3: , x4:  x51: Wyoming*/
      var x {i in STATES} binary >= 0;

/* objective function */
      minimize z: sum{i in STATES} Cost[i]*x[i];

/* Constraints */
s.t. const{j in NEED} : sum{i in STATES} VotesTable[i,j]*x[i] >= Need[j];


/* data section */
data;

set STATES :=  Alaska Delaware "District of Columbia" Montana "North Dakota" "South Dakota" Vermont Wyoming Hawaii Idaho Maine "New Hampshire" "Rhode Island" Nebraska Nevada "New Mexico" Utah "West Virginia" Arkansas Kansas Mississippi Connecticut Iowa Oklahoma Oregon Kentucky "South Carolina" Alabama Colorado Louisiana Arizona Maryland Minnesota Wisconsin Indiana Missouri Tennessee Washington Massachusetts Virginia Georgia "New Jersey" "North Carolina" Michigan Ohio Illinois Pennsylvania Florida "New York" Texas California;
set NEED := Votes;

param VotesTable: Votes:=
 Alabama 9
 Alaska 3
 Arizona 11
 Arkansas 6
 California 55
 Colorado 9
 Connecticut 7
 Delaware 3
 "District of Columbia" 3
 Florida 29
 Georgia 16
 Hawaii 4
 Idaho 4
 Illinois 20
 Indiana 11
 Iowa 6
 Kansas 6
 Kentucky 8
 Louisiana 8
 Maine 4
 Maryland 10
 Massachusetts 11
 Michigan 16
 Minnesota 10
 Mississippi 6
 Missouri 10
 Montana 3
 Nebraska 5
 Nevada 6
 "New Hampshire" 4
 "New Jersey" 14
 "New Mexico" 5
 "New York" 29
 "North Carolina" 15
 "North Dakota" 3
 Ohio 18
 Oklahoma 7
 Oregon 7
 Pennsylvania 20
 "Rhode Island" 4
 "South Carolina" 9
 "South Dakota" 3
 Tennessee 11
 Texas 38
 Utah 6
 Vermont 3
 Virginia 13
 Washington 12
 "West Virginia" 5
 Wisconsin 10
 Wyoming 3;

param Cost:=
 Alabama 135765
 Alaska 1717854
 Arizona 295254
 Arkansas 137732
 California 423970
 Colorado 269601
 Connecticut 14357
 Delaware 6447
 "District of Columbia" 177
 Florida 170304
 Georgia 153909
 Hawaii 28311
 Idaho 216446
 Illinois 149998
 Indiana 94321
 Iowa 145743
 Kansas 213096
 Kentucky 104659
 Louisiana 134264
 Maine 91646
 Maryland 32133
 Massachusetts 27336
 Michigan 250494
 Minnesota 225171
 Mississippi 125434
 Missouri 180533
 Montana 380838
 Nebraska 200345
 Nevada 286351
 "New Hampshire" 24216
 "New Jersey" 22588
 "New Mexico" 314915
 "New York" 141299
 "North Carolina" 139389
 "North Dakota" 183112
 Ohio 116096
 Oklahoma 181035
 Oregon 254805
 Pennsylvania 119283
 "Rhode Island" 4002
 "South Carolina" 82932
 "South Dakota" 199731
 Tennessee 109151
 Texas 695621
 Utah 219887
 Vermont 24901
 Virginia 110785
 Washington 184665
 "West Virginia" 62755
 Wisconsin 169639
 Wyoming 253336;

param Need:=
Votes        270;

end;