Category Archive

I’m not a huge college basketball fan, but I am a sucker for statistics and random numbers. To predict my bracket for this year’s NCAA tournament, I wanted to improve upon the technique of a weighted coin prediction based on each team’s standing, so I used the log5 method (HT: Action Allen) to estimate a winning percentage of team A over team B, given each team’s record.

Instead of a single weighted coin flip, though, I ran a random number of trials between 0 and the percent chance of team A losing. For example, if team A has a 90% probability of defeating team B, then the predicted winner will succeed in the best of up to 10 trials, whereas a 50% chance would mean anywhere from 0 to 50 trials. (Python code for the algorithm appears below, where the inputs A and B are the season win percentages of two teams.)

This method is advantageous because it generally favors stronger teams while predicting likely candidates for upsets in the 50-60% range. My bracket predicts Tennessee, Kansas, Memphis, and UCLA in the final four, with Memphis taking it all. I probably won’t watch many of the games, but I’m curious to see how my predictions turn out.

import random

def gamePredict(A, B):
   Agamewin = (A - A*B) / (A + B - 2*A*B)
   Agamelose = 1 - Agamewin

   numgames = random.randint(0, round(Agamelose*100))
   Awincount = Alosecount = 0
   for i in range(0, numgames):
      game = random.random()
      if (Agamewin > game):
         Awincount = Awincount + 1
      else:
         Alosecount = Alosecount + 1

   if (Awincount > Alosecount):
      return True
   elif (Awincount < Alosecount):
      return False
   else:
      return gamePredict(A, B)  # Rematch!

Over a month ago, I entered the first Olympiad of Misguided Geeks, a programming contest where entrants designed simple four-function calculators in the most creative, complex, and contrived ways possible. The winning entries are quite entertaining and interesting, and the rest of the entries have some very clever and convoluted solutions as well. I didn’t win (nor did I expect to), but I had fun creating my entry and have posted it here for posterity.

By the contest rules, a calculator was considered fully functional if it passes the predetermined set of test cases in the correct order. I decided to take advantage of this, so my entry–the Stocalculator–is essentially a calibrated random number generator. If you input the test cases in the correct order during the month of May 2007, you will get the correct results; any other input produces random numbers. (Strictly speaking, all input produces random numbers, but it just so happens that the sequence of random output matches the test cases under a narrow set of conditions.)

The Stocalculator includes a gtk GUI and can be downloaded here. The significant parts of the code are below.

float DoAdd(float op1, float op2) {
   return (float) randseq(randigit());
}

float DoSub(float op1, float op2) {
   static int sign = -1;
   sign *= -1;
   return (float) (randseq(randigit()) * sign);
}

float DoMul(float op1, float op2) {
   return (float) randseq(digitlen((int)op1) + digitlen((int)op2));
}

float DoDiv(float op1, float op2, int *isErr) {
   int numlen;
   double divseq;
   if (op2 == 0) {
      *isErr = 1;
      return -17;
   }
   numlen = randigit();
   divseq = (float) randseq(numlen);
   if (digitlen((int)divseq) < numlen) {
      divseq *= 0.1;
   }
   return divseq;
}

int digitlen(int n) {
   if (n == 0) {
      return 1;
   }
   double len = floor (log10(n)) + 1;
   return (int) len;
}

int randigit(void) {
   static int stocounter = 0;
   static int seeder = 0;
   int seed;
   double seeded;
   if ((stocounter % 8) == 0) {
      seeder++;
      seeded = (seeder - 8.5) / 4.76095228569523;
      seed = (int) round( (round(time((time_t *) NULL) / 1e7)*1e7) * (9.906966206905*pow(seeded,15) + 5.168373047642*pow(seeded,14) - 73.418531365866*pow(seeded,13) - 37.443567190224*pow(seeded,12) + 209.539291108030*pow(seeded,11) + 103.292020775069*pow(seeded,10) - 291.407341342284*pow(seeded,9) - 136.571031185250*pow(seeded,8) + 204.837010407625
*pow(seeded,7) + 89.386899043508*pow(seeded,6) - 66.937774759431*pow(seeded,5) - 26.886181269472*pow(seeded,4) + 7.159451569824*pow(seeded,3) + 2.929885410459*pow(seeded,2) + 0.201212763525*seeded + 0.037897240236));
      srandom(abs(seed));
   }
   stocounter++;
   return (int) (10.0 * ((double)random() / (double)RAND_MAX));
}

