The binomial group-testing problem consists of finding by group tests all defectives in a given set of items, each of which independently has probability p of being defective. The conjecture that the expected number of tests under an optimal testing algorithm is nondecreasing in p has recently been proved by transplanting the probability structure of the set of defective items. It is proved that this approach works in a much broader setting in which the states of items are dependent and the tests have k possible outputs. The results apply to the collision-resolution problem in random-multiple-access-channel communication.>

The group testing problem is to find by group tests all defectives in a given set of items each of which independently has probability p of being defective. The group testing problem originated with the famous Dorfman’s blood testing problem and has since found many industrial applications including a recent one on multiple-access communication. Unfortunately, optimal group testing algorithms are not known in general. In particular, a very plausible conjecture that the expected number of tests should be nondecreasing in p for $0\leqq p < 1$ has remained open since 1981. In this paper we prove this conjecture by an innovative approach.

In the estimation problem of a two-state stationary Markov process with Gaussian white noise added, the optimal smoother is a two-filter smoother. In a special case, the performance of the optimal nonlinear filter and smoother is evaluated analytically. Some asymptotic results are also derived.