Concentration inequalities for randomly permuted sums

DOI10.1007/978-3-030-26391-1_17MaRDI QIDQ2190646zbMATH OpenOpenAlexFDO

Authors Mélisande Albert

Publication date 21 June 2020

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)

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.

Recommendations

• A non-uniform concentration inequality for a random permutation sum
• A Bernstein-type inequality for functions of bounded interaction
• Concentration inequalities via zero bias couplings
• A Bernstein type inequality for sums of selections from three dimensional arrays
• Concentration inequalities. A nonasymptotic theory of independence

Cited in

(11)

• Concentration for Independent Permutations
• The probability distribution of sums of elements in disjoint parts of a random permutation
• A Bernstein type inequality for sums of selections from three dimensional arrays
• Concentration for locally acting permutations
• Minimax optimality of permutation tests
• Concentration inequalities via zero bias couplings
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• A non-uniform concentration inequality for a random permutation sum
• Differential privacy in constant function market makers
• Large partial random permutations of conditionally convergent series
• Comparing a large number of multivariate distributions

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)