int randseq(int len) {
   int i, num = 0;
   for (i=0; i<len; i++) {
      num += randigit() * (int) pow(10, len-i-1);
   }
   return num;
}

I’ve got nothing today, so here’s 1000 random digits. This serves two purposes: 1) it is an interesting way to visualize a set of size 1000, and 2) it may prove to be useful in the future–you never know when random numbers might come in handy. These numbers were generated with the Mersenne Twister generator, for those that care.

9 7 1 4 1 8 5 9 3 7 0 8 8 8 0 9 9 7 6 9 2 0 0 0 4 9 7 3 6 8 3 4 7 3 7 0 4 5 4 4
4 4 9 9 2 9 8 6 4 9 6 7 8 7 2 3 3 5 2 3 9 4 2 0 2 5 4 7 4 5 5 6 8 6 3 3 5 1 0 1
4 8 4 5 7 9 5 9 8 3 4 4 5 1 6 9 4 0 3 3 1 1 3 3 5 9 7 8 0 1 8 5 8 4 1 6 8 0 6 9
5 6 9 4 4 8 7 1 8 3 2 6 5 8 6 5 5 1 2 0 7 4 6 7 3 0 8 7 4 6 2 6 3 4 8 8 7 5 1 1
2 9 7 5 1 6 0 4 3 6 4 9 3 8 8 4 7 0 3 8 0 9 5 6 4 3 6 4 5 4 0 0 1 6 3 1 3 0 8 9
5 9 7 6 3 1 6 7 4 7 9 6 5 8 5 9 9 4 7 4 5 9 1 0 2 3 1 1 9 9 2 8 0 3 0 2 5 4 6 5
7 7 3 4 3 9 4 6 7 4 1 4 2 0 5 7 8 1 2 0 5 4 5 6 1 3 3 6 8 6 8 5 9 5 1 9 4 7 6 6
8 0 8 2 1 2 8 0 1 6 3 1 4 5 6 5 6 7 8 2 6 4 3 4 3 8 7 2 5 3 7 5 5 5 6 0 9 6 2 5
9 6 9 8 9 3 0 1 3 1 5 9 4 9 1 8 7 8 6 9 1 8 0 8 7 0 9 2 7 4 2 7 9 2 9 0 7 2 7 1
6 8 3 1 4 8 1 5 1 9 0 2 9 4 5 8 3 7 0 9 8 8 2 8 1 2 9 9 5 9 7 9 7 3 5 2 4 0 5 5
5 8 8 9 5 8 0 8 7 7 7 6 2 8 4 8 6 7 0 3 8 8 1 9 5 8 1 2 3 8 5 1 0 7 4 8 7 4 3 4
4 9 5 1 8 2 9 6 4 1 8 4 7 7 6 8 6 3 0 1 3 0 1 1 6 8 8 1 4 6 7 1 8 2 1 9 2 2 1 0
8 0 3 0 8 4 2 7 0 6 5 4 0 0 4 8 0 6 1 3 9 2 4 0 4 3 6 4 7 5 0 4 9 6 0 5 0 4 5 5
4 9 6 8 7 8 0 2 1 4 9 2 3 4 7 1 7 0 4 6 4 4 0 6 0 1 9 5 5 6 3 3 4 0 2 1 6 6 1 4
8 4 1 9 7 8 3 3 6 8 8 7 6 0 5 7 7 3 5 3 3 5 1 9 3 3 7 1 5 9 9 3 0 6 5 0 1 2 4 1
1 2 9 2 1 8 1 9 8 4 3 2 3 5 2 2 4 0 9 5 1 0 0 5 4 3 0 0 7 8 4 2 8 1 2 5 9 9 5 2
8 7 2 1 3 0 7 1 1 4 5 4 7 0 0 3 5 9 2 9 5 9 5 7 2 1 9 6 3 2 9 2 4 3 4 8 5 8 1 1
3 2 7 9 7 1 6 4 5 4 5 1 9 0 7 4 0 8 5 4 3 8 6 4 1 3 9 9 7 5 5 2 9 3 9 6 7 5 3 6
9 1 6 3 2 0 6 1 9 8 1 9 2 6 0 0 6 0 2 6 1 2 8 5 8 9 7 7 6 6 8 5 1 9 1 0 7 1 6 1
6 3 5 5 2 0 9 5 1 1 1 4 4 9 6 5 5 2 8 7 5 7 1 5 4 2 4 9 7 4 1 9 9 9 6 1 6 7 3 7
3 4 2 0 1 7 9 4 0 6 2 2 4 1 9 5 5 0 0 6 3 5 9 1 8 9 5 1 0 2 7 9 0 9 9 8 8 5 6 4
9 1 1 6 1 8 8 5 8 1 5 8 2 3 3 7 8 4 7 1 1 7 9 9 6 0 2 5 0 5 5 7 9 4 9 5 4 4 6 7
5 1 7 4 6 8 9 1 0 5 3 7 8 5 9 9 8 7 2 5 4 5 9 7 0 2 4 8 1 3 8 2 5 7 5 4 7 2 1 5
9 6 0 1 9 8 6 3 7 0 3 3 5 0 4 0 7 9 2 6 6 2 0 5 5 5 5 6 2 8 8 3 3 5 1 4 1 7 3 1
0 1 0 1 4 8 9 4 6 3 4 1 2 8 2 7 4 1 4 5 4 7 2 7 4 5 2 9 6 9 7 4 0 7 4 9 6 5 1 4

