*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

- 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 X_{1}, X_{2},...,X_{n}denote Ω-valued random variables that are independent and identically distributed with uniform probability distributionU. X_{1}, X_{2},...,X_{m}therefore represents a blind search of Ω. Next, let Y_{1}, Y_{2},...,Y_{m}denote Ω-valued random variables that are arbitrarily distributed. X_{1}, X_{2},...,X_{n}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 X_{1}, X_{2},...,X_{m}and Y_{1}, Y_{2},...,Y_{m}are m-valued random variables. Because the uniform probability on Ω^{m}is just the m-fold product measure ofU, X_{1}, X_{2},...,X_{m}) is uniformly distributed on

= Ω^{m}. Thus, by attending solely to the probabilistic

structure of searches, we represent the blind search := (X_{1}, X_{2},...,X_{m}) 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 := (Y_{1}, Y_{2},...,Y_{m}), 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 measureUon induced by D, and an arbitrary probability measure φ on Ω.Urepresents 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., Y

_{n}∈ T

_{n}for all 1 ≤ n ≤ m. So, a stationary target would be not represented by

T

^{n}

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.

This comment has been removed by the author.

ReplyDeleteThe definition of search is not driven by a desire to model physical processes sensibly, but by a desire to establish the basis for a recursion of probability measures. The n-tuple realization of a "search" is a query, and cannot necessarily be interpreted as n queries. An interesting point here is that Dembski and Marks have nothing to say about the source of the value of n. It is not obtained as part of the "search for a search." ;)

ReplyDelete