My problem: When I read the term search for a target without any qualifier, I imagine that
- the target is fix
- the search is over when the target is found the first time
A model for this: a game of Battleship against a random generator with this additional rules:
- all ships are of size one
- you don't know how many ships there are
- the game is over with the first hit
So, if your search space is Ω then there are 2|&Omega| - 1 different targets.
But with this kind of target, the math of W. Dembski's and R. Marks's paper doesn't work: They claim that you can't find a strategy for that works better on average than random search. In the Battleship example: there is no better strategy than shooting at random each turn until your first hit. But this is obviously wrong: A better strategy is not to hit a square twice.
But W. Dembski and R. Marks proved their claim - how so? Well, they redefined the concept of target. The altered rules for the Battleship:
- the position and the number of the ships changes each round
- to succeed, you have to hit a ship each round
For this version - and not for the one above - they proved all their results. The problem: That's not search as we now it...
The technical details: In section III, B, they formalize a search
Suppose now Ω denotes an arbitrary search space. In general, assume Ω is a compact metric space with metric D, though for most theorems and calculations assume Ω is finite (in which case D is a discrete metric). Let X1, X2,...,Xn denote Ω-valued random variables that are independent and identically distributed with uniform probability distribution U. X1, X2,...,Xm therefore represents a blind search of Ω. Next, let Y1, Y2,...,Ym denote Ω-valued random variables that are arbitrarily distributed. X1, X2,...,Xn therefore characterizes an assisted search of Ω.
That's our first version of Battleship - I've no problem with this section. But the next paragraph states
If we now let Ωm denote the m-fold Cartesian product of Ω, then X1, X2,...,Xm and Y1, Y2,...,Ym are m-valued random variables. Because the uniform probability on Ωm is just the m-fold product measure of U, X1, X2,...,Xm) is uniformly distributed on
= Ωm. Thus, by attending solely to the probabilistic
structure of searches, we represent the blind search := (X1, X2,...,Xm) as having a m-dimensional uniform distribution with respect to a metric D~ that suitably extends to the metric D on Ω. Moreover, we represent the assisted search := (Y1, Y2,...,Ym ), in searching for an arbitrary subset of , as having distribution on .
But all these tildes are superﬂuous. Dropping them, we see that the probabilistic connection between a blind search and an assisted search can be entirely characterized in terms of a search space , a metric D that induces a compact topology on Ω, a target T included
in Ω, a uniform probability measure U on induced by D, and an arbitrary probability measure φ on Ω. U represents the probabilistic structure of a blind search, and φ represents the probabilistic structure of an assisted search.
Now, is a subset of Ωm - and there are 2|Ω| m -1 non-empty subsets! A successful search means that ∈ , i.e., Yn ∈ Tn for all 1 ≤ n ≤ m. So, a stationary target would be not represented by
as one may naively expect, but by
but most of the targets don't fit this pattern.
Of course you can claim that knowing that you target doesn't move is additional information. But I haven't encountered a definition of search which expects you to be right on target each time...
P.S.: I tried to reach R. Marks via email - and I left an entry at W. Dembski's blog...
P.P.S.: some details.