Yesterday I posted the results of my stochastic Senate predictions. But that got me thinking: what is the purpose of doing a weighted coin flip to aid in prediction of a random event?

Consider two events, A and B. The probability of event A is p(A) and the probability of event B is p(B) = 1 - p(A). Assume p(A) >= p(B). If I want to use a random device to decide whether I should predict the outcome A or B, I could select a weighted coin that chooses event A with probability f. The probability of correctly choosing outcome A is then p(A)*f, and the probability of correctly choosing outcome B is p(B)*(1 - f) = (1 - p(A))*(1 - f). The total probability of success is therefore T = p(A)*[2*f - 1] - f + 1. In other words, my predictive probability is maximized for f = 1 (which gives T = p(A) and is equivalent to not flipping a coin and always selecting A). This probability T is minimized for f = 0 (which gives T = p(B) and is equivalent to not flipping a coin and always selecting B). Thus, the most accurate outcome is gained without the use of a weighted decision-making coin. Furthermore, if such a coin is necessary, it would be beneficial to use a coin that has a higher weight than the actual probabilities (i.e., f > p(A)). What, then, is the advantage of the weighted coin?

If I were to select event A consistently, I would have a higher probability of greater total accuracy, but I would never correctly select the occurrence of event B. Thus, the use of a weighted coin allows for the correct prediction of either A or B as an outcome. How should this weighting be done, though? If we assume that f = p(A), then the probability of successfully predicting A is [p(A)]² and that of predicting B is [p(B)]². If f > p(A) there is a greater probability of correctly predicting A but a lesser probability of correctly predicting B.

Therefore, the weighted coin flip has its use in solving the coupled requirements that both p(A) and p(B) be nonzero and maximized. This does not yield the highest probability of total accuracy, but it allows the prediction of both A and B events while maintaining as much accuracy as possible. Such a technique may prove useful in a March Madness bracket (especially for someone who doesn’t know too much about college basketball).

Yesterday I made some predictions for this year’s Senate races. Let’s see how I did:

Arizona - Jon Kyl* (R)
California - Dianne Feinstein* (D)
Connecticut - Ned Lamont (D)
Florida - Bill Nelson* (D)
Maryland - Ben Cardin (D)
Massachusetts - Ken Chase (R)
Michigan - Mike Bouchard (R)
Minnesota - Amy Klobuchar (D)
Missouri - Claire McCaskill (D)
Montana - Conrad Burns* (R)
Nevada - John Ensign* (R)
New Jersey - Bob Menendez* (D)
Ohio - Sherrod Brown (D)
Pennsylvania - Bob Casey (D)
Rhode Island - Sheldon Whitehouse (D)
Tennessee - Harold Ford (D)
Texas - Barbara Radnofsky (D)
Utah - Orrin Hatch* (R)
Virginia - Jim Webb (D)
Washington - Mike McGavick (R)
West Virginia - John Raese (R)
Wisconsin - Herb Kohl* (D)

