ON COMBINATORIAL TESTING PROBLEMS

• 成果类型: Article
• 署名作者: Addario-Berry, Louigi; Broutin, Nicolas; Devroye, Luc; Lugosi, Gabor
• 署名单位: McGill University; McGill University; ICREA; Pompeu Fabra University; McGill University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/10-AOS817
• 发表日期: 2010
• 页码: 3063-3092
• 关键词: high dimension; uniform

摘要

We study a class of hypothesis testing problems in which, upon observing the realization of an n-dimensional Gaussian vector, one has to decide whether the vector was drawn from a standard normal distribution or, alternatively, whether there is a subset of the components belonging to a certain given class of sets whose elements have been contaminated, that is, have a mean different from zero. We establish some general conditions under which testing is possible and others under which testing is hopeless with a small risk. The combinatorial and geometric structure of the class of sets is shown to play a crucial role. The bounds are illustrated on various examples.