I recently read an elegant paper of Bobkov

Bobkov, S.G., On concentration of measure on the cube, J. Math. Sci., New York 165, No. 1, 60-70 (2010); translation from Probl. Mat. Anal. 44, 55-64 (2010). ZBL1301.60021.

which gives a concentration inequality in the following form:

Theorem 1.2 (Bobkov). Let f be a function on $[0,1]^n$ symmetric under permutations of coordinates and such that, for all $(x,y)$ in $[0,1]^n$

$$|f(x) - f(y)| < ||x-y||_\infty$$

Then, for all $r > 0$, for some absolute constant $c>0$,

$$P\{|f - Ef| > r\} \leq 2e^{-cnr^2}.$$ where $P$ is the uniform distribution on $[0,1]^n $ and $E$ denotes the expectation under $P$.

1) Is there a similar result for a symmetric function on a product of spheres $(S^k)^n$?

2) How about a symmetric function on a more general product $X^n$? I (naively) suspect that this should still work, perhaps with some modest assumptions on $X$.

Comment 1. The key idea in Bobkov's argument seems to be to use the symmetry to reduce to a function on the simplex $x_1 <= x_2 <= \dots <= x_n$, where concentration properties are known. I imagine there's a technical way to make a very similar sorting argument work for $(S^k)^n$ but I think you'd need a really different proof for $X^n$.

Comment 2. I know a dimension-free concentration inequality on product spaces due to Talagrand, and also McDiarmid's inequality, but I need the stronger result that the concentration gets tighter as $n \rightarrow \infty$ so I don't see how those help.

  • 1
    $\begingroup$ P.S. Thank you for the edits; Bobkov's theorem does indeed assume that the measure on the interval is uniform. $\endgroup$ Commented Aug 23, 2017 at 2:54


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.