Wednesday, 16 May 2007

Three Hats and Coding Theory

So, I saw this interesting article on Digg, about a mathematical problem known often as the three hats problem. Let me set it up for you:

Three people are in some competition run by some maniacal billionaire. If they "win" they get £3,000,000 between them, but if they lose, they leave with nothing (or get thrown to the sharks with lasers on their heads, whatever floats your boat).

The rules of the game are simple. The team have 5 minutes before the event to discuss their strategy, and after that, no communication of any sort is allowed. After this 5 minutes, each contestant gets a hat placed on their head, either red or blue, determined by a independent coin toss. They do not know what colour hat they have on, but they are able to see the hats of the other 2 contestants. On the count of 3, all the contestants must call out either "red", "blue" or "pass" simultaneously, dependent on what colour hat they believe that they are wearing. The team is deemed to have won if at least one contestant gets the colour correct and no member of the team gets the colour wrong (passing is not getting the colour wrong).

The question, of course, is what is the optimal strategy for the contestants to decide upon?
So, this looks similar to a problem which we've all seen before, however we have this issue of not knowing how many of each colour hat there is. Surely, you may think, since the coin tosses were independent of each other, the best strategy would be to pick 2 people to pass, and the third to pick either red or blue dependent on how his mood takes him. This would give a 50:50 shot at getting £1mil, and who's going to complain about that? Surely there cannot be a better strategy than this - it's random, right?

Well, what if I were to tell you that I knew of a strategy which would win 3/4 of the time? Crazy, no? Well, let me sidetrack a little onto another game show (with fewer maniacal billionaires and sharks with lasers, I guess...):

You have been invited to take part in a TV game show, and the winning prize is an awesome sports car (or something like that). You have got to the final round, and the presenter presents you with 3 garage doors. Behind one of these, he tells you, is this awesome sports car. Behind the other two, however, is a goat (or, I guess, we can throw in the sharks with lasers on their heads here...). He asks you to pick a door, 1, 2, or 3.

Let's say, without loss of generality, that you pick door 1. The presenter says, OK, OK, that's cool, but will this change your mind? At this point he opens one of the other doors to reveal a goat. The presenter explains that he will give you one chance to switch from the door you've already picked (door 1) to the other, unopened door.

What should you do, stick, switch, or does it not make a blind bit of difference?

Well, most people will tell you that it will not make a blind bit of difference which door you pick - we've now got 2 doors, one with a sports car and one with a goat, so you've got a 50:50 chance of winning the sports car (or goat) of your dreams!

In fact, as many of you will know, there is more to this problem than meets the eye. Consider what happened before you chose box 1. At that point in time, you had a 1/3 chance of having picked the correct box (clearly) and a 2/3 chance of the car being in one of the other two. So, let us look at this in a case-by-case basis:

CASE 1: You have picked the car already (probability 1/3):

In this case, after the other door is opened by the presenter, if you were to stick you have won (probability of winning 1), if you switch you lose (probability of winning 0).

CASE 2: You have picked a goat already (probability 2/3):

In this case, after the other door is opened by the presenter, if you were to stick you would have lost (probability of winning 0), and if you switch you would have won (probability of winning 1).

So, doing simple arithmetic, we see that overall, if you stick with the box you chose initially, the probability of winning is , but if you switch to the other box, your probability of winning is meaning that you should, in fact, switch boxes, and 2/3 of the time you will win.

So, the result of this is unintuitive, and relies on the initial set-up of the doors.

Going back to our original problem, let us try to understand how this relates. Well, we are looking at what the set-up of the problem could be, so let us list the possible organisation of the hats with their probabilities:

RRR 1/8
RRB 1/8
RBR 1/8
BRR 1/8
RBB 1/8
BRB 1/8
BBR 1/8
BBB 1/8

Nothing too spectacular here, unless you start to look slightly deeper. Consider the fact that there is only a 1/4 chance of all three people wearing the same colour hat. Can we use this fact to our advantage? Well, in the other 6 cases (that is to say the remaining 3/4 of the time), there is one person wearing one colour hat, while the other two people are wearing the other colour. From this, we can extrapolate a rule to follow - if you see that the other two people are wearing hats of the same colour, then shout out the other colour. This rule will mean that 1/4 of the time all of the players will shout out the wrong colour (catastrophic failure), and the other 3/4 of the time, the two players sharing a hat colour will pass, and the player wearing the other colour will guess correctly (success!).

