7
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      On combinatorial testing problems

      Preprint

      , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          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.

          Related collections

          Most cited references 21

          • Record: found
          • Abstract: not found
          • Article: not found

          On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries

              Bookmark
              • Record: found
              • Abstract: found
              • Article: found
              Is Open Access

              Higher criticism for detecting sparse heterogeneous mixtures

              Higher criticism, or second-level significance testing, is a multiple-comparisons concept mentioned in passing by Tukey. It concerns a situation where there are many independent tests of significance and one is interested in rejecting the joint null hypothesis. Tukey suggested comparing the fraction of observed significances at a given \alpha-level to the expected fraction under the joint null. In fact, he suggested standardizing the difference of the two quantities and forming a z-score; the resulting z-score tests the significance of the body of significance tests. We consider a generalization, where we maximize this z-score over a range of significance levels 0<\alpha\leq\alpha_0. We are able to show that the resulting higher criticism statistic is effective at resolving a very subtle testing problem: testing whether n normal means are all zero versus the alternative that a small fraction is nonzero. The subtlety of this ``sparse normal means'' testing problem can be seen from work of Ingster and Jin, who studied such problems in great detail. In their studies, they identified an interesting range of cases where the small fraction of nonzero means is so small that the alternative hypothesis exhibits little noticeable effect on the distribution of the p-values either for the bulk of the tests or for the few most highly significant tests. In this range, when the amplitude of nonzero means is calibrated with the fraction of nonzero means, the likelihood ratio test for a precisely specified alternative would still succeed in separating the two hypotheses.
                Bookmark

                Author and article information

                Journal
                24 August 2009
                2010-11-19
                Article
                10.1214/10-AOS817
                0908.3437

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                IMS-AOS-AOS817
                Annals of Statistics 2010, Vol. 38, No. 5, 3063-3092
                Published in at http://dx.doi.org/10.1214/10-AOS817 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
                math.ST math.CO stat.TH
                vtex

                Comments

                Comment on this article