Concentration estimates for functions of finite high‐dimensional random arrays

DOI10.1002/RSA.21171MaRDI QIDQ6063348zbMATH OpenOpenAlexFDO

Authors Pandelis Dodos, Konstantinos Tyros, Petros Valettas

Publication date 7 November 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

concentration inequalitiesdensity polynomial Hales-Jewett conjectureexchangeable random arraysmartingale difference sequencesquasirandomnessspreadable random arrays

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10) Combinatorial probability (60C05) Inequalities; stochastic orderings (60E15)

Abstract: Let $$ be a $d$-dimensional random array on $[n]$ whose entries take values in a finite set $mathcalX$, that is, $$ is an $mathcalX$-valued stochastic process indexed by the set $$ of all $d$-element subsets of $[n]:=1,dots,n$. We give easily checked conditions on $$ that ensure, for instance, that for every function $$ that satisfies $$ and $$ for some $p>1$, the random variable $$ becomes concentrated after conditioning it on a large subarray of $$. These conditions cover several classes of random arrays with not necessarily independent entries. Applications are given in combinatorics, and examples are also presented that show the optimality of various aspects of the results.

Recommendations

• Concentration inequalities for random tensors
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Sharp concentration of random polytopes
• On concentration functions of random variables

Cites work

• σ-algebras for quasirandom hypergraphs
• A concentration inequality for product spaces
• A density version of the Hales-Jewett theorem
• A generalization of the Lindeberg principle
• A measure-theoretic approach to the theory of dense hypergraphs
• A noncommutative martingale convexity inequality
• A structure theorem for stochastic processes indexed by the discrete hypercube
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Concentration inequalities for random tensors
• Concentration inequalities. A nonasymptotic theory of independence
• Concentration of normalized sums and a central limit theorem for noncorrelated random variables
• Deducing the density Hales-Jewett theorem from an infinitary removal lemma
• Dissociated random variables
• Estimates of moments and tails of Gaussian chaoses
• Finite exchangeable sequences
• Flag algebras
• Graph limits and exchangeable random graphs
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 891064 (Why is no real title available?)
• scientific article; zbMATH DE number 3339773 (Why is no real title available?)
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Hypergraphs, quasi-randomness, and conditions for regularity
• Large networks and graph limits
• Linear equations in primes
• Martingales in Banach spaces
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• Probabilistic Symmetries and Invariance Principles
• Quasi-random graphs
• Quasi-random graphs
• Quasi-random graphs and graph limits
• Quasi-random hypergraphs
• Quasirandomness in hypergraphs
• Ramsey theory for product spaces
• Representations for partially exchangeable arrays of random variables
• Semantic limits of dense combinatorial objects
• Subgraphs of Random Graphs
• Super-reflexive spaces with bases
• Symmetries on random arrays and set-indexed processes
• Szemerédi's regularity lemma revisited
• Szemerédi's regularity lemma via martingales
• The concentration of measure phenomenon
• The poset of hypergraph quasirandomness

Cited in

(2)

• On concentration of high-dimensional matrices with randomly signed entries
• Decompositions of finite high-dimensional random arrays

This page was built for publication: Concentration estimates for functions of finite high‐dimensional random arrays

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