 |
 |
|
|
||
|
 |
Department of Engineering |
|
|
|
|
The premier league demo from the www.understandinguncertainty.org web site.
Wikipedia entry for entropy
Exercise: You are given 12 balls, all equal in weight except for one that is either heavier or lighter. You are also given a two-pan balance to use. In each use of the balance you may put any number of the 12 balls on the left pan and the same number on the right pan, and push a button to initiate the weighing; there are three possible outcomes: either the weights are equal, or the balls on the left are heavier, or the balls on the left are lighter. Your task is to design a strategy to determine which is the odd ball and whether it is heavier or lighter than the others in as few uses of the balance as possible.
While thinking about this problem, you may find it helpful to consider
the following questions:
a) How can one measure information?
b) When you have identified the odd ball and whether it is heavy or
light, how much information have you gained?
c) Once you have designed a strategy, draw a tree showing, for each of
the possible outcomes of a weighing, what weighing you perform next.
At each node in the tree, how much information have the outcomes so
far given you, and how much information remains to be gained?
d) How much information is gained when you learn 1) the state of a
flipped coin; 2) the states of two flipped coins; 3) the outcome of
when a four-sided die is rolled?
e) How much information is gained on the first step of the weighing
problem if 6 balls are weighed against the other 6? How much is gained
if 4 are weighed against 4 on the first step, leaving out 4 balls?
(This is exercise 4.1 from the book Information
Theory, Inference, and Learning Algorithms by David J.C. MacKay.)