Five Years of "The Search for a Search"

The Journal of Advanced Computational Intelligence and Intelligent Informatics published the paper The Search for a Search: Measuring the Information Cost of Higher Level Search of William A. Dembski and Robert J. Marks II (DM) in its July edition in 2010. With the five year jubilee of the publication coming, it seems to be appropriate to revisit a pet peeve of mine...

(Shell game performed on Karl-Liebknecht-Straße in Berlin, photograph by E.asphys)

Imagine a shell game. You have observed the con artist for a while, and now you know:

1. The pea ends up under each of the three shells (left, middle, and right) with the same probability, i.e., $$P(Pea=left)=P(Pea=middle)=P(Pea=right)=1/3$$
2. If the pea ends up under the left or the middle shell, you are able to track its way. So, in these cases, you will find the pea with probability 1 $$P(Finding\,Pea|Pea=left)=P(Finding\,Pea|Pea=middle)=1$$
3. However, if the pea ends up under the right shell, in 999 times out 1000, you make a mistake during your tracking and be convinced that it is under the left or the middle shell - the probability of finding this pea is 1/1000$$P(Finding\,Pea|Pea=right)=1/1000$$

You are invited to play the game. Should you use your knowledge (method $M_1$), or should you chose a shell at random (method $M_2)$? Let's calculate the average probability for finding the pea using your knowledge $$AM_1= P(Pea=left) \cdot P(Finding\,Pea|Pea=left)$$ $$+ P(Pea=middle) \cdot P(Finding\,Pea|Pea=middle)$$ $$+ P(Pea=right) \cdot P(Finding\,Pea|Pea=right)$$ $$AM_1 = \frac{1}{3} \cdot 1 + \frac{1}{3} \cdot 1 + \frac{1}{3} \cdot \frac{1}{1000} = \frac{2001}{3000} \approx \frac{2}{3} $$

What is the average probability when choosing a shell at random? As the pea is in the left, middle or right position with the same probability, we get $$AM_2 = \frac{1}{3} $$

So, $M_1$ or $M_2$? The answer seem to be obvious: you should stick to the first method, as it wins twice as often. Not so fast, say the Drs Dembski and Marks. You should calculate the average of the active information - the active entropy: $$H_1 = \frac{1}{3} \cdot \log_2 \frac{1}{1/3} + \frac{1}{3} \cdot \log_2 \frac{1}{1/3} +\frac{1}{3} \cdot \log_2 \frac{1/1000}{1/3} $$ $$= \log_2(\sqrt[3]{1 \cdot 1 \cdot \frac{1}{1000}}) - \log_2(\sqrt[3]{\frac{1}{3}\cdot \frac{1}{3} \cdot \frac{1}{3}})$$ $$=-\log_2(10) + \log_2(3)\approx -1.737$$ And their conclusion (p. 477): as on average the calculation results in negative active information, the search performance is rendered worse than random search. This is obviously false.

What went wrong? To calculate the overall performance, it is appropriate to use the arithmetic mean, as done for $AM_1$ and $AM_2$. By calculating the active entropy, you are de facto comparing the geometric means of your method and of the random method. The geometric mean favors equidistribution, thereby preferring the inferior random method over your more successful method, which tends to fail in only one case (pea under the third shell). This is a usual scenario: you often find algorithms which do well on most of the cases, but fail in some - often especially manufactured - instances.

Conclusion: The average of the active information is not a good method to describe the performance of a search. If you think otherwise, maybe I can interest you in buying a bridge?

(edited to clarify the search process)