I'm Off to Monte Carlo
The whole issue with random events and random numbers is that their complete unpredictability should make them completely useless when it comes to the field of mathematics in which everything is rigorous and precise. So it may come as a massive surprise to find out that random numbers can help us solve otherwise "impossible" mathematical problems, compute definite integrals that would be almost impossible by any other means, and can even be used to accurately give the value of pi simply by throwing darts at a beer mat! Amazed? Let's take a trip to Monte Carlo to find out.
Actually, no, a far better idea is to set our time machine to travel to Los Alamos sometime around 1946 where a Polish man in his late 30s is recuperating from a recent operation. To pass the time, he is playing solitaire. (Note: for British readers, by "solitaire" I don't mean the game played with wooden pegs, but the card game often called "patience" in Britain. As in the old PC game "Microsoft Solitaire". As this article is intended for an international audience, I'll stick with the American term "solitaire") To be historically precise, the game he is playing is indeed rather like the Microsoft Solitaire version (also known as "Klondike") but has slightly different rules (the "Canfield" version), but that need not concern us here.
Despite his relatively young age, Stanislaw "Stan" Uslaw has already had quite an interesting life. Born in Lviv in what was then Austria-Hungary, now the Ukraine, he obtained his PhD there before being poached to work at Princeton, then Harvard, then becoming professor of the university of Wisconsin-Madison before being poached again to work on the Manhattan Project to develop the atom bomb in World War 2.
As he shuffles the cards to deal another game, his fertile mind is wondering: what percentage of solitaire games actually go all the way to a successful completion? It should, he thinks, be theoretically possible to calculate it using some mathematical theorems involving probability and come up with an answer. As he is a professor in Mathematics, with probability and statistics as a particular speciality of his, he decides to have a go at working it out, after all, if he can't do it with his academic background, probably nobody can.
Alas, after spending quite some time on the thorny problem, he is nowhere near a solution. Not surprisingly - the number of permutations of a standard deck of cards is 52 factorial - roughly an '8' followed by 67 zeros. To put that into perspective, the age of the universe in seconds since the Big Bang is - 'only' - a '4' followed by 17 zeros. But, he's never been beaten by a mathematical problem yet, and he doesn't intent to get beaten now.
He contemplates a radical alternative. Instead of trying to solve it using complicated mathematical theorems involving permutations and probability, why not just simply play the game a hundred times and see how many times out of a hundred the game goes through to completion. It won't be a precise answer, of course, but if the hundred games are a reasonable sample of all the trillions of combinations, then the answer will not be far off.
After his recovery, he was back at work where he discussed his experience with his fellow workmates working at Los Alamos, and wondered if the massively recently built ENIAC computer could be used to crunch through huge numbers of scenarios to solve problems in nuclear physics in a much larger scale but similar concept to how he had solved the problem of his game of solitaire. Because he was working on secret projects, they decided to give it a secret code name and because the concept was based on probabilities and chance they called it the "Monte Carlo" method after the French town famous for its casinos. It is a little surprising that they didn't call it the "Las Vegas" method, as Las Vegas was not too far from where they were working, already had a history of connections with atomic development, and at that era was undergoing expansion of its casino businesses. Maybe it was just a bit too close to home, and in any case, Stanislaw Ulam's uncle had apparently been infamous within the family for being an extremely serious devotee of gambling in Monte Carlo.
Let's give the technique a try out on a problem and see what happens. First, let me pose a problem to be solved:
Given a randomly shuffled standard deck of 52 cards, what is the probability that one pair - and one pair only! - of adjacent cards have the same value?
To try and work through this using the usual techniques of probability would be a nightmare. Working out the probability of having at least one consecutive pair is not too bad (you can have a go as a separate exercise) but trying to rule out all the occasions where there is more than one consecutive pair soon turns into a brain melt.
Alternatively, as this is a computational mathematics site, let's write a computer program to do it. Here's one in Javascript I wrote. I chose Javascript as it's pretty much universally understood and you can run it in your browser without downloading any additional dependent software. If you fancy a go at re-writing it in Python or C or Java or any language of your choice, have a go and see how your results compare to mine. Without more ado, here's the code:
<HTML>
<SCRIPT>
// the function below randomly shuffles an array
// taken from a function at w3resource.com to save
// reinventing the wheel
function shuffle(the_array) {
ctr = the_array.length;
// while there are elements in the array
while (ctr > 0) {
// pick a random index
index = Math.floor(Math.random() * ctr);
// decrease ctr by 1
ctr--;
// and now swap the last element with it
temp = the_array[ctr];
the_array[ctr] = the_array[index];
the_array[index] = temp;
}
return the_array;
}
// the deck of cards is set up as an array
// we do not need to worry about suits as it is only the // values that count
deck_of_cards = [1,2,3,4,5,6,7,8,9,10,11,12,13,1,2,3,4,5,6,7,8,9,10,11,12,13,1,2,3,4,5,6,7,8,9,10,11,12,13,1,2,3,4,5,6,7,8,9,10,11,12,13];
// edit the line below to increase or decrease the number of goes
number_of_goes = 1000;
successful_goes = 0;
for (n=0; n<number_of_goes; n++) {
// shuffle the deck
deck_of_cards = shuffle(deck_of_cards);
adjacent_matches = 0;
// now go through the deck starting at the top looking for adjacent cards with the same value
for (card=0; card<=51; card++) {
if (deck_of_cards[card] == deck_of_cards[card+1]) {
adjacent_matches++;
}
}
if (adjacent_matches == 1) {
successful_goes++;
}
}
probability = (successful_goes/number_of_goes);
document.write(probability);
</SCRIPT>
</HTML>
So what were the results? After 100 goes, the probability came out at 0.14 - after 100 goes it was 0.138 and after a million goes it had stabilised at around 0.144 to 3 decimal places. So, if we're after a practical, working figure rather than a mathematically precise one, then we can reasonably say it will happen about 14% of the time.
Now, prepare for something even more amazing and something you can actually try out at home using nothing more than a beer mat, some compasses and a set of darts. We are going to use these humble implements to accurately calculate the value of pi!!
To start, take a piece of cardboard beer mat which should be about four or five inches square. Then, using some compasses, draw a quarter of a circle from the bottom left hand corner to divide the beer mat into two areas as in the diagram below.
Now, fix the beer mat to a wall several feet away (better darts players should use a further distance than mediocre players like me) and repeatedly throw darts at the beer mat until you've thrown about 100 darts. To get a good result, the darts should land randomly inside the beer mat. If you're not a great darts player, like me, this is very easy to achieve. If you're a hot darts player who can group darts very accurately, then you'll need to make it harder for yourself by placing the beer mat further away until you're hitting the beer mat in a random place each time.
Now, remove the beer mat from the wall, and count the number of holes in the beer mat in area A and the number of holes in area B.
Calculate the number A/(A+B) and then multiply this number by 4.
When I tried, there were 80 darts in area A and 24 in area B which meant there were 104 holes in the beer mat altogether. 80 divided by 104 is 0.769 and multiplying this by 4 gives us 3.08 - which is actually not a bad estimate for pi - an error of about 2%!
Now okay, astronomers in the 6th century BC were using values of pi with similar margins of error. But we got our results with one person, a set of darts and a beer mat! Now imagine (if you had nothing much else to do one evening) taking ten beer mats and doing the exercise ten times, then at the end using the cumulative totals across all the beer mats and - well, I didn't do it because at the time of writing I had more pressing things, but if anyone does do it, please let me know how accurate your results were.
As to how it works is quite simple: if we say the beer mat has a side of unit length, then the area of the quarter circle is pi/4. If the darts land randomly in the mat, then the ratio of number of darts in the quarter circle to number of darts in the whole mat is pi/4 to one.
Want to have a go at doing it another way? Then you can, using nothing more than a room with a floor with wooden floorboards or laminate flooring and a box of matches. This one is very simple to implement - just open the box of matches and scatter them randomly on the floor!
The experiment itself goes by the name of "Buffon's needles", named after Georges-Louis Leclerc, Comte de Buffon who allegedly thought it up. Whether or not he actually did it as a real experiment or whether it was just a "thought" experiment is unclear, however if you are going to try it for real, I strongly recommend matches rather than Leclerc's suggestion of needles, as they are a lot easier to see and a lot less painful if you accidentally tread on one! (Historical note: Leclerc lived in the 18th century and matches as we know them didn't become popular until the 19th century, so he can be excused)
Anyway, when all the matches have landed (and they each need to land in a random orientation!) then you need to count the number of matches which cross a line on the floor between floorboards or strips of laminate, and those number of matches which have landed entirely within a board or strip of laminate. You will then also need to measure the length of a match (assuming they are all roughly the same length to within a negligible tolerance) and also the width of your floorboards.
Here's a picture with just 6 matches on it, in which 2 are contained within the width of a board and 4 are lying across two boards. It actually doesn't matter if the matches are longer or shorter than the width of a board, but it does make the calculations rather easier if the width of a match is less than the width of a board.
The probability of a match landing to fall across two boards is a function of (1) The relative length of the match to the width of the floorboard and (2) The orientation which it lands in, and for this we will assume that all angles between 0 and 360 degrees are equally probable. I'll cut out the detailed maths to save space, but it's quite straightforward and you can look it up on Wikipedia. To cut to the chase, the probability P that a match will cross a line is given by
P = 2L/(t X pi) where L is the length of a match and t is the width of a floorboard.
Rearranging this and substituting gives us this equation in terms of pi as follows:
pi = 2NL/th
- where N is the total number of matches dropped, L is the length of a match, t is the width of a floorboard and h is the number of matches that cross a line.
The picture shown on Wikipeda (by McZusatz - Own work, CC BY-SA 3.0) shows 17 matches yielding a value of pi = 3.1 which is not bad at all.
It's an easy experiment you can try for yourself, or again - given that this is a computational mathematics page - have a go at writing a computer program to simulate throwing 1000 matches.
Like this:
<HTML>
<SCRIPT>
// set the width of the boards equal to twice the length // of a match
// it can be any ratio, but this one makes the final
// formula easy
matchlength = 1;
boardwidth = 2;
// edit the line below to increase or decrease the number // of goes
number_of_goes = 100000;
match_crosses = 0;
// consider with no loss of generality that all matches // land in a North-East to South-West direction
for (n=0; n<number_of_goes; n++) {
// the orientation the match lands in
orientation = Math.floor(Math.random() * 90);
// the x-coordinate of the LEFT HAND SIDE of where it lands
// after x=2, the pattern repeats itself
xleft = Math.random() * 2;
// the y-coordinate is irrelevant
// now calculate xRIGHT
// the javascript function uses radians rather than degrees
xright = xleft + Math.cos(orientation*0.0174533);
// if xright > 2 then it has crossed over onto the next floor board
if (xright > 2) {
match_crosses++;
}
}
// because of the lengths of the matches and widths of
// boards we chose, this formula is easy
pi = number_of_goes/match_crosses;
document.write(pi);
</SCRIPT>
</HTML>
Again - not bad!! 100 iterations yielded pi = 2.8 and 1000 iterations yielded 3.125. And it saved a lot of bending down and picking up matches!
That's enough for now for what's intended to be just a short, fun introductory article. To find out more please follow us on Facebook at the P vs NP page at https://www.facebook.com/pversusnp/