Out of 22 predictions, 14 were correct. 64% isn’t too bad, right? I suppose upsets based on predicted probabilities are more common during March Madness than an election, though. So it looks like we succeeded in replacing many of our politicians with other politicians–and that’s progress, right?

Here we have my predictions for today’s Senate races. These predictions are based on data from Polimetrix and my own use of a stochastic device. (* indicates an incumbent.)

Arizona - Jon Kyl* (R)
California - Dianne Feinstein* (D)
Connecticut - Ned Lamont (D)
Florida - Bill Nelson* (D)
Maryland - Ben Cardin (D)
Massachusetts - Ken Chase (R)
Michigan - Mike Bouchard (R)
Minnesota - Amy Klobuchar (D)
Missouri - Claire McCaskill (D)
Montana - Conrad Burns* (R)
Nevada - John Ensign* (R)
New Jersey - Bob Menendez* (D)
Ohio - Sherrod Brown (D)
Pennsylvania - Bob Casey (D)
Rhode Island - Sheldon Whitehouse (D)
Tennessee - Harold Ford (D)
Texas - Barbara Radnofsky (D)
Utah - Orrin Hatch* (R)
Virginia - Jim Webb (D)
Washington - Mike McGavick (R)
West Virginia - John Raese (R)
Wisconsin - Herb Kohl* (D)

That’s 14 seats for the Democrats and 8 for the Republicans. Regardless of the actual election results, I’m looking forward to seeing how accurately my weighted coin flip predictions turn out.

The d20 is an indispensable stochastic device, with the ability to generate random numbers on demand. But what if the need arises to roll a probability that has less than a 1 in 20 chance (i.e., more than 20 options)? For fractions with non-prime denominators, this is straightforward: divide the denominator into equal parts so that each part is less than 20. Then you can compute the value using a the product of a sequence of rolls. For example, to estimate a probability of 1/21, simply realize that 1/21 = 1/7 * 1/3. Roll the d20 once; if you succeed on rolling 1/7, then roll again to see if you get your 1/3 chance. (Remember that it is fine to discard certain numbers if necessary. To roll 1/7, for example, you could use the range 1-14 and discard 15-20.)

Now on to primes. Primes come into play if we need to estimate a value such as 1/37, or if the decomposition strategy outlined above leaves you with a prime denominator, such as 1/46 = 1/2 * 1/23. There is no simple way to obtain an exact value for this type of fraction; however, it is still possible to estimate a value by considering the average of the two probabilities on either side. In other words, to estimate a value for 1/n, where n is a prime number greater than 20, instead use the value (1/2)*[1/(n+1) + 1/(n-1)]. For n = 23, this would mean approximating 1/23 as the sum (1/44 + 1/48). (Note that a probabilistic sum is akin to a logical “or”. In this example, you should roll both the 1/44 and 1/48 probabilities, and if either is true then consider it a success.)

The relative error of this technique is [(n+1)(n-1)]^-1. For the above example of n = 23, the relative error is 0.19%. For larger n, the error decreases; n = 53 has a relative error of 0.036%, and n = 103 has a relative error of 0.0094%. This method is not perfect, but in many cases its accuracy is sufficient. Besides, it is much more convenient to cary around a single d20, as opposed to 1d100 or 2d10–and even then, the same problem would arise for n > 100. So, until someone invents a d(infinity), we have to stay creative.

The Science Creative Quarterly today published my article “Predictability in the Game of War” that I posted here about four months ago. You can read the full text of the article on the SCQ: http://www.scq.ubc.ca/?p=563

The card game of war is typically considered a children’s game, as it requires no skill to play and minimal understanding of playing card relationships in a standard deck. With skill eliminated as a factor in determining the outcome, it is often assumed that war is simply a random game of chance. Yet the game cannot be purely determined by chance, as the initial conditions of the game must have some bearing on the final state. The existence of random factors in the game do not allow for the claim that war is a deterministic game, yet it still possible to quantify properties of the initial state that are indicative of a victory probability. [Continue reading]

