Skip to main content

Jester in the Dark: Encoding Knowledge into Inferences - Part I




You are dining at the castle hall and the king announces he is going to give the jester's his yearly payment. He points at a small adjacent room, where there are 3 small equal chests. The first with 2 gold coins; the second, 1 gold and 1 silver coin; the third, 2 silver coins. The king's serfs go inside, shuffle the chests, lock them, put out the candles, and summon the court jester to the hall. The buffoon is told to put his hand in a bag, grab 1 chest key, walk into the dark room and get 1 coin out of the matching chest. He brings the coin back and it is a gold one.

The king takes the coin from his hand and says aloud:
- If I send this idiot back there to get the other coin out of the same chest, how likely it is to be gold?
The jester interrupts:
- Please do send me, sire! I'd likely be a happy idiot, with one more gold coin.
The king angrily points out to the jester's face:
- Folly! I'll have you beheaded for stupidity. This gold coin could have come from either chest.

Enjoying your meal at the hall, you have a chance to be bold and save the jester's life. Can you make a case for him?




* You can try and solve it before we go on *




We can start by reasoning informally about the problem, taking the king position. The gold coin could only have come from 2 of the 3 chests. So there is a 50% chance of any of the 2 chests being open and 0% of the third chest being open. If the jester goes back in the room he should then have a 50% chance of finding a gold coin in the open chest.

The catch is that one we know that the first coin is gold, there is a higher chance that it came from chest 1 (the one with 2 gold coins). In fact, there is a 2/3 chance that it cam from chest 1 since out of all 3 gold coins, 2 of them are in it. We will now walk through the inference problem in a more formal way.

First we name the variables:


Then we write the probability we want to discover, which is the probability that the second coin will be gold given that the first one was gold. Since we don't know the opened chest, we can calculate considering all of them. This leads us to write the probability using the sum rule:

 



Which can be rewritten as:


In the form above, the probability is more clear. The first probability inside the summation is the probability that we get a second gold coin given a certain chest and that the first coin was gold. The second probability inside the summation is the probability of a certain chest being open given that the first coin was gold. Each term in the summation will give P(g2|g1) for a certain chest; by summing over all of them we get the desired overall probability.

We know from the problem the probabilities of getting a second gold coin given a chest and a first gold coin. For instance, the probability of getting a gold coin from the second chest (once we already have a gold coin) is 0 since it is only left with the silver coin. The three probabilities are:





The second probability of the chests conditioned on the first gold coin is a bit more tricky and we use the help of Bayes' theorem. We assume a uniform prior on the chests: The posterior probability of the jester opening each chest is the same (he draws a key at random from a bag).





The likelihood of getting a first gold coin given a chest comes from the problem statement. For instance, the probability of getting a first gold coin out of the first chest is 1 since it only has gold coins. The three probabilities are:



The normalizing constant (overall probability of getting a first gold coin) is:



Now we can calculate the posterior probability for each chest:



Then the probability we wanted at the beginning becomes a matter of plugging everything in:



The key insight in our calculations is that chest 1 (containing 2 gold coins) is more likely to have been the opened chest given that the jester brought a gold coin.

This puzzle was a training do we can tackle one that is even more counter-intuitive: the three door puzzle or the Monty Hall problem.




*Image: https://en.wikipedia.org/wiki/Jester#/media/File:Jan_Matejko,_Sta%C5%84czyk.jpg






Comments

Post a Comment

Popular posts from this blog

Slaying The Mythical p

Finally I have come out of the introductory chapters forest. In mission 3.15, MacKay summons us to slay the mythical p-value. The weapons we carry are simple, but sharp and the insights look very promising. This mission will lead us to confront the p-value and its meaning when we are comparing two different models. In this post we are going to carefully go through the exercise solution and insights. First we are going to recalculate the statistician conclusion and then move on to MacKay's approach of comparing two models by how likely is the data given each of them. In a way, this post is also intended as containing part of the essence of chapters 1 and 3. Before reading on I suggest you work on the exercise yourself (for 15 minutes, even if you can't solve it): ‘If the coin were unbiased the chance of getting a result as extreme as that would be less than 7%’ We interpret this sentence as meaning that 7% is the probability of a fair coin getting 140 or mo...
Post a Comment
Read more

First Week, First Chapter

I just finished my first week and want to reflect a bit on why I started this. There are two main reasons: Deepen and broaden my knowledge of Information Theory; and motivate people who might hesitate on taking up the challenge or feel too old to start learning or revisiting a field. The book is very exciting; Mackay's writing is clear and flows nicely, introducing a concept, diving into it, and then out to generalise. His approach is to make you feel as if you are constructing and checking the concepts alongside him. His magic is that the presentation feels both casual and principled, like if you were sitting together with a very smart friend who is explaining you things. I ended this week at page 21, so my current rate is 3 pages per day since I will not be working the weekend. At the current rate I would finish the book in about 6 months. Mackay's prediction for the time required for each exercise worked quite well for me although it took me more time tha...
Post a Comment
Read more