A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
1952/12/01 by Herman Chernoff · 3,628 citations
Decision Sciences · Mathematics · #Advanced Statistical Process Monitoring #Combinatorics #F-distribution #Function (biology) #Mathematics #Measure (data warehouse) #Moment (physics) #Probability distribution #Sample size determination #Simple (philosophy) #Statistical Methods and Inference #Statistical Methods in Clinical Trials #Statistics #Value (mathematics)
paper · pdf · doi:10.1214/aoms/1177729330
published in The Annals of Mathematical Statistics 23(4), 493-507 (Institute of Mathematical Statistics)
openalex publication_date 1952/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 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 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 Privacy
- Optimal Bipartite Network Clustering
- An effective associative memory for pattern recognition
- A Tight Bound of Tail Probabilities for a Discrete-time Martingale with 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
- A Simple Sample Size Formula for Estimating Means of Poisson Random Variables
- 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 Distributions
- Multipath Private Communication: An Information Theoretic Approach
- Learning under p-Tampering Attacks
- Empirically Estimable Classification Bounds Based on a New Divergence Measure
- Distributed Verification of Rare Properties using Importance Splitting Observers
- Chernoff bounds for branching random walks
- Stealthy Communication over Adversarially Jammed Multipath Networks
- On Voronoi diagrams and dual Delaunay complexes on the information-geometric Cauchy manifolds
- S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
- Non-Parametric Methods Applied to the N-Sample Series Comparison
- On Estimation and Optimization of Mean Values of Bounded Variables
- Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
- A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias
- Thermodynamic assessment of probability distribution divergencies and Bayesian model comparison
- Handel: Practical Multi-Signature Aggregation for Large Byzantine Committees
- Quantum Stein's lemma revisited, inequalities for quantum entropies, and a concavity theorem of Lieb
- Confidence Estimation in Structured Prediction
- Error Rate Bounds in Crowdsourcing Models
- Monte-Carlo optimizations for resource allocation problems in stochastic network systems
- Catching the head, tail, and everything in between: a streaming algorithm for the degree distribution
- Position-Based Quantum Cryptography
- Forbidding intersection patterns between layers of the cube
- A New Framework of Multistage Hypothesis Tests
- Sequential Tests of Statistical Hypotheses with Confidence Limits
- Cross-entropy optimisation of importance sampling parameters for\n statistical model checking
- Scalable Algorithms for the Sparse Ridge Regression
- On an Improvement over Rényi's Equivocation Bound
- Concentration Bounds for the Collision Estimator
- Dynamic Maximal Independent Set
- Learning Poisson Binomial Distributions
- Privacy-preserving Learning via Deep Net Pruning
- Scaling Behaviors of Wireless Device-to-Device Communications with Distributed Caching
- Tail asymptotics of signal-to-interference ratio distribution in spatial cellular network models
- Critical Branching Random Walks with Small Drift
- A simple sketching algorithm for entropy estimation
- Secure quantum key distribution against correlated leakage source
- Binary and Multi-Bit Coding for Stable Random Projections
- More Tight Bounds for Active Self-Assembly Using an Insertion Primitive
- Citations, Sequence Alignments, Contagion, and Semantics: On Acyclic Structures and their Randomness
- Computationally Efficient Covert Communication
- Random induced subgraphs of Cayley graphs induced by transpositions
- Graph Codes for Distributed Instant Message Collection in an Arbitrary Noisy Broadcast Network
- On the Exponential Probability Bounds for the Bernoulli Random Variables
- Discrepancy and Signed Domination in Graphs and Hypergraphs
- Strong converse rate for asymptotic hypothesis testing in type III
- New Non-asymptotic Random Channel Coding Theorems
- Remote Preparation of Quantum States
- A supplement to the laws of large numbers and the large deviations
- Characterization of Generalized Alpha-Beta Divergence and Associated Entropy Measures
- Distillation of secret key and entanglement from quantum states
- Tight co-degree condition for the existence of loose Hamilton cycles in 3-graphs
- Scaling up graph homomorphism for classification via sampling
- Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
- On Approximating Frequency Moments of Data Streams with Skewed Projections
- Predicting Features of Quantum Systems from Very Few Measurements
- Log-Quadratic Bounds for the Gaussian Q-function
- Measuring the internal state of a single atom without energy exchange
- A survey of Chernoff and Hoeffding bounds
- Rewriting the Budget: A General Framework for Black-Box Attacks Under Cost Asymmetry
- Balanced Spanning Caterpillars
- Subgaussian Tail Bounds via Stability Arguments
- Optimal Chernoff and Hoeffding Bounds for Finite State Markov Chains
- Chernoff Information between Gaussian Trees
- Linear Probing with Constant Independence
- Probability Estimation with Truncated Inverse Binomial Sampling
- Learning opening books in partially observable games: using random seeds in Phantom Go
- Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
- Applications of the theory of records in the study of random trees
- A Reversion of the Chernoff Bound
- ABKD: Pursuing a Proper Allocation of the Probability Mass in Knowledge Distillation via α-β-Divergence
- (Learned) Frequency Estimation Algorithms under Zipfian Distribution
- Wireless Device-to-Device Communications with Distributed Caching
- Sampling 3-colourings of regular bipartite graphs
- Experimental Side-Channel-Secure Quantum Key Distribution over 200 km
- Multistage Estimation of Bounded-Variable Means
- Imaginary time spectral transforms for excited-state preparation
- Privacy-Utility Management of Hypothesis Tests
- Towards a practical, theoretically sound algorithm for random generation in finite groups
- Beta processes, stick-breaking, and power laws
- Topological and Algebraic Properties of Chernoff Information between Gaussian Graphs
- Large components in random induced subgraphs of n-cubes
- Vector-Neuron Models of Associative Memory
- Sequential Estimation Methods from Inclusion Principle
- TSEB: More Efficient Thompson Sampling for Policy Learning
- Noise-robust discrimination of incoherent point sources with spatial-mode demultiplexing
- A Truncation Approach for Fast Computation of Distribution Functions
- Minimax Euclidean Separation Rates for Testing Convex Hypotheses in ℝd
- Volume Doubling Condition and a Local Poincaré Inequality on Unweighted Random Geometric Graphs
- Entanglement Theory and the Quantum Simulation of Many-Body Physics
- New Optional Stopping Theorems and Maximal Inequalities on Stochastic Processes
- Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms
- Computing Linear Transformations with Unreliable Components
- A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices
- Phase transition for accessibility percolation on hypercubes
- Communication as Voting
- Sparse Multipartite Graphs as Partition Universal for Graphs of Bounded-Degrees
- Distilled Sensing: Adaptive Sampling for Sparse Detection and Estimation
- An elementary proof of a theorem of Johnson and Lindenstrauss
- Randomized broadcast in networks
- Characterizing the Sample Complexity of Private Learners
- Decision Making in Star Networks with Incorrect Beliefs
- Observation of Genuine High-dimensional Multi-partite Non-locality in Entangled Photon States
- Scalable Approximate Biclique Counting over Large Bipartite Graphs
- Block Compressed Sensing Based Distributed Device Detection for M2M Communications
- Bounding Neyman-Pearson Region with f-Divergences
- Relative Canonical Network Ensembles -- (Mis)characterizing Small-World Networks
- On the Non-asymptotic and Sharp Lower Tail Bounds of Random Variables
- Stratified Splitting for Efficient Monte Carlo Integration
- Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm
- Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes
- Euclidean lattices, theta invariants, and thermodynamic formalism
- Edge-colouring random graphs
- Guaranteed Monte Carlo Methods for Bernoulli Random Variables
- Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube
- Non-Asymptotic Chernoff Lower Bound and Its Application to Community Detection in Stochastic Block Model
- Site-by-site quantum state preparation algorithm for preparing vacua of fermionic lattice field theories
- Convergence rates for posterior distributions and adaptive estimation
- Fano’s Inequality for Random Variables
- A Better Resource Allocation Algorithm with Semi-Bandit Feedback
- Active Regression via Linear-Sample Sparsification
- How random are a learner's mistakes?
- Average-case analysis of algorithms for matchings and related problems
- Dynamic traitor tracing for arbitrary alphabets: Divide and conquer
- A Chernoff-type Lower Bound for the Gaussian Q-function
- Classical no-cloning theorem under Liouville dynamics by non-Csiszár f-divergence
- A Chernoff Bound for Random Walks on Expander Graphs
- Tomography scheme for two spin-12qubits in a double quantum dot
- Probability of error, equivocation, and the Chernoff bound
- Zero-One Laws for Sparse Random Graphs
- On the Reliability Roots of Simplicial Complexes and Matroids
- On Size Ramsey Number of Paths, Trees and Circuits. II
- Fast Meta-Learning for Adaptive Hierarchical Classifier Design
- A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
- Edge coloring regular graphs of high degree
- FOCUS: DLLMs Know How to Tame Their Compute Bound
- Meta learning of bounds on the Bayes classifier error
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Quantum Chernoff bound as a measure of nonclassicality for one-mode Gaussian states
- Goodness-of-fit tests via phi-divergences
- The Extremal Function for Complete Minors
- Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
- The scaling window of the 2‐SAT transition
- Clustering Gene Expression Patterns
- On the hardness of approximating vertex cover
- Bridging AIC and BIC: A New Criterion for Autoregression
- Error exponent in asymmetric quantum hypothesis testing and its application to classical-quantum channel coding
- A Scene Image is Nonmutually Exclusive—A Fuzzy Qualitative Scene Understanding
- The Chernoff lower bound for symmetric quantum hypothesis testing
- User-Friendly Tail Bounds for Sums of Random Matrices
- Optimally ranking unrankable tournaments
- On the maximum cardinality of a consistent set of arcs in a random tournament
- Linear Probing with Constant Independence
- GRANITE : a Byzantine-Resilient Dynamic Gossip Learning Framework
- On the complexity of approximating the independent set problem
- An ?(n 4/3) lower bound on the randomized complexity of graph properties
- Generalized Error Exponents for Small Sample Universal Hypothesis Testing
- Awareness and Movement vs. the Spread of Epidemics - Analyzing a Dynamic Model for Urban Social/Technological Networks
- Thwarting the Photon Number Splitting Attack with Entanglement Enhanced BB84 Quantum Key Distribution
- Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
- Optimal Mechanism for Randomized Responses under Universally Composable Security Measure
- The height of a random binary search tree
- Device-independent quantum authorization based on the Clauser-Horne-Shimony-Holt game
- Probabilistic construction of deterministic algorithms: Approximating packing integer programs
- Concentration from Product Moments via an Additional Element of Randomness
- Unifying quantum measurement constructions via a relative-entropy minimum change principle
- Universal Online Contention Resolution with Preselected Order
- A statistical theory for the measurement and estimation of Rayleigh fading channel
- Measurement-Device-Independent Quantum Key Distribution Over a 404 km Optical Fiber
- Towards Quantum Universal Hypothesis Testing
- Scalable twin-field quantum key distribution network enabled by adaptable architecture
- Enhancing Evolutionary Conversion Rate Optimization via Multi-armed Bandit Algorithms
- On Coupon Colorings of Graphs
- On a two-truths phenomenon in spectral graph clustering
- Unconditional Security of Sending or Not Sending Twin-Field Quantum Key Distribution with Finite Pulses
- Quantum correlations and distinguishability of quantum states
- When is the Chernoff Exponent for Quantum Operations Finite?
- A differential geometric approach to statistical inference on the basis of contrast functionals
- A Framework for Quantum-Secure Device-Independent Randomness Expansion
- Non-blind watermarking of network flows
- Higher key rate of measurement-device-independent quantum key distribution through joint data processing
- Computationally Efficient Estimators for Dimension Reductions Using Stable Random Projections
- Matrix Chernoff concentration bounds for multipartite soft covering and expander walks
- Strongly continuous and locally equi-continuous semigroups on locally convex spaces
- Divergence, Optimization and Geometry
- On Divergences and Informations in Statistics and Information Theory
- Information Theory and Statistics: A Tutorial
- Graph-Based Prediction Models for Data Debiasing
- A convergence law for continuous logic and continuous structures with finite domains
- Query Complexity of Approximate Equilibria in Anonymous Games
- Range Counting Oracles for Geometric Problems
- The greedy coloring is a bad probabilistic algorithm
- 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