This may, of course, seem massively counter intuitive, since the colour of one person's hat is completely independent of the colour of the other two, but if you follow my reasoning, you will see that it is in fact true.

Now, why, you might ask, is this post called "Three Hats and Coding Theory" - what the hell is coding theory, and what has it got to do with this little puzzle?

Coding theory centres around the transmission of data across noisy channels. The specific area of Coding Theory which this puzzle can help with is "channel coding" - that is error checking of data. Let us begin by studying the premise behind these error codes.

First, let us imagine that we are sending an 7-bit code (that is 7 numbers, all either 0 or 1) across some noisy channel, and there is a chance that some 0's might be changed to 1's and some 1's to 0's. WLOG, let us transmit the code 0011011. One (very poor) method of checking if there has been an error would be to transmit each bit of the code twice (i.e. send 00001111001111). If there is an error, then there will probably be a discrepancy, but unfortunately in this instance we don't know which is wrong, so we would have to ask for the data to be resent. To get this error correcting component, we would need a repetition code of at least 3, that is to say we would send "000000111111000111111", and then if one bit changes in one of the triples, we can correct the message back to the original. However, the issue with this is that, well, we'd have to send 3 times the amount of data which, technical term coming up here, sucks big time.

This is where the "Hamming Code" comes in. Using a Hamming (11,7) code, we are able to find and correct 1-bit errors in a 7-bit code, by making the code 11-bits long. These 4 "parity checking" bits are put in positions 1,2,4 and 8 of the code. Each of these bits relates to the bitwise sum of the bits in the positions which have a 1 in their binary representation at the 1st, 2nd, 3rd or 4th digit respectively.

That was a bit of a mouthful, so let's use our example to show this more clearly:

Digit:00010010001101000101 011001111000100110101011
Original:xx0x011 x011
Parity 1: 0 = 0 + 0 + 1 + 0 + 1
Parity 2: 0 = 0 + 1 + 1 + 1 + 1
Parity 3: 0 = 0 + 1 + 1
Parity 4: 0 = 0 + 1 + 1
Final: 0 0 0 0 0 1 1 0 0 1 1

The trick with this is to now change one of the digits, and see if we can recover the original message.

First, assume that one of the Parity digits changes. This would result in a Fail on that check, but a pass on all the others. Every other digit of the sequence (3,5,6,7,9,10,11) is covered by at least one other parity check, so that means that the parity digit must be wrong, error corrected.

Next, assume that one of the original digits has been changed. Now, if you will note, by virtue of the way that we designed the parity digits, if one of the non-parity digits has been changed, then more than one parity check will fail. Moreover, each digit being incorrect would cause a different set of parity checks to fail, giving us exactly which digit dunnit.

How does this relate to the hat problem, you ask? Well, unfortunately I do not have the exact details of this, but it does relate to the extension of the hats problem to having more people. Essentially, it comes down to the fact that you are manufacturing a situation where either very few people are right and noone is wrong, or as many people as possible are wrong and noone is right. Essentially the person who does the shouting of a colour is basing his idea on the colours of the other hats, and what he therefore expects his hat colour to be most of the time. This can be related in an obvious manner to a parity digit. Obviously, in the Hamming Code sense, you would expect the Parity Digit to be (in our case) the bitwise sum of the other digits that it sees, if it's wrong, then we know the situation isn't quite right. Similarly, the person shouting out a colour is basing his result on what he sees, and if the colour is not the same as his hat, then we know the situation is not an optimal one (in this case we know all the hats are the same colour in the 3-person scenario).

Research into this has resulted in a theory which results in chances of winning getting closer and closer to 100% as the number of participants increases, even in the case where there are not contestants (which can easily be shown to have solutions where you can win of the time). New Covering Codes (that is, essentially, data compression) have been designed around this game, and research into this puzzle have resulted in some interesting solutions to problems in Coding Theory.

Coding theory isn't really my area (as you've probably guessed), but this I found to be quite an interesting read, and I did find out a lot of things I did not know before.

Original Article Here

Wednesday, 2 May 2007

I'm back!

Hello to anyone that reads this (Ok, so that's going to be my mum and a few members of the Warwick Mathematics Society), I wanted to (finally) update everyone with what's been going on, and why there have been like... no posts here of late :)

