I remember, as a child, walking up the steps of the Laxey Wheel and thinking "that is a big waterwheel". That was around 25 years ago and just this week I was back at the Laxey Wheel for the first time since. No less fascinating this time around; the sense of childlike wonder at the size of the wheel still intact, but now joined by a sense of the beauty of the 100m long rod, moved by the wheel which in turn moves a rocker, which in turn lifts a rod inside a shaft up and down which was used to pump water out of the mine.

We were due to visit the Isle of Man a year ago exactly, but circumstances conspired to mean that holiday was cancelled at the last minute. So this year, to allow some time to reflect on last year and to relax, we did the same holiday we had planned. It wasn't quite the same holiday - last year we had planned to come over by plane, and stay in Central Douglas with a hire car. This time, we drove from London up to Liverpool (via a few family visits) and took the car ferry across, staying outside Douglas at a hotel with a car park.

The Isle of Man has changed. Even with only my childhood memories to rely on, the place is quieter. There are fewer tourists and there is no bustle of a seaside resort around Douglas which I remember from when I was a kid. With the advent of a financial services industry attracted by zero rate corporation tax and high-earners attracted by the low income tax, it's become a services-led economy.

That said, there's still a few tourists in the Isle Of Man. It's wearing the decline in the tourist trade well - there's no sense of self-pity and whlst nowhere is bustling, there are still a few cars in the car park at every tourist site, so you never feel as though you're on your own.

In my previous visits, I'd always visited with family who didn't drive, and so we were limited by what public transport could offer to/from Douglas on a day-trip. So this trip was the first time I'd ventured to places only accessible by car. When I say "accessible by car" I mean that in its loosest sense; I'm glad we brought the 4x4 with us.

I had expected the scenery to be stunning, and I wasn't disappointed. But I was only expecting the mountain scenery; I wasn't so much expecting the coastline to be so interesting. How can a coastline be interesting, you may say. Thanks to the help of a friend who lives on the Isle of Man, we occassionally headed past the end of the made road and along a bumpy track to a little-known carpark with a geological wonder sat at the end of it.

Along the sealine there was a rocky outcrop made of limestone. Nothing unusual in that. Except this was folded. Across the beach you could easily see how the alternating strata of limestone and mudstone had folded and buckled.

In amongst the grey limestone was a lot of black basalt. Forced up through fissures in the limestone many years ago it protruded from the cracks in the limestone like geological Polyfilla bulging at the surface.

And that's without mentioning the limestone cobbles along the beach filled with fossils...

At Niarbyl, a white line down the cliff face marks the last visible remnant of an Ocean. The Isle of Man is (along with the rest of the British Isles) formed as two tectonic plates push together. The southern half of the Isle of Man, England and Wales used to lie across the Iapetus Ocean from Scotland and the nothern half of the Isle of Man. As the plates moved together, the ocean shrank and at Niarbyl is the only place where the boundary between the two plates is visible above the surface.

The climb up Snaefell is worth it for the view. We went up twice in a day - once by tram when it was literally freezing and enveloped by cloud then walked up from the carpark in the evening when the cloud was thinner and the view was stunningly beautiful.

When arriving into Douglas, there is a strange "toy town" look as you approach the harbour. The appearance is that of a glimpse into the future of Portmeirion. Portmeirion is the village which grew up and became the town of Douglas. Of course, behind the Prom there's an M&S and even a Tesco now - progress can only be halted so far.

The population of the Isle of Man is around 80,000 people. To put that in perspective - you could fit all of them into a large football stadium. You don't need to look at the government figures to see the demographic split either - just a few days looking around the Island will do that for you. There is nobody in their twenties. There are kids, teenagers and families with kids - but all of the young, single adults have taken the boat and haven't come back (yet). It's no real surprise. With the lack of a full university on the island, the only chance for a tertiary education lies a boat-ride away, and few seem to return home straight after university - the bungee cord appears to snap them back either when they are ready to have kids or to retire.

But what a place to retire to. It's impossible to be stressed, or rush when on holiday in the Isle of Man, and that feeling would be a great one to have when retired. I'm sure that when you have an office job in the Isle of Man, the stress is the same as an office job anywhere else, but if you didn't have the daily grind, nothing would be more relaxing that a ten minute drive into the mountains and a breath of fresh air and views across the Irish Sea to England in one direction and Ireland in the other.

