On the cutoff point for pairwise enabling in multiple access systems

摘要

Let p/sup 0/ be the minimum Bernoulli probability for which pairwise enabling is an optimal group testing algorithm under a Bernoulli arrival sequence model. In a previous work, it was shown that 0.430>or=p/sup 0/>or=0.568 for unbounded Bernoulli arrival sequences, based on the threshold probabilities at which certain triple enabling algorithms (operating with and without the aid of a helpful genie, respectively) become more efficient. By deriving constructive results using the powerful but seemingly nonconstructive upper-bounding technique introduced by N.A. Mikhailov and B.S. Tsybakov (1981), the author sharpens this result by proving that p/sup 0/>or=0.5 for unbounded arrival sequences, and that p/sup 0/ approximately=0.545 in the finite arrival sequence model recently studied by F.K. Hwang and X.M. Chang (1987). The present results for unbounded arrival sequences also extend to the reservation schemes considered by Hwang and Chang, where it is now shown that 0.386>or=p/sup 0//sub I/>or=0.387 under the intermediate reservation model and 0.436>or=p/sup 0//sub G/>or=1/ square root 3 under the Gudjohnsen reservation model, respectively.