9
$\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$
2
$\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".

| cite | improve this answer | |
$\endgroup$
2
$\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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hypercontravity url seems badly broken. $\endgroup$ – dohmatob Aug 25 at 11:20
  • $\begingroup$ Good point, I replaced the broken link by a reference $\endgroup$ – Guillaume Aubrun Aug 25 at 13:53
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 ?

| cite | improve this answer | |
$\endgroup$
0
$\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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ As far as I can tell, this paper that paper is targeted at 0/1 random variables (and not Gaussian, the interest of the OP). No ? $\endgroup$ – dohmatob Aug 25 at 11:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.