Horizontal No Free Lunch Theorem

In my previous post I criticized the Horizontal No Free Lunch theorem for searches consisting of at least two queries. But even in the case of a single assisted query, I can't get my head around it.

Dembski and Marks define an assisted query as any choice from Ω₁ that provides more information about the search environment or candidate solutions than a blind search. As an example, they give for instance, we might imagine an Easter egg hunt where one is told “warmer” if one is moving away from an egg and “colder” if one is moving toward it.

The ultimate assisted search is no search at all, the unveiled Easter egg. So, imagine a blind (A), a drunken (B), and a seeing, sober (C) chess-player, and ask them to locate the White Dame (♕) on a chess board. (A) will be find it with a probability of 1/64, (C) with a probability of 1, and lets assume for (B) a probability of 1/2.

Then (A) represents the blind search, (B) an assisted search and (C) what the authors call a perfect search on our search space Ω = {a1,a2,....,h8} (|Ω|=64).

Imagine that ♕ is positioned on a1, so T₁ = {a1}. Then we have three probability measures, α_a1, β_a1, and γ_a1 for each one of our players, which allow us to calculate the probability for each one to find T₁:

• α_a1(T₁)= 1/64


• β_a1(T₁) = 1/2


• γ_a1(T₁) = 1

And we can calculate - according to (3.1) (10) the active information of these measures for various sets and combinations, e.g.
I₊(β_a1|α_a1(T₁)){a1} = log₂1/2 - log₂1/64 = 5.

So, the drunken player has more active information on the whereabouts of ♕ than the blind one.

I₊(γ_a1|α_a1(T₁)){b1} = log₂0 - log₂1/64 = -∞

A more surprising result: if ♕ is on b1, but (C) sees it on a1, he is much less informed than (A).

But of course, γ_a1 isn't the right measure if ♕ is on b1, we would expect γ_b1: the idea of an assisted search seems to be that it assists to the right direction - for our Easter egg hunt: if your helper directs you always to the same place, whether there is an egg or not, he is no helper indeed, he's just a nuisance:

Trivially, a search helped in this way can't be differed from an unassisted search.

But I'm afraid that exactly what W. Dembski and R. Marks do in their Horizontal No Free Lunch Theorem: let's take the partition T~ = {{a1},{a2},...,{h8}} of our Ω₁ above. What does

Σ α_a1{T_i} × I₊(γ_a1|α_a1){T_i}

mean? Nothing else than that our seeing, sober man errs 63 times out of 64 when looking for ♕. That just doesn't make sense.

The meaningful expression would have been:

Σ α_Ti{T_i} × I₊(γ_Ti|α_Ti){T_i}

And while the first sum adds up to -∞ the latter one is not negative at all: it's just 6.

nota bene: I think this is the idea behind Rob's (R0b?) comment to my previous post. So, thanks Rob!