Sunday, October 10, 2010

Bernoulli vs. Clark Kent

When discussing the consequences of their Horizontal No Free Lunch theorem, the authors W. Dembski and R. Marks state:

Because the active entropy is strictly negative, any uninformed assisted search will on average perform worse than the baseline search.

Here, the baseline search is the blind search. But what is an assisted search? As an example, the authors have introduced the perfect search

an assisted search guaranteed to succeed

Let's look at an example: a shell game - three shells, one pea. The operator is a fair man, who will hide the pea with probability 1/3 under any of the three shells.

The players are Bernoulli and Clark Kent. Knowing the paper of W. Dembski and R. Marks on the HNFLT, Bernoulli makes a guess at random, using a uniform distribution on the shells.

Clark Kent just picks the shell which hides the pea (remember - Clark Kent is Superman...), thereby performing a perfect search.

Who fares better? According to W. Dembski and R. Marks, both do equally well: observing the picking pattern of Clark Kent, they conclude that Clark Kent uses a uniform measure on the search space - as Bernoulli does: unfortunately, the mathematics of their paper has no way to deal with a strategy which is influenced by the position of the target (as any assisted search would be.)


  1. What do they mean by "uninformed assisted search"? Would they claim that Clark Kent's search is informed?

  2. Very good question: They never define an "uninformed assisted search", neither in this paper, nor in its predecessors ("Conservation of Information in Search", "Bernoulli's Principle of Insufficient Reason and Conservation of Information in Computer Search". "Life's Conservation Law" or "Efficient Per Query Information Extraction from a Hamming Oracle").
    In the literature, an uninformed search is a search without using any domain specific information.
    An uninformed assisted search therefore is a kind of white raven.

  3. For mutual benefit, you will do me a favor promoting your own blog on mine!