Essay:A counterexample to a theorem of William Dembski and Richard Marks
In their article The Search for a Search the authors William Dembski and Richard Marks seem to assume that any search on a space induces a probability measure on the search space, as they write in section 3.1 (Active Information):
"Let U denote a uniform distribution on characteristic of an unassisted search and the (nonuniform) measure of for an assisted search. Let and denote the probability over the target set ."
Such an induced measure gives the probability to find a subset T of when performing the corresponding search. But for the assisted searches mentioned in the text (a perfect search (indicating an assisted search guaranteed to succeed) and another search indicating an assisted search guaranteed to fail), such probability measures obviously do not exist! Thus these cases are not covered by their Theorem 1 (Horizontal No Free Lunch), as the Kullback-Leibler-distance is defined only for probability measures.
But perhaps the authors intended their theorem only to be valid for those searches which induce a measure on the search space - indeed, they use the term uninformed assisted searches when describing their results. Unfortunately, this term is not defined - neither in the current text, nor in their previous publications Conservation of Information in Search - Measuring the Cost of Success or Efficient Per Query Information Extraction from a Hamming Oracle.
Unfortunately, even in this case, the theorem does not work: assuming the easiest nontrivial case of guessing an element of a set with two elements (tossing a coin), , the two strategies naming an element at random (uniform distribution on ) and sticking with one element (dirac distribution) give the same success rate for a fair coin. The same result occurs when averaging over the probability of showing head (assuming that this probability is uniformly distributed on [0,1]), contradicting the statement of William Dembski and Richard Marks:
Because the active entropy is strictly negative, any uninformed assisted search () will on average perform worse than the baseline search. (Highlighting mine)
In my opinion, the fundamental problem stems from identifying the search space and the space of (deterministic) searches. This is doubtless elegant, but does not seem to work.
- W. A. Dembski and R. J. Marks II, "The Search for a Search: Measuring the Information Cost of Higher Level Search," Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 14, No. 5, pp. 475-486, September 2010
- W. A. Dembski and R. J. Marks II, "Conservation of Information in Search: Measuring the Cost of Success," IEEE Trans. on Systems, Man and Cybernetics A, Systems and Humans, Vol. 39, No. 5, pp. 1051-1061, September 2009
- W. Ewert, G. Montanez, W. A. Dembski, and R. J. Marks II, "Efficient Per Query Information Extraction from a Hamming Oracle," Proc. of the 42nd Meeting of the Southeastern Symposium on System Theory, IEEE, University of Texas at Tyler, pp. 290-297, March 7-9, 2010