Concentration inequalities for sub-additive functions using the entropy method (Q4445180)

A function \(f\) of \(n\) variables is sub-additive if there exists a sequence of functions \(f_k\) of \(n-1\) variables such that for all \(x_1,\dots,x_n,\) \[ \sum^n_{k=1}f(x_1,\dots,x_n)-f_k(x_1,\dots,x_{k-1},x_{k+1},\dots,x_n)\leq f(x_1,\dots,x_n). \] A function of \(n\) independent random variables \(X_1,\dots,X_n\) is sub-additive if \(Z=f(X_1,\dots,X_n)\) is \(\sigma(X_1,\dots,X_n)\)-measurable, \(Z_k=f_k(X_1,\dots,X_{k-1},X_{k+1},\dots,X_n)\) is \(\sigma(X_1,\dots, X_{k-1},X_{k+1},\) \(\dots,X_n)\)-measurable for all \(k=1,2,\dots,n\) and the above inequality is satisfied almost surely. The difference \(Z-Z_k\) is called the increment of \(Z.\) Exponential concentration inequalities are obtained for sub-additive functions of independent random variables under weak conditions in the increments of these functions, like the existence of exponential moments for these increments. As a consequence of these general inequalities a refinement of Talagrand's inequality for empirical processes and new bounds for randomized processes associated to unbounded random variables are given. These results are obtained by further developing the entropy method introduced by Ledoux. For the entire collection see [Zbl 1024.00031].