Proof: All Blind-Memoryless search strategies are equivalent

[Eidos]

Hi All

Is there a proof that all blind-memoryless search strategies are equivalent?

By equivalent I mean that no blind-memoryless search strategy can outperform any other in terms of time to goal and domain coverage.

It seems to me that this is intuitively true.

How would I go about proving it?

Thanks :-)

[Coin]

You might want to look at the No Free Lunch (http://www.no-free-lunch.org/) theorems, which prove something stronger:

All algorithms that search for an extremum of a cost function perform exactly the same when averaged over all possible cost functions. So, for any search/optimization algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class.

The way the proof is done is something along the lines of showing that for any given algorithm you may choose, each search landscape that the algorithm turns out to do well on is balanced by a perverse search landscape (somewhere out there in the set of all possible landscapes) that looks like that optimal landscape locally but is actually tricking the algorithm into moving away from the good points.

I think what you want to prove may actually follow from Wolpert and Macready's existing theorems here?

[Eidos]

You might want to look at the No Free Lunch (http://www.no-free-lunch.org/) theorems, which prove something stronger:



The way the proof is done is something along the lines of showing that for any given algorithm you may choose, each search landscape that the algorithm turns out to do well on is balanced by a perverse search landscape (somewhere out there in the set of all possible landscapes) that looks like that optimal landscape locally but is actually tricking the algorithm into moving away from the good points.

I think what you want to prove may actually follow from Wolpert and Macready's existing theorems here?

Thanks very much ^^
Thats exactly what I was looking for.