Concentration inequalities for order statistics

DOI10.1214/ECP.V17-2210MaRDI QIDQ742953zbMATH OpenOpenAlexWikidataFDO

Authors Stéphane Boucheron, Maud Thomas

Publication date 22 September 2014

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.7209

zbMATH Keywords

order statisticsconcentration inequalitiesentropy methodEfron-Stein inequalitiesRényi's representation

Mathematics Subject Classification ID

Extreme value theory; extremal stochastic processes (60G70) Statistics of extreme values; tail inference (62G32) Inequalities; stochastic orderings (60E15) Order statistics; empirical distribution functions (62G30)

Abstract: This note describes non-asymptotic variance and tail bounds for order statistics of samples of independent identically distributed random variables. Those bounds are checked to be asymptotically tight when the sampling distribution belongs to a maximum domain of attraction. If the sampling distribution has non-decreasing hazard rate (this includes the Gaussian distribution), we derive an exponential Efron-Stein inequality for order statistics: an inequality connecting the logarithmic moment generating function of centered order statistics with exponential moments of Efron-Stein (jackknife) estimates of variance. We use this general connection to derive variance and tail bounds for order statistics of Gaussian sample. Those bounds are not within the scope of the Tsirelson-Ibragimov-Sudakov Gaussian concentration inequality. Proofs are elementary and combine R'enyi's representation of order statistics and the so-called entropy approach to concentration inequalities popularized by M. Ledoux.

Recommendations

• Maximum variance of order statistics
• Stability of order statistics under dependence
• Extreme variances of order statistics in dependent samples
• Exponential inequalities for tail probabilities of generalized order statistics
• Bounds for absolute moments of order statistics

Cited in

(21)

• Functional inequalities for forward and backward diffusions
• Concentration inequalities for statistical inference
• Non asymptotic variance bounds and deviation inequalities by optimal transport
• Tail index estimation, concentration and adaptivity
• Non-asymptotic bounds for percentiles of independent non-identical random variables
• A note on transportation cost inequalities for diffusions with reflections
• scientific article; zbMATH DE number 3969959 (Why is no real title available?)
• scientific article; zbMATH DE number 954480 (Why is no real title available?)
• Metastability in a condensing zero-range process in the thermodynamic limit
• Constant rate distributions on partially ordered sets
• Some superconcentration inequalities for extrema of stationary Gaussian processes
• Optimal stopping of a random sequence with unknown distribution
• Cross-validation on extreme regions
• Multiple prizes in tournaments with career concerns
• Concentration order on a metric space, with some statistical applications
• Improved one-sided deviation inequalities under regularity assumptions for product measures
• Maximum variance of order statistics
• Sequential estimation of quantiles with applications to A/B testing and best-arm identification
• The variance of the \(\ell _p^n\)-norm of the Gaussian vector, and Dvoretzky's theorem
• A localization-delocalization transition for nonhomogeneous random matrices
• Sparse equisigned PCA: algorithms and performance bounds in the noisy rank-1 setting

This page was built for publication: Concentration inequalities for order statistics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742953)