Calculating Pi (when you’re ill)

So, I’ve not been well lately. And because a few days lying on my back with insufficient mental stimulation is a quick route to insanity for me, I’ve been trying to spend my most-conscious moment doing things that keep my brain ticking over. And that’s how I ended up calculating pi.

Dan, shortly before inpatient admission but already recovering from the worst parts of his hospital visit, last week.
When I say I’ve been unwell, that might be an understatement. But we’ll get to that another time.

Pi (or π) is, of course, the ratio of the circumference of a circle to its diameter, for every circle. You’ll probably have learned it in school as 3.14, 3.142, or 3.14159, unless you were one of those creepy kids who tried to memorise a lot more digits. Over the years, we’ve been able to calculate it to increasing precision, and although there’s no practical or theoretical reason that we need to know it beyond the 32 digits worked out by Ludolph van Ceulen in the 16th Century, it’s still a fascinating topic that attracts research and debate.

Graph illustrating the calculation of digits of pi over the millenia. Note the logarithmic scale on the left and the staggered scale on the bottom axis.
Our calculation of pi has rocketed since the development of the digital computer.

Most of the computer-based systems we use today are hard to explain, but there’s a really fun computer-based experimental method that can be used to estimate the value of pi that I’m going to share with you. As I’ve been stuck in bed (and often asleep) for the last few days, I’ve not been able to do much productive work, but I have found myself able to implement an example of how to calculate pi. Recovery like a nerd, am I right?

A "pi pie", from a Pi Day celebration.
Pi goes on forever. Pie, sadly, comes to an end.

Remember in school, when you’ll have learned that the formula to describe a circle (of radius 1) on a cartesian coordinate system is x2 + y2 = 1? Well you can work this backwards, too: if you have a point on a grid, (x,y), then you can tell whether it’s inside or outside that circle. If x2 + y2 < 1, it’s inside, and if x2 + y2 > 1, it’s outside. Meanwhile, the difference between the area of a circle and the area of a square that exactly contains it is π/4.

A circle of radius 1 at the intersection of the axes of a cartesian coordinate system.
Think back to your school days. Ever draw a circle like this? Do the words “Cartesian coordinates” ring any bells?

Take those two facts together and you can develop an experimental way to determine pi, called a Monte Carlo method. Take a circle of radius 1 inside a square that exactly contains it. Then randomly choose points within the square. Statistically speaking, these random points have a π/4 chance of occurring within the circle (rather than outside it). So if we take the number of points that lie within the circle, divide that by the total number of points, and then multiply by 4, we should get something that approaches the value of pi. You could even do it by hand!

Output of Dan's demonstration of the Monte Carlo method as used to approximate the value of pi.
I wrote some software to do exactly that. Here’s what it looks like – the red points are inside the circle, and the black points are outside.

The software illustration I’ve written is raw JavaScript, HTML, and SVG, and should work in any modern web browser (though it can get a little slow once it’s drawn a few thousand points!). Give it a go, here! When you go to that page, your browser will start drawing dots at random points, colouring them red if the sum of the squares of their coordinates is less than 1, which is the radius of the circle (and the width of the square that encompasses it). As it goes along, it uses the formula I described above to approximate the value of pi. You’ll probably get as far as 3.14 before you get bored, but there’s no reason that this method couldn’t be used to go as far as you like: it’s not the best tool for the job, but it’s super-easy to understand and explain.

Oh, and it’s all completely open-source, so you’re welcome to take it and do with it what you wish. Turn off the graphical output to make it run faster, and see if you can get an accurate approximation to 5 digits of pi! Or slow it down so you can see how the appearance of each and every point affects the calculation. Or adapt it into a teaching tool and show your maths students one way that pi can be derived experimentally. It’s all yours: have fun.

And I’ll update you on my health at some other point.

Non-transitive Games

Non-transitive dice

Have you ever come across non-transitive dice? The classic set, that you can get in most magic shops, consists of three different-coloured six-sided dice:

A "Grimes" style set of 3 non-transitive dice. Notice the unusual numbering.
A “Grime’s” style set of 3 non-transitive dice. Notice the unusual numbering.

There are several variants, but a common one, as discussed by James Grime, involves one die with five “3” sides and one “6” side (described as red below), a second die with three “2” sides and three “5” sides (described as green below), and a third die with one “1” side and five “four” sides (described as blue below).

They’re all fair dice, and – like a normal six-sided dice – they all have an average score of 3.5. But they’ve got an interesting property, which you can use for all kinds of magic tricks and gambling games. Typically: the red die will beat the green die, the green die will beat the blue die, and the blue die will beat the red die! (think Rock, Paper, Scissors…)

Red beats Green beats Blue beats Red.
Seemingly paradoxically, the dice will generally beat one another in a circular pattern.

If you want to beat your opponent, have them pick a die first. If they pick green, you take red. If they take red, you take blue. If they take blue, you take green. You now have about a 60% chance of getting the highest roll (normally you’d have about a 33% chance of winning, and a 17% chance of a draw, so a 60% chance is significantly better). To make sure that you’ve got the best odds, play “best of 10” or similar: the more times you play, the less-likely you are to be caught out by an unfortunate unlucky streak.

But if that doesn’t bake your noodle enough, try grabbing two sets of nontransitive dice and try again. Now you’ll see that the pattern reverses: the green pair tends to beat the red pair, the red pair tends to beat the blue pair, and the blue pair tends to beat the green pair! (this makes for a great second act to your efforts to fleece somebody of their money in a gambling game: once they’ve worked out how you keep winning, give them the chance to go “double or nothing”, using two dice, and you’ll even offer to choose first!)

Double Red beats Double Blue beats Double Green beats Double Red
When you pair up the dice, the cycle reverses! While red beats green, double-green beats double-red!

The properties of these dice – and of the more-exotic forms, like Oskar van Deventer’s seven-dice set (suitable for playing a game with three players and beating both of your opponents) and like the polyhedral varieties discussed on Wikipedia – intrigue the game theorist and board games designer in me. Could there be the potential for this mechanic to exist in a board game? I’m thinking something with Risk-like combat (dice ‘knock out’ one another from highest to lowest) but with a “dice acquisition” mechanic (so players perform actions, perhaps in an auction format, to acquire dice of particular colours – each with their own strengths and weaknesses among other dice – to support their “hand” of dice). There’s a discussion going on in /r/tabletopgamedesign

I’ve even written a program (which you’re welcome to download, adapt, and use) to calulate the odds of any combination of any variety of non-transitive dice against one another, or even to help you develop your own non-transitive dice sets.

Penney’s game

A coin being flipped.
Heads or tails? Image courtesy David M. Diaz.

Here’s another non-transitive game for you, but this time: I’ve made it into a real, playable game that you can try out right now. In this game, you and I will each, in turn, predict three consecutive flips of a fair coin – so you might predict “tails, heads, heads”. Then we’ll start flipping a coin, again and again, until one of our sequences comes up. And more often than not, I’ll win.

