A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
1952/12/01 by Herman Chernoff · 151 citations
Mathematics · Decision Sciences · #Statistical Methods and Inference #Advanced Statistical Process Monitoring #Statistical Methods in Clinical Trials
paper · pdf · doi:10.1214/aoms/1177729330
Abstract
In many cases an optimum or computationally convenient test of a simple hypothesis H0 against a simple alternative H1 may be given in the following form. Reject H0 if Sn = ∑nj=1 Xj \leqq k, where X1, X2, ⋯, Xn are n independent observations of a chance variable X whose distribution depends on the true hypothesis and where k is some appropriate number. In particular the likelihood ratio test for fixed sample size can be reduced to this form. It is shown that with each test of the above form there is associated an index ρ. If ρ1 and ρ2 are the indices corresponding to two alternative tests e = log ρ1/log ρ2 measures the relative efficiency of these tests in the following sense. For large samples, a sample of size n with the first test will give about the same probabilities of error as a sample of size en with the second test. To obtain the above result, use is made of the fact that P(Sn \leqq na) behaves roughly like mn where m is the minimum value assumed by the moment generating function of X - a. It is shown that if H0 and H1 specify probability distributions of X which are very close to each other, one may approximate ρ by assuming that X is normally distributed.
Citations
Cited by
- Zip Trees
- A randomized linear-time algorithm to find minimum spanning trees
- Profile forward regression screening for ultra-high dimensional semiparametric varying coefficient partially linear models
- Time-uniform, nonparametric, nonasymptotic confidence sequences
- The finite key effect of side-channel-secure quantum key distribution beyond post-selection technique
- Quantum Key Distribution Beyond Stationary Channels
- Rate-Distortion-Perception Theory: Redefining the Fundamental Limits of Information Representation
- Simple broadband signal detection at the fundamental limit
- Autonomous quantum processing unit: an autonomous thermal computing machine & its physical limitations
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- The Notion of Security for Probabilistic Cryptosystems
- Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
- Randomization Resilient To Sensitive Reconstruction
- General Classes of Lower Bounds on the Probability of Error in Multiple Hypothesis Testing
- Two non-regular extensions of the large deviation bound
- Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
- Scalable Verification of Markov Decision Processes
- Robustness of OLS to sample removals: Theoretical analysis and implications
- Spherical Regression under Mismatch Corruption with Application to Automated Knowledge Translation
- Principles of Quantum Communication Theory: A Modern Approach
- The evolution of random reversal graph
- A Note on the PAC Bayesian Theorem
- A note on tilted Sperner families with patterns
- Stability of the independence number of G(n, r, 1) graphs
- Generalized Variational Inference: Three arguments for deriving new Posteriors
- Fully Dynamic Spectral Sparsification for Directed Hypergraphs
- Bias-Class Discrimination of Universal QRAM Boolean Memories
- A Doubled Adjacency Spectral Embedding Approach to Graph Clustering
- Large Deviation inequalities for sums of positive correlated variables with clustering
- An Efficient Secret Communication Scheme for the Bosonic Wiretap Channel
- Asymptotic and non-asymptotic estimates for multivariate Laplace integrals
- A Deterministic Algorithm for the Vertex Connectivity Survivable Network\n Design Problem
- On the diameter of random uniform hypergraphs in dense regime
- Nonlinear Estimators and Tail Bounds for Dimension Reduction in l1 Using Cauchy Random Projections
- Finite Size Analysis of Decoy-State BB84 with Advantage Distillation
- Approximating Quadratic 0-1 Programming via SOCP
- A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
- The Mixed Birth-death/death-Birth Moran Process
- Bosonic data hiding: power of linear vs non-linear optics
- Payment-failure times for random Lightning paths
- Estimation of Entropy and Mutual Information
- Finite-Horizon Quickest Change Detection Balancing Latency with False Alarm Probability
- Distinguishability and Accessible Information in Quantum Theory
- Limit theorems for eigenvectors of the normalized Laplacian for random graphs
- Cycle Ramsey numbers for random graphs
- Connectivity of the k-out Hypercube
- Moment estimation in paired comparison models with a growing number of subjects
- Sequential Adversarial Hypothesis Testing
- Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training
- Chernoff Bounds and Saddlepoint Approximations for the Outage Probability in Intelligent Reflecting Surface Assisted Communication Systems
- Probability Inequalities for Sums of Bounded Random Variables
- Risk Estimation in Differential Fuzzing via Extreme Value Theory
- Robustness for expander graphs
- Sequential Change Detection Under A Markov Setup With Unknown Pre-Change and Post-Change Distributions
- Reliable Memories Built from Unreliable Components Based on Expander Graphs
- Concentration Inequalities for Bounded Random Vectors
- A sufficient condition for tail asymptotics of SIR distribution in downlink cellular networks
- Information Limits for Recovering a Hidden Community
- Selection and Estimation for Mixed Graphical Models
- A probabilistic demand side management approach by consumption admission control
- Frankl-Rödl type theorems for codes and permutations
- In-situ characterization of quantum devices with error correction
- Limiting behavior of relative Rényi entropy in a non-regular location shift family
- Dealing with ignorance: universal discrimination, learning and quantum correlations
- Extremely chaotic Boolean networks
- Near-Optimal Offline Reinforcement Learning via Double Variance\n Reduction
- Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the G(n,p) random model
- Chernoff-Hoeffding Inequality and Applications
- Binary Causal-Adversary Channels
- Algorithms and Hardness for Linear Algebra on Geometric Graphs
- Set Families with Low Pairwise Intersection
- Learning from networked examples
- A central limit theorem for partitions involving generalised divisor functions
- Elementary Tail Bounds on the Hypergeometric Distribution
- Learning Upper Lower Value Envelopes to Shape Online RL: A Principled Approach
- How the Degeneracy Helps for Triangle Counting in Graph Streams
- HiLoRA: Adaptive Hierarchical LoRA Routing for Training-Free Domain Generalization
- Inequalities, identities, and bounds for divided differences of the exponential function
- Computational Complexity of Probabilistic Turing Machines
- Operational Interpretations of the Chernoff Inequality
- An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
- Beyond Hoeffding and Chernoff: Trading conclusiveness for advantages in quantum hypothesis testing
- The gamma-ray emission from Radio Galaxies and their contribution to the Isotropic Gamma-Ray Background
- Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
- Approximation Algorithms for D-optimal Design
- Achieving Pareto Optimality in Games via Single-bit Feedback
- Cocycle stability in permutations of random simplicial complexes
- Testable algorithms for approximately counting edges and triangles in sublinear time and space
- Analyzing α-divergence in Gaussian Rate-Distortion-Perception Theory
- Privacy-Utility Tradeoff for Hypothesis Testing Over A Noisy Channel
- Strong converse bounds in quantum network information theory: distributed hypothesis testing and source coding
- Concentration Bounds for High Sensitivity Functions Through Differential\n Privacy
- Optimal Bipartite Network Clustering
- An effective associative memory for pattern recognition
- A Tight Bound of Tail Probabilities for a Discrete-time Martingale with\n Uniformly Bounded Jumps
- Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
- The multilayer random dot product graph
- The efficiency of the likelihood ratio to choose between a t-distribution and a normal distribution
- Very Sparse Stable Random Projections, Estimators and Tail Bounds for Stable Random Projections
- Ramsey numbers of graphs with most degrees bounded in random graphs
- Thompson Sampling for Combinatorial Semi-Bandits
- New constructions and bounds for nonabelian Sidon sets with applications to Turán-type problems
- Rate-optimal Meta Learning of Classification Error
- Concentration Inequalities for Branching Random Walk
- Domain size asymptotics for Markov logic networks
- Achieving quantum-limited sub-Rayleigh identification of incoherent sources with arbitrary intensities
- Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
- Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
- The practical issues of side-channel-secure quantum key distribution
- Central Binomial Tail Bounds
- Ensemble Estimation of Distributional Functionals via k-Nearest Neighbors
- Error exponents of quantum state discrimination with composite correlated hypotheses
- Generalized quantum Chernoff bound
- Worst-case Nonparametric Bounds for the Student T-statistic
- Generalized Leverage Score Sampling for Neural Networks
- Chernoff Index for Cox Test of Separate Parametric Families
- Asymptotic Properties of Random Voronoi Cells with Arbitrary Underlying Density
- On two relaxations of quadratically-constrained cardinality minimization
- The Application of Remote Sensing for Detecting Mass Graves: An Experimental Animal Case Study from Costa Rica*
- Martingale Couplings and Bounds on the Tails of Probability\n Distributions
- Learning under p-Tampering Attacks
- Empirically Estimable Classification Bounds Based on a New Divergence Measure
- Chernoff bounds for branching random walks
- Stealthy Communication over Adversarially Jammed Multipath Networks
- S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
- Non-Parametric Methods Applied to the N-Sample Series Comparison
- Deep sequencing of the X chromosome reveals the proliferation history of colorectal adenomas. [europepmc]
- The influence of population size, noise strength and behavioral task on best-encoded stimulus for neurons with unimodal or monotonic tuning curves. [europepmc]
- Self-Averaging Property of Minimal Investment Risk of Mean-Variance Model. [europepmc]
- Extending Wireless Rechargeable Sensor Network Life without Full Knowledge. [europepmc]
- Classifying Diverse Physical Activities Using "Smart Garments". [europepmc]
- Computational Information Geometry for Binary Classification of High-Dimensional Random Tensors. [europepmc]
- Ensemble Estimation of Information Divergence † . [europepmc]
- Approximations of Shannon Mutual Information for Discrete Variables with Applications to Neural Population Coding. [europepmc]
- Entropic Regularization of Markov Decision Processes. [europepmc]
- Utilizing Amari-Alpha Divergence to Stabilize the Training of Generative Adversarial Networks. [europepmc]
- On Voronoi Diagrams on the Information-Geometric Cauchy Manifolds. [europepmc]
- Supervised dimensionality reduction for big data. [europepmc]
- Threshold theorem in isolated quantum dynamics with stochastic control errors. [europepmc]
- Robust twin-field quantum key distribution through sending or not sending. [europepmc]
- Security Analysis of Sending or Not-Sending Twin-Field Quantum Key Distribution with Weak Randomness. [europepmc]
- Revisiting Chernoff Information with Likelihood Ratio Exponential Families. [europepmc]
- A central limit theorem for integer partitions into small powers. [europepmc]
- Performance of Test Supermartingale Confidence Intervals for the Success Probability of Bernoulli Trials. [europepmc]
- A Survey on Error Exponents in Distributed Hypothesis Testing: Connections with Information Theory, Interpretations, and Applications. [europepmc]
- Fast Proxy Centers for the Jeffreys Centroid: The Jeffreys-Fisher-Rao Center and the Gauss-Bregman Inductive Center. [europepmc]
- Joint Communication and Channel Discrimination. [europepmc]
- Observation of Genuine High-dimensional Multi-partite Non-locality in Entangled Photon States. [europepmc]
- Eliminating single points of trust: a hybrid quantum and post-quantum blockchain with distributed key generation. [europepmc]
- Weighted Chernoff Information and Optimal Loss Exponent in Context-Sensitive Hypothesis Testing. [europepmc]
- Moment Estimation in Paired Comparison Models with a Growing Number of Subjects [europepmc]
Related