Basically, the Sunday before last (22nd Apr), I was cooking a risotto with Emma (my girlfriend) and managed to miss the onion and cut straight into my finger. Unfortunately, I also managed to cut right through my main vein and my digital nerve :( I was in hospital at Walsgrave from Monday morning til Thursday, missed 2 exams and my essay deadline - funsies!

Anyway, I've been unable to type properly until now due to a bandage which got to about 1 inch thick around my whole hand - thankfully I'm now down to a simple finger bandage, and can almost touch-type again :)

Anyway - upcoming posts include some talk about illegal numbers (well, illegal in the US, but that's where this blog is hosted, so illegal on this blog) and the internet aftermath from yesterday (interesting story even for non-techies), some more essay updates and of course a review of my Biffy Clyro gigs :)

Anyways, toodles!


Monday, 16 April 2007

A bad Biffy Clyro cover I made - Wave Upon Wave Upon Wave

Hey all, this is a bit of an odd post for this blog, but what the hey, I made a cover of Biffy Clyro's Wave Upon Wave Upon Wave after having seen them twice over the weekend :D I'll put some reviews of the gigs up here in due course, but for the time being, enjoy(?) the cover!

If you want to get a good version of the song (the original!) then the album you need is Biffy Clyro's "Infinity Land":

Saturday, 14 April 2007

Book Review - Numbers And Functions, R. P. Burn

This is the first of my book reviews, aimed at current undergraduate mathematicians, especially those at Warwick University.

For my first review, I will be looking at one of the recommended books (nb. link only works for Warwick Mathematicians) for Warwick's 1st year Analysis I & II course - Numbers and Functions: Steps to Analysis by R. P. Burn.

This book covers all areas of basic analysis and presents them in a problems-and-answers manner. That is to say, the majority of this book is written as brief introductory paragraphs followed by a number of questions which both test understanding of concepts, and produce methods of proving many of the Theorems the book gives. All problems have at least outline solutions, so if you get stuck there are always hints to push you in the right direction.

One of the major advantages of this book, at least for me in my first year, was that I felt that I was teaching myself these topics. As any first year student knows, lectures can be initially very daunting, and most people will find that if they are unable to understand one topic from the lecture, very quickly they will begin to slow down and lose understanding of the following concepts. The only way to remedy this is work outside of a lecture, and for me at least this did not happen. This book really saved me come revision time, and I used it to essentially learn the majority of the course at my own pace.

That is not to say that this book can replace an entire Analysis course - I would suggest you do rather more work than I did, especially if you have problems - but it is a very strong learning aid. It gives problems which are more engineered to gaining a greater understanding of a concept than a typical assignment sheet is, and will help you to not only remember the concepts, but to understand them more fully.

Come revision time, each chapter is finished off with a summary of the definitions and results from the chapter, and has question number references to help you pinpoint the area in which it was proven or used. The historical notes at each chapter are nice, but not really of much use (although they can be a welcome break after looking over 70-odd questions!).

On to content, the book is split into two main sections "Numbers" and, unsurprisingly, "Functions." It all starts very simply, harking back to A-level maths, with a more "mathsy" look at Induction and Inequalities. These give a nice slow introduction to some of the rigour of mathematics, and provide the reader with a real bridge to university-level maths. Sequences, Series and Completeness finish the Numbers section (totalling 131 pages and 352 questions!) and provide detailed looks at many concepts and theorems such as the Fundamental Theorem of Arithmetic, the Bolzano-Weierstrass Theorem and Power Series.

The second half of the book - "Functions" - concerns itself with continuity, completeness, calculus and function sequences. Weighing in at almost 200 pages and 417 questions, the majority of the book lies here. There are far too many concepts to really be mentioned here, but they are again presented in a brilliant style in which the reader really teaches themselves these concepts.

This book really, in my opinion, is the leading book for a first year analysis course, and outshines Guide to Analysis (Macmillan Mathematical Guides) by Mary Hart, and was truly a lifesaver for me saving me having to retake my Analysis exams.

This book is available from from the link below - enjoy!

Tuesday, 10 April 2007

Beatie Boys, Foo Fighters, RHCP to play Live Earth UK

Right, I just saw this posted on the Wii news channel, and just had to pop it up here. This one isn't from the world of Maths or Computers as normal (although it did come from a Wii...).

The lineup for the UK portion of the Live Earth concert has just been announced, and what a lineup it is - Beastie Boys, Foo Fighters, Red Hot Chili Peppers, Bloc Party, Razorlight... Well that's about it for my favourite bands, but even so! (Full lineup at bottom)

The gig is on 07/07/07 all around the world, and the UK portion is being held at the Wembley Stadium. Registration for tickets will be available from the Live Earth site from this Friday for the UK gig, so take a look!

The US lineup has also been announced, and artists include Smashing Pumpkins, Roger Waters, The Police, Fall Out Boy and Bon Jovi - so another gig worth going to! Tickets for the US portion of Live Earth go on sale from the other site Monday April 16th EDT.


UK, Wembley Stadium:
Beastie Boys, Black Eyed Peas, Bloc Party, Corinne Bailey Rae, Damien Rice, David Gray, Duran Duran, Foo Fighters, Genesis, James Blunt, John Legend, Keane, Madonna, Paolo Nutini, Razorlight, Red Hot Chili Peppers, Snow Patrol

US, Giants Stadium: AFI, Akon, Alicia Keys, Bon Jovi, Dave Matthews Band, Fall Out Boy, John Mayer, Kanye West, Kelly Clarkson, KT Tunstall, Ludacris, Melissa Etheridge, The Police, Rihanna, Roger Waters, Smashing Pumpkins

Friday, 6 April 2007

Happy Easter!

Just a very quick post to wish anyone that bothers reading this a happy easter, and to tell anyone that cares that I'm back in Reading this weekend, so I'll try to organise Easter drinks at Bob's or something :)

This also seems like a great time to thank WolverineX02, who made the
for blogger greasemonkey script, and as such I will link to the script and his homepage :)


