Skip to main content
added 71 characters in body
Source Link
Ron P
  • 947
  • 6
  • 15

I simplify Tao's proof of Proposition 2.

Arrange the $a_i$s is decreasing order, $a_1\geq a_2 \geq \cdots$. Let $C$ be a (large) absolute constant that will be determined later. Let $n_0=\lceil C/p\rceil$. Decompose each $a_i$ as $a_i=b_i+c_i$, where $b_i=\max\{0,a_i-a_{n_0}\}$ and $c_i=\min\{a_{n_0},a_i\}$. Note that the $b_i$s and $c_i$s are non-negative and decreasing.

We must bound away from zero the probability of the event $\{\sum a_i \xi_i \leq p\sum a_i\}\supset \{\sum b_i \xi_i \leq p\sum b_i\}\cap \{\sum c_i \xi_i \leq p\sum c_i\}$. SinceBy FKG Inequality (https://en.wikipedia.org/wiki/FKG_inequality ), the last two events are positively correlated,correlated; therefore it is sufficient to bound each one of them away from zero separately.

For the first event, $\Pr(\sum b_i \xi_i \leq p\sum b_i)\geq \Pr(x_1=\cdots=x_{n_0-1}=0)=(1-p)^{n_0-1}\geq e^{-C}$.

For the second event, we suppose $a_{n_0}>0$ (otherwise the event holds trivially) and normalize so that $a_{n_0}=1$. We apply the Berry-Esseen inequality to obtain $$ \Pr(\sum c_i \xi_i > p\sum c_i)= \frac 1 2 + O\left(\frac{p\sum c_i^3}{(p\sum c_i^2)^{3/2}}\right). $$

Since $c_1=\cdots=c_{n_0}=1$ and $c_i\leq 1$ (for all $i$), we can estimate the right hand-side by $$ \frac{p\sum c_i^3}{(p\sum c_i^2)^{3/2}}\leq p^{-1/2}\frac{\sum c_i^2}{(\sum c_i^2)^{3/2}}\leq (pn_0)^{-1/2}\leq C^{-1/2}. $$ Choosing $C$ large enough concludes the proof.

I simplify Tao's proof of Proposition 2.

Arrange the $a_i$s is decreasing order, $a_1\geq a_2 \geq \cdots$. Let $C$ be a (large) absolute constant that will be determined later. Let $n_0=\lceil C/p\rceil$. Decompose each $a_i$ as $a_i=b_i+c_i$, where $b_i=\max\{0,a_i-a_{n_0}\}$ and $c_i=\min\{a_{n_0},a_i\}$. Note that the $b_i$s and $c_i$s are non-negative and decreasing.

We must bound away from zero the probability of the event $\{\sum a_i \xi_i \leq p\sum a_i\}\supset \{\sum b_i \xi_i \leq p\sum b_i\}\cap \{\sum c_i \xi_i \leq p\sum c_i\}$. Since the last two events are positively correlated, it is sufficient to bound each one of them away from zero separately.

For the first event, $\Pr(\sum b_i \xi_i \leq p\sum b_i)\geq \Pr(x_1=\cdots=x_{n_0-1}=0)=(1-p)^{n_0-1}\geq e^{-C}$.

For the second event, we suppose $a_{n_0}>0$ (otherwise the event holds trivially) and normalize so that $a_{n_0}=1$. We apply the Berry-Esseen inequality to obtain $$ \Pr(\sum c_i \xi_i > p\sum c_i)= \frac 1 2 + O\left(\frac{p\sum c_i^3}{(p\sum c_i^2)^{3/2}}\right). $$

Since $c_1=\cdots=c_{n_0}=1$ and $c_i\leq 1$ (for all $i$), we can estimate the right hand-side by $$ \frac{p\sum c_i^3}{(p\sum c_i^2)^{3/2}}\leq p^{-1/2}\frac{\sum c_i^2}{(\sum c_i^2)^{3/2}}\leq (pn_0)^{-1/2}\leq C^{-1/2}. $$ Choosing $C$ large enough concludes the proof.

I simplify Tao's proof of Proposition 2.

Arrange the $a_i$s is decreasing order, $a_1\geq a_2 \geq \cdots$. Let $C$ be a (large) absolute constant that will be determined later. Let $n_0=\lceil C/p\rceil$. Decompose each $a_i$ as $a_i=b_i+c_i$, where $b_i=\max\{0,a_i-a_{n_0}\}$ and $c_i=\min\{a_{n_0},a_i\}$. Note that the $b_i$s and $c_i$s are non-negative and decreasing.

We must bound away from zero the probability of the event $\{\sum a_i \xi_i \leq p\sum a_i\}\supset \{\sum b_i \xi_i \leq p\sum b_i\}\cap \{\sum c_i \xi_i \leq p\sum c_i\}$. By FKG Inequality (https://en.wikipedia.org/wiki/FKG_inequality ), the last two events are positively correlated; therefore it is sufficient to bound each one of them away from zero separately.

For the first event, $\Pr(\sum b_i \xi_i \leq p\sum b_i)\geq \Pr(x_1=\cdots=x_{n_0-1}=0)=(1-p)^{n_0-1}\geq e^{-C}$.

For the second event, we suppose $a_{n_0}>0$ (otherwise the event holds trivially) and normalize so that $a_{n_0}=1$. We apply the Berry-Esseen inequality to obtain $$ \Pr(\sum c_i \xi_i > p\sum c_i)= \frac 1 2 + O\left(\frac{p\sum c_i^3}{(p\sum c_i^2)^{3/2}}\right). $$

Since $c_1=\cdots=c_{n_0}=1$ and $c_i\leq 1$ (for all $i$), we can estimate the right hand-side by $$ \frac{p\sum c_i^3}{(p\sum c_i^2)^{3/2}}\leq p^{-1/2}\frac{\sum c_i^2}{(\sum c_i^2)^{3/2}}\leq (pn_0)^{-1/2}\leq C^{-1/2}. $$ Choosing $C$ large enough concludes the proof.

Source Link
Ron P
  • 947
  • 6
  • 15

I simplify Tao's proof of Proposition 2.

Arrange the $a_i$s is decreasing order, $a_1\geq a_2 \geq \cdots$. Let $C$ be a (large) absolute constant that will be determined later. Let $n_0=\lceil C/p\rceil$. Decompose each $a_i$ as $a_i=b_i+c_i$, where $b_i=\max\{0,a_i-a_{n_0}\}$ and $c_i=\min\{a_{n_0},a_i\}$. Note that the $b_i$s and $c_i$s are non-negative and decreasing.

We must bound away from zero the probability of the event $\{\sum a_i \xi_i \leq p\sum a_i\}\supset \{\sum b_i \xi_i \leq p\sum b_i\}\cap \{\sum c_i \xi_i \leq p\sum c_i\}$. Since the last two events are positively correlated, it is sufficient to bound each one of them away from zero separately.

For the first event, $\Pr(\sum b_i \xi_i \leq p\sum b_i)\geq \Pr(x_1=\cdots=x_{n_0-1}=0)=(1-p)^{n_0-1}\geq e^{-C}$.

For the second event, we suppose $a_{n_0}>0$ (otherwise the event holds trivially) and normalize so that $a_{n_0}=1$. We apply the Berry-Esseen inequality to obtain $$ \Pr(\sum c_i \xi_i > p\sum c_i)= \frac 1 2 + O\left(\frac{p\sum c_i^3}{(p\sum c_i^2)^{3/2}}\right). $$

Since $c_1=\cdots=c_{n_0}=1$ and $c_i\leq 1$ (for all $i$), we can estimate the right hand-side by $$ \frac{p\sum c_i^3}{(p\sum c_i^2)^{3/2}}\leq p^{-1/2}\frac{\sum c_i^2}{(\sum c_i^2)^{3/2}}\leq (pn_0)^{-1/2}\leq C^{-1/2}. $$ Choosing $C$ large enough concludes the proof.