Having said that - apparently there is one thing to get stressed over on the Isle of Man. Word of warning - if you a presenter of a popular motoring show on the BBC and have a home in the Isle of Man - don't block off a popular footpath or you'll find that the locals can get very stressed indeed...

My random ramblings about life, maths, trashy TV and anything else which comes to mind...

## Thursday, June 30, 2011

## Sunday, June 26, 2011

### It's not difficult!

Sometimes in life, you see people struggling with things which are easy. I don't mean that you should judge someone harshly for failing to grasp the quickest way to solve a differential equation or not being able to name a Mozart symphony from the first few notes - I mean things which are really not difficult and which form part of every day life.

For instance, there are times in our lives when we are faced with finding a particular seat. On a plane, in the theatre or even on a boat (which is where I am as I write this, as it happens). Usually, you're faced with a ticket which may "23 A" or "Row X, seat 76" on it. If it's really complicated then maybe it will say "STALLS ROW A SEAT 2". But in any of these cases, it's not difficult to find your seat.

Though I often wonder, when sitting in the theatre waiting for the show to start or sitting in my seat on a plane waiting for others to board, whether I have some super-human ability which is rare and which all of the other people trying to find their seats somehow lack. You see people wandering up and down in the aisle of the theatre, looking at their ticket, looking at the seats and looking back at their ticket again. They see the words "Row A" and are bemused by this most mystic and unfamiliar rune. What could it possibly mean? They seem to have a puzzled look on their face as if faced with an impenetrable riddle which they must solve in order to find their seat.

This is a mild source of both bemusement and amusement when it happens before the show starts. I'm usually sitting there staring at a big red curtain clockwatching, so watching the stupid people fail to understand what "ROW V SEAT 19" could possibly mean makes me chuckle. But when it happens just after the show starts, then it makes my blood boil. The most important, scene-setting, part of a show can come just after the curtain goes up. Many any important line is lost in the distraction which is someone being shown how to read a simple grid reference by someone shining around a bright torch in a dark theatre.

On a plane, the only annoyance is when someone has dithered so long about their seat that you've just settled down in your aisle seat, only to have to stand up and disarrange yourself and your things to let them slide past into the window seat. That's not the most annoying thing on planes though.