Here’s a rare sports-related entry. Baseball is fun for many reasons, one of which is the countless statistics that can be calculated–whether or not they are meaningful. On the walk to work today I thought of a way of assessing a team’s success in making the playoffs: the Cumulative Postseason Stochastic Indicator (CPSI).

If the outcome of all baseball games were randomly determined, then we would expect each team to have a win percentage of 0.500. In a division with D teams, there is thus a 1/D probability of a team winning the division title. There is a 1/D chance of being second in the division, and therefore a 1/D*(2!/3!) probability of claiming the wildcard. Therefore, the probability that a team qualifies for the playoffs in stochastic baseball is SBP = 4/(3D). For the AL Central division, for example, a stochastic team should qualify four out of every fifteen years.

The Cumulative Postseason Stochastic Indicator is a measurement of a team’s record of making the playoffs versus the stochastic probability SBP. Over a time interval T, count the number of times Q a team has made it to the playoffs. The CPSI can then be defined as:

CPSI = (Q/T)/SBP = 3*Q*D/(4*T)

A team has above stochastic performance for CPSI > 1, and below for CPSI < 1. Maximum CPSI over a time interval occurs when Q = T. Let’s look at some values for this year’s AL playoff teams:

Whether or not this statistic is meaningful is left as an exercise for the reader. In any case, go Twins!

The history of science and technology has many instances of discovery by accident: scientists may be measuring a certain object of phenomenon when they accidentally observe something else, leading them to a new finding they had not anticipated. My favorite story of this type is the discovery of the cosmic microwave background radiation by Penzias and Wilson. What they initially thought was noise in their equipment was actually a faint signature of the cosmic fireball.

Accidental discoveries still happen, large and small in scale. But what about random discoveries? In the “olden days” this might have taken the form of walking into a library, picking an arbitrary book off an arbitrary shelf, flipping to an arbitrary page, and happening upon a piece of information that results in the metaphorical light bulb turning on. I would imagine that this type of discovery has not been too common, especially on the larger scale. With the introduction of the Internet, however, it is much easier to obtain random information. Projects like StumbleUpon are not completely random, but they provide a similar function. Furthermore, it would not be difficult to have a random Internet resource emailed once a week, day, hour, or any frequency. Given the large reservoir of information on the Internet, there would certainly be a lot of “useless” information–one would not want to depend on stochastic information searching for research progress. But perhaps the introduction of random knowledge would (does?) lend itself to a few important connections, leading to discoveries and inventions that may not have otherwise occurred.

Let’s try it out: I located a pseudo-random web page using random word and number generators. Everyone likes peach cobbler, right?
http://southernfood.about.com/od/peachcobblers/r/blbb147.htm

As children, most of us learned the game tic-tac-toe. The game was amusing until we solved it–at some point, most children learn the algorithm to force every game to end in a draw. This strategy game then gave way to Connect Four (which is also solvable), checkers (which is mostly solvable), and chess (which is only easily solvable for certain endgames). Checkers (and probably chess) will likely be completely solved in the near future as computing power advances.

After the initial childhood exploration of strategy games, there seems to be two paths to pursue. The first is the deterministic strategy games described above (with either polynomial or exponential complexity). The second is often manifested as a physical sport, but it is characterized by the introduction of non-deterministic elements (such as weather, dice rolls, equipment malfunction, etc.). A game of football may be played with flawless strategy, but because of the nature of the variables involved, a game of football is not computationally solvable. Games of chance (such as gambling) fall somewhere between here. A game of poker or blackjack is not completely deterministic, but with proper strategy it is probabilistically deterministic. So a world-class chess player might be certain of victory at a given place in their game, a world-class poker player would be reasonably assured of victory in all probability, and a world-class football player could only count on victory when the clock or range of scores provided certainty.

As for myself, I plan on learning the game of go in the near future. It falls in the first category described above, but it is exponentially complex. The game has been solved for 3×3 and 4×4 boards, but most people play on 19×19 boards. Sounds like fun.

