4
$\begingroup$

In the book (available online for free) "Information Theory, Inference, and Learning Algorithms" by David J.C. MacKay, on pages 68f, and in this recorded lecture of his (Youtube), the "Weighing Problem" (an example of combinatorial group testing) is described and solved by what could be called a "greedy information content strategy". It is mentioned at the end of the Youtube lecture (around 45:45) that there are problems where this strategy would fail (or be sub-optimal). My question is: What is an example puzzle/problem where such a "greedy information content strategy" fails? In general, in what kinds of problems (puzzles?) does it fail?

I will now outline what I mean by "greedy information content strategy". The "Weighing Problem" involves having some number of balls, all equal in weight except for one that is either heavier or lighter. One may weigh any two subsets of the balls against each other in a scale. The task is to find the odd ball with as few uses of the scale as possible. In each weighing, one makes a partition of the balls into the three subsets (weigh left, weigh right, don't weigh). Starting with a uniform prior probability distribution, one updates it after each weighing according to the result. The optimal solution strategy, as presented by MacKay, dictates to make partitions which maximize the expected information content of the next weighing outcome. This is what I call "greedy information content strategy".

$\endgroup$
1
  • 1
    $\begingroup$ This Vsauce 2 video provides an example (at least one where a greedy algorithm fails - I'm not sure about a "greedy information content strategy"). $\endgroup$ May 27 '20 at 0:33
1
$\begingroup$

Noticing the (well known) fact that building a prefix-free binary code (with minimum average length) is equivalent to devising an strategy for finding an item with yes-no questions... it's quite evident that the greedy strategy (maximize the information content gained in each step) can be suboptimal. Because, in that scenario, the greedy strategy would correspond to the Shannon-Fano coding. And this code is suboptimal. In that page an example is provided in which the Huffman code (non greedy) performs better.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer! Do you know an example of a puzzle (like the "weighing problem"), or a way to construct a puzzle, that illustrates this? If not, I'll try to think of one myself. $\endgroup$ May 27 '20 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.