I tend to get onto the plane early. I do that so I can get my bag into an overhead locker about my seat. And then the arrogant latecomers arrange. These are not the people who sheepishly stroll onto the plane knowing that they have held other people up. These are the men (sorry, no intention to be sexist, but it's always been men) in suits (again, only my experience) who are still talking on their phone, and who stroll onto the plane once everyone else is seated. They are usually carrying cases so large they are only borderline qualifiers for cabin baggage and then they try to get them into the locker.

It's at this point that they seem to think that everything already up there is much less important than their own case. They slide other bags around, even sometimes take them down and move them to other parts of the plane, just so that their own overstuffed case can sit as close as possible to their seat. After all, they couldn't possibly waste a second of their valuable time going to get their bag back from slightly further down the cabin when the plane lands...

But it's not just finding seats which isn't difficult. Why is it that some people think that by pulling a funny face and breathing in a bit, it's possible to walk through them. You notice it when getting off the tube, when getting out of a lift, even when coming out of the toilet in a bar. If you are waiting to go into a door - whatever kind of door - and there are already people behind the door, then generally those people will need to get out before you can get in. So maybe the worst place to stand is directly in front of that door. When getting on the tube, it's just common sense to stand out of the way, but I've noticed something a little more odd when getting out of a lift; the people standing on the outside of the lift usually feel quite affronted that anyone else should be in their lift. You can see the look on their face. A single look which says "I have pressed the button, and so this is MY lift now. What on earth are you doing already in it?" And then, if you're anything like me, you shuffle out with the apologetic gait possible as if to acknowledge that yes - it is their lift now, and I'm terribly sorry for standing in it.

Of course, the other thing which isn't difficult is walking down one flight of stairs rather than taking the lift down to the ground floor from the first. But please. Don't get me started...

For instance, there are times in our lives when we are faced with finding a particular seat. On a plane, in the theatre or even on a boat (which is where I am as I write this, as it happens). Usually, you're faced with a ticket which may "23 A" or "Row X, seat 76" on it. If it's really complicated then maybe it will say "STALLS ROW A SEAT 2". But in any of these cases, it's not difficult to find your seat.

Though I often wonder, when sitting in the theatre waiting for the show to start or sitting in my seat on a plane waiting for others to board, whether I have some super-human ability which is rare and which all of the other people trying to find their seats somehow lack. You see people wandering up and down in the aisle of the theatre, looking at their ticket, looking at the seats and looking back at their ticket again. They see the words "Row A" and are bemused by this most mystic and unfamiliar rune. What could it possibly mean? They seem to have a puzzled look on their face as if faced with an impenetrable riddle which they must solve in order to find their seat.

This is a mild source of both bemusement and amusement when it happens before the show starts. I'm usually sitting there staring at a big red curtain clockwatching, so watching the stupid people fail to understand what "ROW V SEAT 19" could possibly mean makes me chuckle. But when it happens just after the show starts, then it makes my blood boil. The most important, scene-setting, part of a show can come just after the curtain goes up. Many any important line is lost in the distraction which is someone being shown how to read a simple grid reference by someone shining around a bright torch in a dark theatre.

On a plane, the only annoyance is when someone has dithered so long about their seat that you've just settled down in your aisle seat, only to have to stand up and disarrange yourself and your things to let them slide past into the window seat. That's not the most annoying thing on planes though.

I tend to get onto the plane early. I do that so I can get my bag into an overhead locker about my seat. And then the arrogant latecomers arrange. These are not the people who sheepishly stroll onto the plane knowing that they have held other people up. These are the men (sorry, no intention to be sexist, but it's always been men) in suits (again, only my experience) who are still talking on their phone, and who stroll onto the plane once everyone else is seated. They are usually carrying cases so large they are only borderline qualifiers for cabin baggage and then they try to get them into the locker.

It's at this point that they seem to think that everything already up there is much less important than their own case. They slide other bags around, even sometimes take them down and move them to other parts of the plane, just so that their own overstuffed case can sit as close as possible to their seat. After all, they couldn't possibly waste a second of their valuable time going to get their bag back from slightly further down the cabin when the plane lands...

But it's not just finding seats which isn't difficult. Why is it that some people think that by pulling a funny face and breathing in a bit, it's possible to walk through them. You notice it when getting off the tube, when getting out of a lift, even when coming out of the toilet in a bar. If you are waiting to go into a door - whatever kind of door - and there are already people behind the door, then generally those people will need to get out before you can get in. So maybe the worst place to stand is directly in front of that door. When getting on the tube, it's just common sense to stand out of the way, but I've noticed something a little more odd when getting out of a lift; the people standing on the outside of the lift usually feel quite affronted that anyone else should be in their lift. You can see the look on their face. A single look which says "I have pressed the button, and so this is MY lift now. What on earth are you doing already in it?" And then, if you're anything like me, you shuffle out with the apologetic gait possible as if to acknowledge that yes - it is their lift now, and I'm terribly sorry for standing in it.

Of course, the other thing which isn't difficult is walking down one flight of stairs rather than taking the lift down to the ground floor from the first. But please. Don't get me started...

## Friday, June 10, 2011

### Writing in Tippex

Yesterday, I wrote a length about pigeonholes and cats. But did I get carried away? Much as I hate to presume that you've read that post - I don't think this is going to make much sense if you haven't...

I'm not the kind of person who lets a blog post fester and evolve before posting; I'm the kind of person who will write a blog post and stick it up immediately. Publish and be damned.

Having read back yesterday's post, I wrote the following:

"Of course, given so many years, the genes of Henry IV will have spread themselves wide throughout the population and so many of us will be distantly related to him. But the only way to prove that would be to take DNA samples."

I got lost in my own words when writing this and there are two distinct problems with that short assertion.

The first is to suggest that DNA samples would prove relationship to Henry IV. I must put my hand up here and admit that I slipped between the idea of mathematic proof and the common meaning of the word without flagging it up. What I meant of course, was that DNA testing would show that it was either very likely or very unlikely that we were related to Henry IV.

DNA testing is an exact science but that shouldn't be taken to mean that the results are definitite in the pure mathematical sense. Say Henry IV had a particular set of mutations in his DNA which also showed up my DNA. Then the overwhelmingly likely reason is that I am descended from him and this mutations have come to me that. Much less likely - but not impossible - is that exactly the same set of mutations has arisen by chance in a completely separate line and I am not related to Henry IV.

The second problem with my assertion is that I said the "only way to prove..." when talking about DNA testing. There is no way to prove in the mathematical sense that I (or anyone else) is related to Henry IV. (That's an argument for another day, although I can make it rigorous, I promise) there is another way which doesn't involve DNA testing, and gives about as much certain and it's very simple.

Evolution tells us that humans evolved from an ape-like ancestor. At some point in the past there must have been a common ancestor from which all humans are descended. Every human is descended from that ancestor, including Henry IV and so we are all related to Henry IV.

So - I hear you not asking - why isn't that rigorous. The chances of evolution happening twice are very slim. Very slim indeed. But they are not zero. So it's theoretically possible that life began twice, completely indedependently, and in both cases, animals identical to humans evolved and Henry IV is one of those lines and I'm in the other.

At this point, please don't mistake me for some kind of nutter. I'm not. Obviously evolution of humans hasn't happened in parallel twice on earth. But the point is that the chances of it happening are not zero, and so we can't say in the mathematical sense that we have proved it didn't happen - even if we have shown beyond reasonable doubt that it didn't. But note that there isn't a pigeonhole - abstract or otherwise - in sight.

One footnote here is to note that we can easily show - beyond reasonable doubt - that we are all related to Henry IV but not that we are descended from him directly.

And that's why I like to write things in Tippex - they correct themselves...

I'm not the kind of person who lets a blog post fester and evolve before posting; I'm the kind of person who will write a blog post and stick it up immediately. Publish and be damned.

Having read back yesterday's post, I wrote the following:

"Of course, given so many years, the genes of Henry IV will have spread themselves wide throughout the population and so many of us will be distantly related to him. But the only way to prove that would be to take DNA samples."

I got lost in my own words when writing this and there are two distinct problems with that short assertion.

The first is to suggest that DNA samples would prove relationship to Henry IV. I must put my hand up here and admit that I slipped between the idea of mathematic proof and the common meaning of the word without flagging it up. What I meant of course, was that DNA testing would show that it was either very likely or very unlikely that we were related to Henry IV.

DNA testing is an exact science but that shouldn't be taken to mean that the results are definitite in the pure mathematical sense. Say Henry IV had a particular set of mutations in his DNA which also showed up my DNA. Then the overwhelmingly likely reason is that I am descended from him and this mutations have come to me that. Much less likely - but not impossible - is that exactly the same set of mutations has arisen by chance in a completely separate line and I am not related to Henry IV.

The second problem with my assertion is that I said the "only way to prove..." when talking about DNA testing. There is no way to prove in the mathematical sense that I (or anyone else) is related to Henry IV. (That's an argument for another day, although I can make it rigorous, I promise) there is another way which doesn't involve DNA testing, and gives about as much certain and it's very simple.

Evolution tells us that humans evolved from an ape-like ancestor. At some point in the past there must have been a common ancestor from which all humans are descended. Every human is descended from that ancestor, including Henry IV and so we are all related to Henry IV.

So - I hear you not asking - why isn't that rigorous. The chances of evolution happening twice are very slim. Very slim indeed. But they are not zero. So it's theoretically possible that life began twice, completely indedependently, and in both cases, animals identical to humans evolved and Henry IV is one of those lines and I'm in the other.

At this point, please don't mistake me for some kind of nutter. I'm not. Obviously evolution of humans hasn't happened in parallel twice on earth. But the point is that the chances of it happening are not zero, and so we can't say in the mathematical sense that we have proved it didn't happen - even if we have shown beyond reasonable doubt that it didn't. But note that there isn't a pigeonhole - abstract or otherwise - in sight.

One footnote here is to note that we can easily show - beyond reasonable doubt - that we are all related to Henry IV but not that we are descended from him directly.

And that's why I like to write things in Tippex - they correct themselves...

## Thursday, June 9, 2011

### Putting the cat amongst the pigeonholes

The pigeonhole principle is such an obvious statement that few people realise that it's actually useful. However, a few people (who should know better, given who they are) actually get a bit too overly excited and try to use the pigeonhole principle to demonstrate the truth of things which simply aren't true.

Before getting into the pigeonhole principle itself, it may be interesting to muse first on the nature of truth. Mathematical truth is a strong concept. Things are not "true" in mathematics simply because we can't find couter-examples - things are only "true" in the mathematical sense when we can show via a structured and logical argument that there can be no possible exceptions to the rule.

Of particular interest here is the difference between an events which has a probability of 1 and an event which has a probability of "very nearly 1". In every day life, the two things are considered the same. "99%" sure is pretty much a synonym for "I'm sure"; mathematics however is not so forgiving.

Take a pack of cards. Shuffle the cards. Throw them up in the air. Pick them up of the floor and put the back back together. Common sense tells us that the cards won't be in order. Mathematics tells us simply that it's "very unlikely" that they'd be in order - but it's certainly not impossible.

The pigeonhole principle deals with certainty, not probability. The pigeonhole principle is mathematically strong - it tells us what is true - not just what is very likely to be true. The principle is very simple. Simply put it says that if you have more objects than you have boxes, and you put the objects into the boxes then at least one of the boxes will contain more than one object. It doesn't tell us how many boxes contain more than one object, nor does it tell us how many objects are in each box - it tells us only that at least one, unspecified, box will contain more than one object. Simple. But useful.

The birthday paradox will provide an interesting diversion here. The birthday paradox is a well known result - though not actually a paradox. If you take a random group of people, then you only need 23 people before there's a better than 50% chance that two people share a birthday. This number is lower than most people imagine, and I guess that's why it's sometimes called a paradox. Anyway, in order to see how the pigeonhole principle comes into play, we need to look at the birthday paradox the other way on.

Rather than looking at how many people we need in order to give us a certain chance of a birthday match, let's fix the number of people and look at how likely it is they share a birthday. For the purposes of this, I'm going to take it as read that there are 366 possible birthdays (we need to include 29th February, as it is a birthday for some people...)

If we have two people, then the probability that they share a birthday is 1/366. The more people we add to the group, the higher the chance that they share a birthday. As we've said before, once you get to 23 people you have a better than 50/50 chance of two people sharing a birthday. As you get towards 100 people you are really very very likely to have two people sharing a birthday. But you're still not certain that two people with. Right up until you've got 366 people you can't be certain that two people share a birthday. The chance that no two people in a group that size share a birthday is really very small indeed, but it could happen.

However, once you get to 367 people, the pigeonhole principle rears its head and removes the need for complicated calculations. If you must, imagine 366 boxes with a different date written on each. Take your 367 people and tell them to go and sit in the box with their birthday written on it. You could imagine a situation where 366 people are each sitting in their box but you still have one person left over. They have to go somewhere, and which ever box they sit in has two people - and there are our two people who share a birthday. At this point, we can be absolutely sure that two people in the group share a birthday. Of course, this is obvious - but I'm made the description so rigorous so that I can attempt to explain why two ways in which the pigeonhole principle are regularly applied are not so rigorous.

Let's start with one of Stephen Fry's favourite anecdotes. Everyone has two parents, four grandparents, eight great-grandparents and so on. It doesn't take many generations before we have an enormous number of ancestors. The common argument says that this number of ancestors is great than the population of England at the time at the time of Henry IV, and therefore Henry IV must be an ancestor of everyone who has English blood stretching back that far.

It's a great thought. But it's not true.

Once the number of ancestors is greater than the population, we do have a problem - and the pigeonhole principle can help us solve the problem - but the conclusion is the wrong one. The pigeonhole principle applied to this situation tells us that once we go back far enough, at least two the positions in our family tree must be occupied by the same person. This sounds alarming, but it isn't so. One person may have had children who both married, had offspring and so on for many generations until at some point someone from one family marries someone from the other. The bride and groom in this situation will share an ancestor, but it may be so many generations ago that it's well outside of living memory and doesn't present any problems.

This is interesting, but doesn't show that we are all descended from Henry IV. It just shows that at the time of Henry IV, at least two of the ancestral lines in our family tree must converge into a single ancestor. And it won't be the same common ancestor for everyone - and that common ancestor is very unlikely to be Henry IV.

Of course, given so many years, the genes of Henry IV will have spread themselves wide throughout the population and so many of us will be distantly related to him. But the only way to prove that would be to take DNA samples.

It's not just the lovely Mr Fry who gets carried away with the pigeonhole principle though. Marcus Chown once abused the principle to get to an interesting result.

The Marcus Chown case is a little more complicated, and requires a little extension of the pigeonhole principle to the infinite. We can state the infinite case as follows. If we have a finite number of boxes, and an infinite number of objects then when we put the objects into the boxes, at least one of the boxes will have an infinite number of objects in it.

At this point, I know I'm talking nonsense about infinite objects and putting all of them into some boxes, but bear with me. The objects and boxes are both abstract here, but we can look at a real world example.

There are a infinite number of integers. (I'm going to take that as read). Imagine writing them down in full - one, two, three, four, five, etc.

There are 100 tiles in a Scrabble set. Those 100 letter tiles can be used to spell some numbers. But they can only be used to spell a finite number of numbers. It's quite a lot, but it's definitely finite. If that's obvious, then let's take it as read - if it's not obvious then just consider that there are only a finite number of ways of arranging 100 tiles and only some of those will spell out numbers.

So what does that tell us. Well it tells us that if we have two imaginary boxes, one which contains all the numbers you can spell out with a Scrabble Set and the other box contains the ones you can't. The first box contains a finite number of numbers, and so the second must contain an infinite number of numbers.

So, we've shown that there are an infinite number of numbers which you can't spell using the letters from a Scrabble set. I think that's quite cool even if you're bored to death by now.

So where's this going, I hear you ask. Well Marcus Chown used a similar argument when talking on stage a few years ago.

The first part is going to have to be taken as read, even though it's actually quite counter-intuitive. So - the assertion is that there are only a finite number of possible histories for the Universe. The second assertion is that there are an infinite number of Universes. Go with me here...

Marcus Chown took those things, and said that because there are an infitinite number of Universes and a finite number of possible histories, each history must happen an infinite number of times.

Not true I'm afraid. The pigeonhole principle tells us only that at least one of those histories must exist an infinite number of times - not all of them. And it's very unlikely that the particular history corresponding to our Universe exists an infinite number of times.

The result Marcus Chown was presenting is quite possibly true, but the logic he used to get to it was, I'm afraid, fallacious.

We have strayed dangerously close to quantum physics here, and then as we know - nothing becomes certain. And according to quantum physics, if we put a cat in a pigeonhole it's only decoherence which allows us to be pretty sure it's still going to be there when we go to collect it later.

Hmm. Cats. Quantum Physics. There must be a thought experiment there somewhere, if only I could think of one... ;-)

Before getting into the pigeonhole principle itself, it may be interesting to muse first on the nature of truth. Mathematical truth is a strong concept. Things are not "true" in mathematics simply because we can't find couter-examples - things are only "true" in the mathematical sense when we can show via a structured and logical argument that there can be no possible exceptions to the rule.

Of particular interest here is the difference between an events which has a probability of 1 and an event which has a probability of "very nearly 1". In every day life, the two things are considered the same. "99%" sure is pretty much a synonym for "I'm sure"; mathematics however is not so forgiving.

Take a pack of cards. Shuffle the cards. Throw them up in the air. Pick them up of the floor and put the back back together. Common sense tells us that the cards won't be in order. Mathematics tells us simply that it's "very unlikely" that they'd be in order - but it's certainly not impossible.

The pigeonhole principle deals with certainty, not probability. The pigeonhole principle is mathematically strong - it tells us what is true - not just what is very likely to be true. The principle is very simple. Simply put it says that if you have more objects than you have boxes, and you put the objects into the boxes then at least one of the boxes will contain more than one object. It doesn't tell us how many boxes contain more than one object, nor does it tell us how many objects are in each box - it tells us only that at least one, unspecified, box will contain more than one object. Simple. But useful.

The birthday paradox will provide an interesting diversion here. The birthday paradox is a well known result - though not actually a paradox. If you take a random group of people, then you only need 23 people before there's a better than 50% chance that two people share a birthday. This number is lower than most people imagine, and I guess that's why it's sometimes called a paradox. Anyway, in order to see how the pigeonhole principle comes into play, we need to look at the birthday paradox the other way on.

Rather than looking at how many people we need in order to give us a certain chance of a birthday match, let's fix the number of people and look at how likely it is they share a birthday. For the purposes of this, I'm going to take it as read that there are 366 possible birthdays (we need to include 29th February, as it is a birthday for some people...)

If we have two people, then the probability that they share a birthday is 1/366. The more people we add to the group, the higher the chance that they share a birthday. As we've said before, once you get to 23 people you have a better than 50/50 chance of two people sharing a birthday. As you get towards 100 people you are really very very likely to have two people sharing a birthday. But you're still not certain that two people with. Right up until you've got 366 people you can't be certain that two people share a birthday. The chance that no two people in a group that size share a birthday is really very small indeed, but it could happen.

However, once you get to 367 people, the pigeonhole principle rears its head and removes the need for complicated calculations. If you must, imagine 366 boxes with a different date written on each. Take your 367 people and tell them to go and sit in the box with their birthday written on it. You could imagine a situation where 366 people are each sitting in their box but you still have one person left over. They have to go somewhere, and which ever box they sit in has two people - and there are our two people who share a birthday. At this point, we can be absolutely sure that two people in the group share a birthday. Of course, this is obvious - but I'm made the description so rigorous so that I can attempt to explain why two ways in which the pigeonhole principle are regularly applied are not so rigorous.

Let's start with one of Stephen Fry's favourite anecdotes. Everyone has two parents, four grandparents, eight great-grandparents and so on. It doesn't take many generations before we have an enormous number of ancestors. The common argument says that this number of ancestors is great than the population of England at the time at the time of Henry IV, and therefore Henry IV must be an ancestor of everyone who has English blood stretching back that far.

It's a great thought. But it's not true.

Once the number of ancestors is greater than the population, we do have a problem - and the pigeonhole principle can help us solve the problem - but the conclusion is the wrong one. The pigeonhole principle applied to this situation tells us that once we go back far enough, at least two the positions in our family tree must be occupied by the same person. This sounds alarming, but it isn't so. One person may have had children who both married, had offspring and so on for many generations until at some point someone from one family marries someone from the other. The bride and groom in this situation will share an ancestor, but it may be so many generations ago that it's well outside of living memory and doesn't present any problems.

This is interesting, but doesn't show that we are all descended from Henry IV. It just shows that at the time of Henry IV, at least two of the ancestral lines in our family tree must converge into a single ancestor. And it won't be the same common ancestor for everyone - and that common ancestor is very unlikely to be Henry IV.

Of course, given so many years, the genes of Henry IV will have spread themselves wide throughout the population and so many of us will be distantly related to him. But the only way to prove that would be to take DNA samples.

It's not just the lovely Mr Fry who gets carried away with the pigeonhole principle though. Marcus Chown once abused the principle to get to an interesting result.

The Marcus Chown case is a little more complicated, and requires a little extension of the pigeonhole principle to the infinite. We can state the infinite case as follows. If we have a finite number of boxes, and an infinite number of objects then when we put the objects into the boxes, at least one of the boxes will have an infinite number of objects in it.

At this point, I know I'm talking nonsense about infinite objects and putting all of them into some boxes, but bear with me. The objects and boxes are both abstract here, but we can look at a real world example.

There are a infinite number of integers. (I'm going to take that as read). Imagine writing them down in full - one, two, three, four, five, etc.

There are 100 tiles in a Scrabble set. Those 100 letter tiles can be used to spell some numbers. But they can only be used to spell a finite number of numbers. It's quite a lot, but it's definitely finite. If that's obvious, then let's take it as read - if it's not obvious then just consider that there are only a finite number of ways of arranging 100 tiles and only some of those will spell out numbers.

So what does that tell us. Well it tells us that if we have two imaginary boxes, one which contains all the numbers you can spell out with a Scrabble Set and the other box contains the ones you can't. The first box contains a finite number of numbers, and so the second must contain an infinite number of numbers.

So, we've shown that there are an infinite number of numbers which you can't spell using the letters from a Scrabble set. I think that's quite cool even if you're bored to death by now.

So where's this going, I hear you ask. Well Marcus Chown used a similar argument when talking on stage a few years ago.

The first part is going to have to be taken as read, even though it's actually quite counter-intuitive. So - the assertion is that there are only a finite number of possible histories for the Universe. The second assertion is that there are an infinite number of Universes. Go with me here...

Marcus Chown took those things, and said that because there are an infitinite number of Universes and a finite number of possible histories, each history must happen an infinite number of times.

Not true I'm afraid. The pigeonhole principle tells us only that at least one of those histories must exist an infinite number of times - not all of them. And it's very unlikely that the particular history corresponding to our Universe exists an infinite number of times.

The result Marcus Chown was presenting is quite possibly true, but the logic he used to get to it was, I'm afraid, fallacious.

We have strayed dangerously close to quantum physics here, and then as we know - nothing becomes certain. And according to quantum physics, if we put a cat in a pigeonhole it's only decoherence which allows us to be pretty sure it's still going to be there when we go to collect it later.

Hmm. Cats. Quantum Physics. There must be a thought experiment there somewhere, if only I could think of one... ;-)

Subscribe to:
Posts (Atom)