We are genetically programmed to safeguard our genes. This is not only limited to the genes in our body, but also those of our parents, offspring, siblings, and other family. I have sometimes wondered if our affinity for a particular familial relationship is influenced by the degree of genetic similarity. A parent is always 50% genetically similar to its child. Two siblings, however, can be anywhere from 0% to 100% genetically similar, with a mean of 50%. An uncle and niece will have a mean similarity of 25% in the range [0%, 50%]. Two cousins will have a mean similarity of 12.5% in the range [0%, 50%]. (These values are inclusive of identical twins, exclusive of incest, and assume normal transmission of genes from parent to offspring.) So on average, it is genetically advantageous to have greater affinity to your immediate family than your extended family. Makes sense, right?

But what about that one cousin that you get along so well with? What is the probability that a person is more genetically similar to their cousin than their sibling? I decided to ask my good friend, Monte-Carlo simulation. I whipped up a quick script and ran off one million cases to find the result: there is a 0.64% chance that a person is more genetically similar to their cousin than their sibling.

It’s not terribly likely, but it is a high enough probability that it certainly occurs. I wonder if in these cases there actually is a greater outward affinity toward the cousin as a result of the genetic similarity.

(I should also note that my personal sibling affinity is greater than my cousin affinity, regardless of genetic similarity.)

Whenever I see a globe, I enjoy spinning it around and stopping it randomly with my finger. The place at which my finger lands is then my next travel destination (fictitiously, at least). Without any nearby globes, I decided to script a computerized version of the globe-spin. Below is the resulting destination from my random globe-spin. If you want to make your own globe spins, I have included the Matlab script below. The script requires the M_Map package as well.

rand(’twister’,sum(100*clock));
rlon = -180 + 360.*rand(1,1);
rlat = -90 + 180.*rand(1,1);
lonwidth = 50;
latwidth = 25;
lonmin = rlon-lonwidth;
lonmax = rlon+lonwidth;
latmin = max(rlat-latwidth,-90);
latmax = min(rlat+latwidth,90);

