Skip to main content
added 2 characters in body
Source Link
Lior Eldar
  • 445
  • 2
  • 8

A Gaussian variable $X_i\sim {\cal N}(0,1)$ is anti-concentrated in the following sense: for any $\epsilon>0$ we have: $$ \mathbf{P}( |X_i| \leq \epsilon ) = O(\epsilon). $$ Hence if we consider a polynomial $P(X_1,..., X_n)$ of degree $d$, in $n$ independent Gaussian variables, then it is clear that the best anti-concentration bound we can hope is $$ \mathbf{P}( P(X_1,..., X_n) \leq \epsilon) = O(\epsilon^{1/d}). $$$$ \mathbf{P}( |P(X_1,..., X_n)| \leq \epsilon) = O(\epsilon^{1/d}). $$ This follows immediately when we consider a monomial of the form $X_i^d$ for some Gaussian variable $X_i$, $i\in [n]$. A seminal result by Carbery and Wright shows that this is tight up to a factor of $d$: $$ \mathbf{P}( P(X_1,..., X_n) \leq \epsilon) \leq d \epsilon^{1/d}. $$$$ \mathbf{P}( |P(X_1,..., X_n)| \leq \epsilon) \leq d \epsilon^{1/d}. $$

However, what is known when we assume in addition that $P$ is $\textbf{multi-linear}$ in the variables $X_i$. Is it anti-concentrated more like the degree-1 uni-variate case, or does it behave like the $d$-power monomial case?

A Gaussian variable $X_i\sim {\cal N}(0,1)$ is anti-concentrated in the following sense: for any $\epsilon>0$ we have: $$ \mathbf{P}( |X_i| \leq \epsilon ) = O(\epsilon). $$ Hence if we consider a polynomial $P(X_1,..., X_n)$ of degree $d$, in $n$ independent Gaussian variables, then it is clear that the best anti-concentration bound we can hope is $$ \mathbf{P}( P(X_1,..., X_n) \leq \epsilon) = O(\epsilon^{1/d}). $$ This follows immediately when we consider a monomial of the form $X_i^d$ for some Gaussian variable $X_i$, $i\in [n]$. A seminal result by Carbery and Wright shows that this is tight up to a factor of $d$: $$ \mathbf{P}( P(X_1,..., X_n) \leq \epsilon) \leq d \epsilon^{1/d}. $$

However, what is known when we assume in addition that $P$ is $\textbf{multi-linear}$ in the variables $X_i$. Is it anti-concentrated more like the degree-1 uni-variate case, or does it behave like the $d$-power monomial case?

A Gaussian variable $X_i\sim {\cal N}(0,1)$ is anti-concentrated in the following sense: for any $\epsilon>0$ we have: $$ \mathbf{P}( |X_i| \leq \epsilon ) = O(\epsilon). $$ Hence if we consider a polynomial $P(X_1,..., X_n)$ of degree $d$, in $n$ independent Gaussian variables, then it is clear that the best anti-concentration bound we can hope is $$ \mathbf{P}( |P(X_1,..., X_n)| \leq \epsilon) = O(\epsilon^{1/d}). $$ This follows immediately when we consider a monomial of the form $X_i^d$ for some Gaussian variable $X_i$, $i\in [n]$. A seminal result by Carbery and Wright shows that this is tight up to a factor of $d$: $$ \mathbf{P}( |P(X_1,..., X_n)| \leq \epsilon) \leq d \epsilon^{1/d}. $$

However, what is known when we assume in addition that $P$ is $\textbf{multi-linear}$ in the variables $X_i$. Is it anti-concentrated more like the degree-1 uni-variate case, or does it behave like the $d$-power monomial case?

Source Link
Lior Eldar
  • 445
  • 2
  • 8

anti-concentration of multi-linear polynomials in Gaussian variables

A Gaussian variable $X_i\sim {\cal N}(0,1)$ is anti-concentrated in the following sense: for any $\epsilon>0$ we have: $$ \mathbf{P}( |X_i| \leq \epsilon ) = O(\epsilon). $$ Hence if we consider a polynomial $P(X_1,..., X_n)$ of degree $d$, in $n$ independent Gaussian variables, then it is clear that the best anti-concentration bound we can hope is $$ \mathbf{P}( P(X_1,..., X_n) \leq \epsilon) = O(\epsilon^{1/d}). $$ This follows immediately when we consider a monomial of the form $X_i^d$ for some Gaussian variable $X_i$, $i\in [n]$. A seminal result by Carbery and Wright shows that this is tight up to a factor of $d$: $$ \mathbf{P}( P(X_1,..., X_n) \leq \epsilon) \leq d \epsilon^{1/d}. $$

However, what is known when we assume in addition that $P$ is $\textbf{multi-linear}$ in the variables $X_i$. Is it anti-concentrated more like the degree-1 uni-variate case, or does it behave like the $d$-power monomial case?