11
$\begingroup$

I have a set of random variables $X_1,\ldots,X_n$, all Gaussian with mean 0 and variance 1, indepedent. Let $p(x_1,\ldots,x_n)$ be some polynomial that takes products and sums of $x_1,\ldots,x_n$.

What can be said about the concentration of measure of $p(X_1,\ldots,X_n)$ around $E[p(X_1,\ldots,X_n)]$?

If there were only two-order interactions, I think I would look around for concentration of measure for chi-squared random variables, but unfortunately the interaction can be of a higher degree.

$\endgroup$

4 Answers 4

4
$\begingroup$

Hypercontractivity implies that for a polynomial $P$ of total degree $d$ in Gaussian variables and $q \geq 2$, we have $$ \|P\|_{L^q} \leq (q-1)^{d/2} \|P\|_{L^2} .$$ Applying Markov inequality for the optimal $q$ yields then for $t \geq C_d$ $$ \mathrm{Prob} \left(|P- \mathbf{E} P| \geq t \sqrt{\mathrm{Var}(P)} \right) \leq \exp(-c_d t^{2/d} ) $$ for some constants $C_d,c_d$.

Reference: Corollary 5.49 in Aubrun-Szarek, Alice and Bob meet Banach

$\endgroup$
1
  • $\begingroup$ Good point, I replaced the broken link by a reference $\endgroup$ Commented Aug 25, 2020 at 13:53
3
$\begingroup$

From the abstract of the paper Schudy and Sviridenko: "In this work we design a general method for proving moment inequalities for polynomials of independent random variables. Our method works for a wide range of random variables including Gaussian, Boolean, exponential, Poisson and many others. We apply our method to derive general concentration inequalities for polynomials of independent random variables. [...] We show that our concentration inequality is stronger than the well-known concentration inequality due to Kim and Vu".

$\endgroup$
1
$\begingroup$

If the polynomial is of low degree, try the Kim-Vu method: http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/papers/polycon.pdf

$\endgroup$
0
1
$\begingroup$

Your problem seems hard at a glance, because there are a lot of elements, but is it actually ?

You have a polynomial of Gaussian variables. You can explicitly compute the variance of that quantity (the formula for the variance is going to be hideous but you can), and then, just use Chebyshev's inequality and you have a nice concentration inequality

Would that not be powerful enough for whatever you need to do ?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .