Concentration inequalities for randomly permuted sums

DOI10.1007/978-3-030-26391-1_17zbMATH Open1443.60019arXiv1805.03579OpenAlexW2801322205MaRDI QIDQ2190646FDOQ2190646

Mélisande Albert

Publication date: 21 June 2020

Abstract: Initially motivated by the study of the non-asymptotic properties of non-parametric tests based on permutation methods, concentration inequalities for uniformly permuted sums have been largely studied in the literature. Recently, Delyon et al. proved a new Bernstein-type concentration inequality based on martingale theory. This work presents a new proof of this inequality based on the fundamental inequalities for random permutations of Talagrand. The idea is to first obtain a rough inequality for the square root of the permuted sum, and then, iterate the previous analysis and plug this first inequality to obtain a general concentration of permuted sums around their median. Then, concentration inequalities around the mean are deduced. This method allows us to obtain the Bernstein-type inequality up to constants, and, in particular, to recovers the Gaussian behavior of such permuted sums under classical conditions encountered in the literature. Then, an application to the study of the second kind error rate of permutation tests of independence is presented.

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

zbMATH Keywords

concentration inequalitiesrandom permutations

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Combinatorial probability (60C05)

Cited In (8)

• Minimax optimality of permutation tests
• Concentration for Independent Permutations
• Large partial random permutations of conditionally convergent series
• Comparing a large number of multivariate distributions
• The probability distribution of sums of elements in disjoint parts of a random permutation
• Concentration for locally acting permutations
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Differential privacy in constant function market makers

This page was built for publication: Concentration inequalities for randomly permuted sums

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