Given i.i.d. random variables $X_i$ that are bounded ($C_1 <=X_i <=C_2$ for $C_1>0$), as well as a symmetric function $f(X_1,\cdots,X_N)$ (i.e., invariant with respect to permutations of $X_i$'s). Is there any inequality that is sharper than McDiarmid's inequality, for bounding the probability that $f$ deviates from its mean?

It seems to me that McDiarmid doesn't make use of the symmetry at all, and thus there might be a stronger concentration at the mean than McDiarmid predicts.

A concrete example of such a symmetric function is $f=\frac{N\sum X_i^2}{(\sum X_i)^2}$. Thank you.

  • 1
    $\begingroup$ I think you can use the fact that without loss of generality you can assume $X_1\le X_2\le \dotsc\le X_N$ to refine Hoeffding or McDiarmid. $\endgroup$ – S.B. Oct 30 '16 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.