## Abstract

We consider nonadaptive group testing with Bernoulli tests, where each item is placed in each test independently with some fixed probability. We give a tight threshold on the maximum number of tests required to find the defective set under optimal Bernoulli testing. Achievability is given by a result of Scarlett and Cevher; here we give a converse bound showing that this result is best possible. Our new converse requires three parts: a typicality bound generalising the trivial counting bound, a converse on the COMP algorithm of Chan et al, and a bound on the SSS algorithm similar to that given by Aldridge, Baldassini, and Johnson. Our result has a number of important corollaries, in particular that, in denser cases, Bernoulli nonadaptive group testing is strictly worse than the best adaptive strategies.

Original language | English |
---|---|

Pages (from-to) | 7142-7148 |

Journal | IEEE Transactions on Information Theory |

Volume | 63 |

Issue number | 11 |

Early online date | 4 Sep 2017 |

DOIs | |

Publication status | Published - 1 Nov 2017 |

## Keywords

- Capacity planning
- Detection algorithms
- Electronic mail
- Entropy
- Error probability
- Testing

## ASJC Scopus subject areas

- Information Systems
- Computer Science Applications
- Library and Information Sciences