[button link=”https://danq.me/penney/” align=”center” size=”large” caption=”Click here to play a non-transitive coin game.”]Play “Penney’s Game”[/button]

If you win 10 times (or you lose 20 times, which is more likely!), then I’ll explain how the game works, so you know how I “cheated”. I’ll remind you: the coin flips are fair, and it’s nothing to do with a computer – if we played this game face-to-face, with a real coin, I’d still win. Now go play!

Lucy’s Birthday

The other Three Ringers and I are working hard to wrap up Milestone: Jethrik, the latest version of the software. I was optimising some of the older volunteer availability-management code when, by coincidence, I noticed this new bug:

Lucy 173's birthday is in 13/1 days.
Well, at least she’s being rational about it.

I suppose it’s true: Lucy (who’s an imaginary piece of test data) will celebrate her birthday in 13/1 days. Or 13.0 days, if you prefer. But most humans seem to be happier with their periods of time not expressed as top-heavy fractions, for some reason, so I suppose we’d better fix that one.

They’re busy days for Three Rings, right now, as we’re also making arrangements for our 10th Birthday Conference, next month. Between my Three Rings work, a busy stretch at my day job, voluntary work at Oxford Friend, yet-more-executor-stuff, and three different courses, I don’t have much time for anything else!

But I’m still alive, and I’m sure I’ll have more to say about all of the things I’ve been getting up to sometime. Maybe at half term. Or Christmas!

Update: Squee! We’ve got folders!

 

Suppose you have a time machine that can only jump to leap days. What’s the chance that a random jump will put you on a Monday? [Maths]

This link was originally posted to /r/puzzles. See more things from Dan's Reddit account.

Here’s a puzzle for you –

Like the TARDIS, your time machine has a fault.
Like the TARDIS, your time machine has a fault. The fault isn’t a failure of its chameleon circuit, but a quirk in its ability to jump to particular dates. Picture courtesy aussiegall (Flickr), licensed Creative Commons.

You own a time machine with an unusual property: it can only travel to 29th February. It can jump to any 29th February, anywhere at all, in any year (even back before we invented the Gregorian Calendar, and far into the future after we’ve stopped using it), but it can only finish its journey on a 29th of February, in a Gregorian leap year (for this reason, it can only jump to years which are leap years).

One day, you decide to take it for a spin. So you get into your time machine and press the “random” button. Moments later, you have arrived: it is now 29th February in a random year!

Without knowing what year it is: what is the probability that it is a Monday? (hint: the answer is not 1/7 – half of your challenge is to work out why!).

Dan Q

The Leap Machine (Puzzle)

Here’s a puzzle for you –

Like the TARDIS, your time machine has a fault.
Like the TARDIS, your time machine has a fault. The fault isn’t a failure of its chameleon circuit, but a quirk in its ability to jump to particular dates. Picture courtesy aussiegall (Flickr), licensed Creative Commons.

You own a time machine with an unusual property: it can only travel to 29th February. It can jump to any 29th February, anywhere at all, in any year (even back before we invented the Gregorian Calendar, and far into the future after we’ve stopped using it), but it can only finish its journey on a 29th of February, in a Gregorian leap year (for this reason, it can only jump to years which are leap years).

One day, you decide to take it for a spin. So you get into your time machine and press the “random” button. Moments later, you have arrived: it is now 29th February in a random year!

Without knowing what year it is: what is the probability that it is a Monday? (hint: the answer is not 1/7 – half of your challenge is to work out why!).

Edinburgh 2012 – Day Five

After our attempt at a relaxing day off, which resulted in us getting pretty-much soaked and exhausted, we returned on day five of our holiday to the comedy scene for more fun and laughter.

Ruth, JTA, Matt and Hannah-Mae outside the Canons' Gait.
Ruth, JTA, Matt and Hannah-Mae outside the Canons’ Gait. Do I win a prize for being the first Abnibber to publish a photo of Matt’s new girlfriend?

After failing to get into Richard Wiseman‘s Psychobabble, which attracted a huge queue long before we got to the venue, Ruth, JTA and I instead went to RomComCon: a two-woman show telling the story of how they road-tested all of the top romantic comedy “boy meets girl” cliché situations, to see if they actually worked in real life. It was sweet, even where it wasn’t funny, and it was confidently-performed, even where it wasn’t perfectly-scripted. The mixture of media (slides, video, audience participation, and good old-fashioned storytelling) was refreshing enough to help me overlook the sometimes-stilted jumps in dialogue. I’ll admit: I cried a little, but then I sometimes do that during actual RomComs, too. Although I did have to say “Well d’uh!” when the conclusion of the presentation was that to get into a great relationship, you have to be open and honest and willing to experiment and not to give up hope that you’ll find one. You know: the kinds of things I’ve been saying for years.

Ruth & JTA in the Voodoo Rooms, waiting for Owen Niblock's "Codemaker" to start.
Ruth & JTA in the Voodoo Rooms, waiting for Owen Niblock’s “Codemaker” to start.Ruth & JTA in the Voodoo Rooms, waiting for Owen Niblock’s “Codemaker” to start.

We met up with Matt and his new girlfriend, Hannah-Mae, who turns out to be a lovely, friendly, and dryly-sarcastic young woman who makes a wonderful match for our Matt. Then, after a drink together, parted ways to see different shows; promising to meet up again later in the day.

"Codemaker" Owen Niblock presents Google Image Search pictures that come up when the search engine is presented with a picture of his wife.
“Codemaker” Owen Niblock presents Google Image Search pictures that come up when the search engine is presented with a picture of his wife. The audience member who’s half-standing didn’t laugh throughout the entire performance: this might not have been the right show for him.

We watched Owen Niblock‘s Codemaker, and were pleased to discover that it was everything that Computer Programmer Extraordinaire (which we saw on day two) failed to be. Codemaker was genuinely geeky (Owen would put up code segments and then explain why they were interesting), funny (everything from the five-months-a-year beard story to his relationship Service Level Agreement with his wife was fabulously-crafted), and moving. In some ways I’m sad that he isn’t attracting a larger audience – we three represented about a quarter to a fifth of those in attendance, at the end – but on the other hand, his computer-centric humour (full of graphs and pictures of old computers) is rather niche and perhaps wouldn’t appeal to the mainstream. Highly recommended to the geeks among you, though!

Ruth discovers a police box and is inordinately excited.
Ruth discovers a police box on the way back to the flat and is inordinately excited. Apparently she’d somehow managed to never see one before.

Back at the flat, we drank gin and played Ca$h ‘n’ Gun$ with Matt and Hannah-Mae. JTA won three consecutive games, the jammy sod, despite the efforts of the rest of us (Matt or I with a hand grenade, Ruth or I as The Kid, or even Hannah-Mae once she had a gun in each hand), and all the way along every single time insisted that he was losing. Sneaky bugger.

Hannah-Mae, Matt, JTA and I with Richard Wiseman.
Hannah-Mae, Matt, JTA and I with Richard Wiseman. JTA was aware that a photo was going to be taken at some point, but was distracted by talking to another comedian, off-camera.

We all reconvened at the afternoon repeat of Richard Wiseman’s show, where he demonstrated (in a very fun and engaging way) a series of psychological, mathematical, and slight-of-hand tricks behind the “mind-reading” and illusion effects used by various professional entertainers. I’ve clearly studied this stuff far too much, because I didn’t end up learning anything new, but I did enjoy his patter and the way he makes his material interesting, and it’s well-worth a look. Later, Ruth and I would try to develop a mathematical formula for the smallest possible sum totals possible for integer magic squares of a given order (Wiseman’s final trick involved the high-speed construction of a perfect magic square to a sum total provided by a member of the audience: a simple problem: if anybody wants me to demonstrate how it’s done, it’s quite fun).

Thom Tuck wants to be where the people are. He wants to see... wants to see them, dancing.
Thom Tuck wants to be where the people are. He wants to see… wants to see them, dancing. Walking around on those… what’s what word again? Seriously: what’s that word again?

Finally, we all went to see Thom Tuck again. Matt, JTA and I had seen him earlier in the week, but we’d insisted that Hannah-Mae and Ruth get the chance to see his fantastic show, too (as well as giving ourselves an excuse to see it again ourselves, of course). He wasn’t quite so impressive the second time around, but it was great to see that his knowledge of straight-to-DVD Disney movies really is just-about as encyclopaedic as he claims, when we gave us new material we hadn’t heard on his previous show (and omitted some that we had), as well as adapting to suggestions of films shouted out by the audience. Straight-To-DVD remains for me a chilling and hilarious show and perhaps the most-enjoyable thing I’ve ever seen on the Fringe.

Monogamy and Mathematics

“We have to split up… in case somebody better comes along!”

Either from our own real life or from popular culture and the media, we’ve all come across a statement like that. It’s rarely quite so brazen: instead, it’s sometimes concealed behind another reason, whether tactful or simply false. But it still reeks of a lack of commitment and an unwillingness to “give it a try.”

With thanks for Flickr user "i.am.rebecca".

However, it turns out that there’s actually a solid mathematical basis for it. Let’s assume for a moment that you:

  1. Engage exclusively in monogamous relationships. To each their own, I suppose.
  2. Are seeking for a relationship that will last indefinitely (e.g. traditional monogamous marriage, “’til death do us part,” and all that jazz).
  3. Can’t or won’t date your exes.
  4. Can rate all of your relationships relative to one another (i.e. rank them all, from best to worst)?
  5. Can reasonably estimate the number of partners that you will have the opportunity to assess over the course of your life. You can work this out by speculating on how long you’ll live (and be dating!) for, and multiplying, though of course there are several factors that will introduce error. When making this assumption, you should assume that you break up from any monogamous relationship that you’re currently in, and that no future monogamous relationship is allowed to last long enough that it may prevent you from exploring the next one, until you find “the one” – the lucky winner you’re hoping to spend the rest of your life with.

Assuming that all of the above is true, what strategy should you employ in order to maximise your chance of getting yourself the best possible lover (for you)?

The derivation of the optimal policy for the secretary problem.

It turns out that clever (and probably single) mathematicians have already solved this puzzle for you. They call it the Secretary Problem, because they’d rather think about it as being a human resources exercise, rather than a reminder of their own tragic loneliness.

A Mathematical Strategy for Monogamy

Here’s what you do:

  1. Take the number of people you expect to be able to date over the course of your lifetime, assuming that you  never “settle down” and stop dating others. For example’s sake, let’s pick 20.
  2. Divide that number by e – about 2.71828. You won’t get a round number, so round down. In our example, we get 7.
  3. Date that many people – maybe you already have. Leave them all. This is important: these first few (7, in our example) aren’t “keepers”: the only reason you date them is to give you a basis for comparison against which you rate all of your future lovers.
  4. Keep dating: only stop when you find somebody who is better than everybody you’ve dated so far.

And there you have it! Mathematically-speaking, this strategy gives you a 37% chance of ending up with the person who – of all the people you’d have had the chance to date – is the best. 37% doesn’t sound like much, but from a mathematical standpoint, it’s the best you can do with monogamy unless you permit yourself to date exes, or to cheat.

Or to conveniently see your current partner as being better than you would have objectively rated them otherwise. That’s what love will do for you, but that’s harder to model mathematically.

Of course, if everybody used this technique (or even if enough people used it that you might be reasonably expected to date somebody who did, at some point in your life), then the problem drifts into the domain of game theory. And by that point, you’d do better to set up a dating agency, collect everybody’s details, and use a Stable Marriage problem solution to pair everybody up.

This has been a lesson in why mathematicians shouldn’t date.

Avatar Diary

Went into college for Pure Maths, and for the first time in 1999, arrived on time (as opposed to one or more hours early)! Went out for tea to McDonalds with my dad and sisters in the evening. Went to my mum’s house, and spent five hours (almost breaking my personal record of 5 hours 27 minutes) on the phone to Fay, and, after failing to go to sleep afterwards, sat up and watched the sunrise before dropping off. If anyone asks about why I was on the phone to her at that time of night, I’ll tell them that I’m running a phone sex line as a way of making extra income. No – that won’t work… It was my call… Hmm… Let me think of an explanation, then…

Andy Heywood attempts to explain Pure Maths

Avatar Diary

Maths in the morning. How is it that the first lesson in a new module always makes so much more sense than any other one? Went home for lunch in my three-hour break, returning for Psychology. Watched a video on “Eyewitness Testimony”. We’ve seen the same one three times now. Alecia took the second half of the lesson to preach to us – usally the kind of activity for Monday’s Psychology lessons – and persuaded Richard and me to come with her to church on Sunday. Promised I’d go, and I think I’ve persuaded Rik too, as well (even though he let her down on the Carol Service). “You can’t knock it ’til you’ve tried it,” I told him, with my usual democratic tact.

Couldn’t sleep again tonight – same as last night – watched TV until about 4:30am…