Concentration inequalities for order statistics

Stéphane Boucheron, Maud Thomas

Type: Article

Publication Date: 2012-01-01

Citations: 46

DOI: https://doi.org/10.1214/ecp.v17-2210

Abstract

This note describes non-asymptotic variance and tail bounds for order statistics of samples of independent identically distributed random variables. When the sampling distribution belongs to a maximum domain of attraction, these bounds are checked to be asymptotically tight. When the sampling distribution has a non decreasing hazard rate, we derive an exponential Efron-Stein inequality for order statistics, that is an inequality connecting the logarithmic moment generating function of order statistics with exponential moments of Efron-Stein (jackknife) estimates of variance. This connection is used to derive variance and tail bounds for order statistics of Gaussian samples that are not within the scope of the Gaussian concentration inequality. Proofs are elementary and combine Rényi's representation of order statistics with the entropy approach to concentration of measure popularized by M. Ledoux.

Locations

arXiv (Cornell University) - View - PDF
HAL (Le Centre pour la Communication Scientifique Directe) - View
DataCite API - View
Electronic Communications in Probability - View - PDF

Similar Works

Action	Title	Year	Authors
+	Inequalities for order statistics of samples from distributions with monotone hazard rate	2016	V. G. Ushakov N. G. Ushakov
+	Concentration inequalities for order statistics Using the entropy method and Rényi's representation	2012	Stéphane Boucheron Marlin U. Thomas
+	Moments of Order Statistics from Length-Biased Exponential Distribution and Associated Inference	2020	Zuber Akhter Jagdish Saran Kanika Verma Narinder Pushkarna
+	Entropic Central Limit Theorem for Order Statistics	2022	Martina Cardone Alex Dytso Cynthia Rush
+	Order statistics of uniform, logistic and exponential distributions	2016	Collins O Okoyo
+	Exponential inequalities for tail probabilities of generalized order statistics	2005	Frank Marohn
+ PDF Chat	On characterizations of continuous distributions in terms of moments of order statistics when the sample size is random	1998	Z. Grudzieú Dominik Szynal
+ PDF Chat	A Characterization of the Exponential Distribution by Order Statistics	1971	M. M. Desu
+	On the asymptotics of numbers of observations in random regions determined by order statistics	2011	Anna Dembińska George Iliopoulos
+	The concentration inequalities of functions of independent random variables	2007	Xiaogang Zhang
+	Moment inequalities for order statistics with applications to characterizations of distributions	1991	Lesław Gajek Ursula Gather
+	Characterization of the Exponential Distribution Using Lower Moments of Order Statistics	1975	Z. Govindarajulu
+	Limit theorems for order statistics from exponentials	2015	Yu Miao Rujun Wang André Adler
+	Order Statistics, Quantiles, and Coverages	2014	Jean Dickinson Gibbons S. Chakraborti
+	Order Statistics, Quantiles, and Coverages	2010
+	Order Statistics, Quantiles, and Coverages	2020	Jean Dickinson Gibbons S. Chakraborti
+	Variance estimation for order statistics and kernel-smoothed sample quantiles	2006	KY Cheung Sms Lee
+	Improving the hartley-David-Gumbel bound for the mean of extreme order statistics	1990	N. Balakrishnan
+	On a Characterization of the Exponential Distribution by Order Statistics	1985	Maria Iwińska
+	A characterization of exponential distributions based on order statistics	1980	C. B. Bell Y. Rama Krishna Sarma

Works That Cite This (40)

Action	Title	Year	Authors
+	Tail index estimation, concentration and adaptivity	2015	Stéphane Boucheron Maud Thomas
+ PDF Chat	The HulC: confidence regions from convex hulls	2023	Arun Kumar Kuchibhotla Sivaraman Balakrishnan Larry Wasserman
+	Iterative Least Trimmed Squares for Mixed Linear Regression.	2019	Yanyao Shen Sujay Sanghavi
+	Lower bounds in multiple testing: A framework based on derandomized proxies	2020	M. G. Rabinovich Michael I. Jordan Martin J. Wainwright
+ PDF Chat	Non-asymptotic bounds for percentiles of independent non-identical random variables	2019	Dong Xia
+	Improved deviation inequalities for convex functions	2018	Kévin Tanguy
+ PDF Chat	Functional inequalities for forward and backward diffusions	2020	Daniel Bartl Ludovic Tangpi
+ PDF Chat	Metastability in a condensing zero-range process in the thermodynamic limit	2016	Inés Armendáriz Stefan Großkinsky Michail Loulakis
+	On $\ell_p$-Gaussian-Grothendieck problem	2020	Wei–Kuo Chen Arnab Sen
+	SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax	2015	Weijie Su Emmanuel J. Candès

Works Cited by This (7)

Action	Title	Year	Authors
+ PDF Chat	About the constants in Talagrand's concentration inequalities for empirical processes	2000	Pascal Massart
+ PDF Chat	The Concentration of Measure Phenomenon	2005	Michel Ledoux
+ PDF Chat	Concentration inequalities using the entropy method	2003	Stéphane Boucheron Gábor Lugosi Pascal Massart
+	A General Theory for Jackknife Variance Estimation	1989	Jun Shao Changbao Wu
+	The Jackknife Estimate of Variance	1981	B. Efron C. Stein
+	Discrete Isoperimetric Inequalities and the Probability of a Decoding Error	2000	Jean–Pierre Tillich Gilles Zémor
+	A Remark on Hypercontractivity and Tail Inequalities for the Largest Eigenvalues of Random Matrices	2003	Michel Ledoux