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:	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011
Original:	x	x	0	x	0	1	1	x	0	1	1
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