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.)