A Bernstein type inequality for sums of selections from three dimensional arrays

Debapratim Banerjee; Matteo Sordello

doi:10.1016/j.spl.2019.06.010

paper

A Bernstein type inequality for sums of selections from three dimensional arrays

arXiv:1907.08729 · doi:10.1016/j.spl.2019.06.010

Abstract

We consider the three dimensional array $A = {a_{i, j, k}}_{1 \leq i, j, k \leq n}$ , with $a_{i, j, k} \in [0, 1]$ , and the two random statistics $T_{1} := \sum_{i = 1}^{n} \sum_{j = 1}^{n} a_{i, j, σ (i)}$ and $T_{2} := \sum_{i = 1}^{n} a_{i, σ (i), π (i)}$ , where $σ$ and $π$ are chosen independently from the set of permutations of ${1, 2, \dots, n} .$ These can be viewed as natural three dimensional generalizations of the statistic $T_{3} = \sum_{i = 1}^{n} a_{i, σ (i)}$ , considered by Hoeffding \cite{Hoe51}. Here we give Bernstein type concentration inequalities for $T_{1}$ and $T_{2}$ by extending the argument for concentration of $T_{3}$ by Chatterjee \cite{Cha05}.