## Tuesday, October 20, 2009

### W. Dembski's and R. Marks's The Search for a Search and my major problem with it

William Dembski and Robert Marks announced a new paper The Search for a Search: Measuring the Information Cost of Higher Level Search (draft) which should appear in a peer-reviewed journal at any moment.

My problem: When I read the term search for a target without any qualifier, I imagine that
1. the target is fix
2. 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:
1. all ships are of size one
2. you don't know how many ships there are
3. 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:
1. the position and the number of the ships changes each round
2. 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

Tn

as one may naively expect, but by

T×Ω×...×Ω
∪ Ω×T×Ω×...×Ω
∪ Ω×Ω×T×Ω×...×Ω
∪...
∪ &Omega×Ω×...×&Omega×T

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.