Essay Backtrack - Julia Sets

I have been mentioning Julia Sets in my essay updates a lot, and yet I still have not really explained what they are in great detail, or given you any examples. This post aims to explain Julia Sets and some related results in a manner which is graspable by a first year mathematician or so. The prerequisite knowledge really for a basic understanding is Complex Numbers and Functions.

To find a Julia Set, we first need the function for which it is a Julia Set of. Although this concept can be extended to other cases (or reduced to in the case of ), the most common case is that of a function . The function also needs to be quite smooth, specifically it needs to be holomorphic (you do not really need to understand this greatly for a basic understanding, but if you're interested wikipedia has the definition behind the link).

Now, the concept of a Julia Set is based upon the long term effect of repeated iterations of on points in the plane. That is to say, given a point , we want to find out what happens as we take repeated iterations of , that is as . There are, in a simplistic case, 2 different things that can happen. The first is that the point tends off to infinity upon repeated iteration of . The second is that it doesn't, and remains bounded. Now, this may not sound particularly exciting, but this concept can give some surprising results right from the offset.

Generally speaking, a good point to start at in the study of Julia Sets is looking at the Julia Set of a Polynomial Map - (note that it is a simple exercise to notice that in fact any complex polynomial map of the form can be reduced to one of the form ). So, let us look at the most simple of these maps, that is . Now, let us try to find which points are in the set . In this particular case, it is simple. As we know, if we take a point , then , and so all points such that will move towards , all points with will move toward infinity and all points with will stay on the unit circle. We can now say that the filled julia set . Furthermore, the Julia set is . Finally, in terms of definitions, the Fatou Set of this function is defined to be , that is all the points which are not in the filled Julia Set.

So, having seen a very simple example, we may wonder what will the effect be when we change our value of ? Well, this is where we get our surprising result. Running a simple script through MATLAB (which I will write about in the future), we find that our Filled Julia set (with ) now looks like this:

This is a set of fractal nature, that is to say that it has an infinitely fine structure (so if you zoom in on the edge of it, it remains detailed at arbitrary levels) and small parts of it bear a resemblance to the entire set.

Julia Sets were some of the first things I came across when writing my second year essay, and my interest in them has really pushed me towards learning about complex dynamics in general, thus my third year essay!

If you want to find out more about Julia Sets, and in fact fractals in general, I would suggest that the book Fractal Geometry: Mathematical Foundations and Applications by Kenneth Falconer is brilliant, and well worth a read for anyone with interest in this area.