Concentration inequalities for order statistics

DOI10.1214/ECP.V17-2210zbMATH Open1349.60021arXiv1207.7209OpenAlexW3103700089WikidataQ58374454 ScholiaQ58374454MaRDI QIDQ742953FDOQ742953

Stéphane Boucheron, Maud Thomas

Publication date: 22 September 2014

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

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.

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

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

zbMATH Keywords

order statisticsconcentration inequalities[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=R%EF%BF%BD%EF%BF%BDnyi%27s+representation&go=Go R��nyi's representation]entropy methodEfron-Stein inequalities

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)

Cited In (20)

• Non-asymptotic bounds for percentiles of independent non-identical random variables
• Improved one-sided deviation inequalities under regularity assumptions for product measures
• Metastability in a condensing zero-range process in the thermodynamic limit
• Multiple prizes in tournaments with career concerns
• Title not available (Why is that?)
• The variance of the $\ell _p^n$-norm of the Gaussian vector, and Dvoretzky’s theorem
• Concentration Inequalities for Statistical Inference
• Title not available (Why is that?)
• Constant rate distributions on partially ordered sets
• Optimal Stopping of a Random Sequence with Unknown Distribution
• A note on transportation cost inequalities for diffusions with reflections
• Sequential estimation of quantiles with applications to A/B testing and best-arm identification
• Maximum variance of order statistics
• Tail index estimation, concentration and adaptivity
• Cross-validation on extreme regions
• Sparse equisigned PCA: algorithms and performance bounds in the noisy rank-1 setting
• Non asymptotic variance bounds and deviation inequalities by optimal transport
• Concentration order on a metric space, with some statistical applications
• A localization-delocalization transition for nonhomogeneous random matrices
• Functional inequalities for forward and backward diffusions

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)