figure
m_proj(’Albers Equal-Area Conic’,'long’,[lonmin lonmax],’lat’,[latmin latmax]);
m_coast(’patch’,[1 .85 .7]);
m_grid(’box’,'fancy’,'tickdir’,'in’);
hold on;
m_plot(rlon,rlat,’or’,'MarkerSize’,8,’MarkerFaceColor’,[1 0 0]);

A thousand monkeys may be able to randomly pound out the works of Shakespeare, but in all probability it would take longer than the age of the Universe. Creationists will often use this line of reasoning as a refutation of evolution, but the evolutionary process–although containing random elements–is not identical to the classic monkey paradox. Instead, it is more akin to a SuperMonkey, which I have coded below in Python for your amusement (and yes, I know the code could be more efficient). SmartMonkey pounds keys at random, but once a character has correctly been entered in its proper place, it is locked there. If you want to run this code, you also need to use this sample-with-replacement method.

A better monkey-model when making an evolutionary analogy, my SmartMonkey pounded out Hamlet in just 1215 iterations (~18 minutes on a dying PIII 750MHz laptop). Even for a slow SmartMonkey, this type of result could certainly be achieved well within an acceptable timeframe.

import random
import sys
import psyco
psyco.full()

if len(sys.argv) < 2:
   text = "My hovercraft is full of eels."
   desc = "Phrase: \"" + text + "\""
else:
   fid = open(sys.argv[1],’r')
   text = fid.read()
   desc = “File: ” + sys.argv[1]

charset = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P', \
'Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f','g','h','i', \
'j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','1','2', \
'3','4','5','6','7','8','9','0','~','!','@','#','$','%','^','&','*','(',')', \
'-','_','+','=','[', '{',']‘,’}',’\\’,'|’,':’,';’,'\”‘,’\”,’,',”, \
‘/’,'?’,’ ‘,’\n’,'\r’]
test = range(1,len(text)+1)
itercnt = 0

print desc
print “SmartMonkey is pounding the keyboard…”
while sum(test) != 0:
   monkey = sample_wr(charset,len(text))
   for i in range(0,len(text)):
      if monkey[i] == text[i]:
         test[i] = 0
   itercnt = itercnt + 1
print “Number of iterations:”, itercnt

Here’s the output of a quick script I hacked together. Glancing at my keyboard, I created three sets of emoticon “eyes”, “noses”, and “mouths” to generate a set of smileys. No need to thank me.

06-29-06 Update: Added one set of eyes, one nose, and four mouths.

10-09-07: Instead of reformatting this entry for WordPress, I’m just going to keep a link to the original Livejournal entry.

For all those times when you forget the value of pi but just so happen to have a twenty-sided die (d20), here’s a simple way to do the calculation:

1) Roll 2d20 (roll the twenty-sided die twice)
2) If the sum of the two rolls is less than 27, or if you rolled double 20’s, count this as a success
3) Repeat this process n times, keeping a cumulative total of the number of successes

Pi = 4 * [# of successes] / [n]

Aren’t you glad you carry that d20 in your pocket?

Appraise war in terms of the fundamental factors. –Sun Tzu

The card game of war is typically considered a children’s game, as it requires no skill to play and minimal understanding of playing card relationships in a standard deck. With skill eliminated as a factor in determining the outcome, it is often assumed that war is simply a random game of chance. Yet the game cannot be purely determined by chance, as the initial conditions of the game must have some bearing on the final state. The existence of random factors in the game do not allow for the claim that war is a deterministic game, yet it still possible to quantify properties of the initial state that are indicative of a victory probability.

The Rules of War
The traditional game of war uses a standard 52-card deck of playing cards divided evenly and randomly between two players. Neither player is allowed to view their hand or rearrange it. The players simultaneously reveal the top card of their deck on the table, and the player with the higher value takes all cards on the table. Cards won from a particular trick are gathered and added to the bottom of the victor’s deck. Suits are disregarded in war, making it an ideal game for exposing young players to concepts of inequality. If both players reveal cards of equal value, a war commences: each player plays two face-down cards on the table and reveals a third card that decides the victor. It is possible to play two, three, or more iterations of a war before the revealed cards are not equal, but in most cases one iteration will suffice to decide the outcome. The victor gains all cards played in the war, including those played face-down. This is the only way in which a player may capture an opponent’s aces. A player loses the game when all of their cards have been captured or exhausted.

Variations in the game of war include varying the number of face-down cards in a war to one, three, a random value, or a plethora of other dependencies. The other major variation consists of placing all cards won from tricks in a separate pile until the player’s deck is extinguished. These cards are then shuffled and used to continue the game. None of these variations is significant enough to differ from the standard rules above when considering a long term analysis. Other variations of war exist in plenty, but most of these have additional rules that warrant their classification as a different game.

Collecting Game Statistics
A computer simulation of war provides a robust and rapid method for examining deterministic tendencies of the game. This simulation used the Mersenne twister random number generator, which has a period much greater than is required for an analysis of this magnitude. Ten million games of war generated a set of three characteristics. The first, and most obvious, statistic is victory. One might guess that in lieu of any deterministic factors, the outcome of a game of war would be no different than tossing a coin. Two other values were also calculated based on a player’s starting hand: deck weight and initial advantage.

Deck weight is a measure of the relative strength of a player’s starting 26 cards. Given that there are 13 different numerical card values (two through ace), define the weight of the card with numerical value 8 to be 0. Defined as such, the cards {9, 10, J, Q, K, A} would have weights of {1, 2, 3, 4, 5, 6} respectively, and likewise the cards {2, 3, 4, 5, 6, 7} would have respective weights of {-6, -5, -4, -3, -2, -1}. The deck weight is then defined as the sum of the weights of a player’s initial 26 cards. The weight of an entire 52 card deck is 0, as would be the case for each player in a perfectly divided game of war (for example, one player is dealt all the reds while the other all the blacks). In a game not so evenly divided, the weight of one player’s deck is equal to the opposite of the other player’s deck (since the weight of the entire 52 cards must vanish). The maximum possible deck weight for a player is 84, which would ensure certain victory. In general, a large dec
k weight may be indicative of a player’s advantage over their opponent, at least concerning card values.

While the deck weight may suggest a certain type of advantage, the ordering of the cards in war is equally important. The initial advantage is defined for a player as the number of tricks won minus the number of tricks lost, over the first iteration through their deck. If no wars occur in the first 26 cards of play, it would be expected on average for a player to have an initial advantage of 0. The maximum initial advantage of 26 would give a player sure and swift victory. For any particular game, a player with a large initial advantage will be in possession of a majority of the cards once all initial 26 have been played. After this point, though, the random element of placing cards won at the bottom of a player’s deck renders the initial advantage measurement useless any further prediction. At best, it is an indicator of the depedence of final victory on the initial ordering of the cards.

Simulation Results
The average cases for both statistics are as expected: the mean deck weight and mean initial advantage are both 0, with both statistics normally distributed about a mean of zero at a 99% confidence level. Deck weight is distributed with a standard deviation of 13.62 and initial advantage with a standard deviation of 4.69. It is interesting to note that even with 10 million games, the maximum and minimum values of the weight and initial advantage did not occur once. Of course, these states are also highly improbable. Neither histogram corresponds exactly to the normal distribution, but the agreement is well within acceptable statistical significance.

Figures 1 and 2 are plots of the probability of victory versus deck weight and initial advantage, respectively. The relationship between deck weight and victory shown in figure 1 is clearly linear, at least for a deck weight between -40 and 40 (or 3?). At magnitudes greater than 40, the number of sample games decreases sharply allowing the bounds on the victory probability to be less constrained. Fitting a line to this data with linear least-squares yields the equation p(W) = (7.67e-03)*W + 0.504, where W is the deck weight and p(W) is the probability of victory. This line fits the data with a correlation of R² = 0.994. With a deck weight W = 0, the probability of victory is nearly 50% as expected. Although on average a player will win and lose an equal number of games, predictability is possible once the deck weight is determined. The probability of victory improves to 60%, 70%, and 80% respectively for deck weights one, two, and three, standard deviations from the mean.

Figure 1: Victory probability versus deck weight with linear regression.

Figure 2: Victory probability versus initial advantage with linear regression.

The relationship between initial advantage and victory is illustrated in figure 2. This trend is even more markedly linear than figure 1, with no points significantly deviant from a linear regression. This can be attributed to the smaller range of values (-26 to 26) of initial advantage compared with deck weight. The fit linear relationship between these two variables is p(A) = (8.08e-03)*A + 0.500, where A is the initial advantage and p(A) is the probability of victory. This line fits the data with R² = 0.999, even better than the relationship in figure 1. For this statistic, the victory probabilities at one, two, and three standard deviations from the mean are 54%, 58%, and 61%. Though the relationship is apparent between A and p(A), the degree to which initial advantage is useful in prediction is low. An initial advantage of 26 would win the game automatically, but a slightly lesser value of 24 does not even win 70% of the time. Prediction based on initial advantage seems to be of higher risk and lesser certain
ty.

Deck weight is a useful indicator of victory probability, and is easily obtained by keeping a cumulative total of the weight as the first 26 cards are played. However, the question of applicability now comes into focus: the weight of the deck is only known after play has begun. Perhaps the cunning player could casually make a friendly wager once they discover their own advantage. Or, those slight of hand could stack the deck in their favor enough to tip the balance–but not enough that suspicions are aroused. But of course, fair game play is always the best course of action. Perhaps the ability to impress an opponent by making an early prediction will suffice, as we sing with Edwin Starr: War. Huh. Yeah. What is it good for? Absolutely nothing!

Last week marked the first time I was involved in the purchase of a lottery ticket (Powerball, of course). And, of course, we didn’t win with our five dollar investment. Maybe it’s because I didn’t actually watch the Powerball drawing, but playing the lottery seems to be lacking the “rush” of true gambling. Personally, I love anything that involves random numbers in some way, from poker to Monte Carlo integration. But Powerball just doesn’t have the same satisfaction as any other game of chance. But then again, I’ve never won Powerball either. I suppose if I won the jackpot, I would indeed get a rush bigger than turning over a full house at a $2-$4 table. Even so, I’m still trying to figure out if it’s worth playing Powerball when the jackpot is giving pot odds. I’ll play any poker hand when I get odds. I’ll even make bets based on coin flips or the birthday paradox given odds (and a sufficient bankroll). But playing the odds implies multiple chances, which really becomes a long-term investment. So unless I achieve near-immortality, you probably won’t see me with too many more Powerball tickets.