On the cutoff point for pairwise enabling in multiple access systems

Let p⁰ 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⩽p⁰⩽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⁰ ⩽0.5 for unbounded arrival sequences, and that p⁰≈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⩽p⁰_I⩽0.387 under the intermediate reservation model and 0.436⩽p⁰_G⩽1/√3 under the Gudjohnsen reservation model, respectively