Discrete Search: Probabilistic Existence Theorems
As an example, consider the following
group testing problem. Let a set of n factors is given and assume that only
some of them are significant. Let T be the (unknown) group of significant
factors. It is required to determine T by testing as few as possible factor
groups.
Assume that the result of the test for the factor group X
can be written in the form
f(X,T) = min {K, N(X,T)},
where N(X,T) is the number of elements in the intersection
of X and T and K is an integer. (In binary screening problems K=1, in the
multiaccess channel problem K=2 and in additive screening K=n.)
To prove existence of a deterministic design of length N
separating all factor groups it is enough to prove that the probability of
separation of these groups is positive for a random design. Using this general
principle suggested in an early work of A.Renyi, we can derive upper
bounds for the length of optimal nonsequential group testing designs in
different cases when the information about the number of elements in T
and X is available. A general way of derivation of asymptotic upper bounds,
when n tends to infinity, is also available.
The technique is applied to many discrete search problems
including searching with lies.
References
·
Ermakov S.M., Zhigljavsky A.A. (1987)
Mathematical Theory of Optimal Experiment. Nauka,
· O'Geran J., Wynn H.P., Zhigljavsky A.A. (1991) Search. Acta Applicandae Mathematicae, 25, 241-276.
· O'Geran J., Wynn H.P., Zhigljavsky A.A. Mastermind as a test-bed for search algorithms. Chance, 1993, 6, 31-37.
· Wynn H.P., Zhigljavsky A.A. (1994) The theory of search from a statistical viewpoint, Test, 3, No. 2, 1-45 (with discussion).
· Zhigljavsky A.A., Zabalkanskaya L. (1996) Existence theorems for some group testing strategies, Journal of Statistical Planning and Inference, 55, No 2, 151-173.
· Zhigljavsky A.A. (2003) Probabilistic existence theorems in group testing, Journal of Statistical Planning and Inference, vol. 115, No. 1, 1 - 43.