Let $X\in\{0,1\}^2$ have mean $\mu=\left[\begin{smallmatrix}p_1\\p_2\end{smallmatrix}\right]$ and $\Pr[X_1 = X_2 = 1] = p\le \min\{p_1,p_2\}$. (Note we must have $1-p_1-p_2+p\ge 0$ for the distribution to be well defined.) We can then compute the covariance matrix $\Sigma = E[(X-\mu)(X-\mu)^T] = \left[\begin{smallmatrix}p_1(1-p_1)&p-p_1p_2\\p-p_1p_2&p_2(1-p_2)\end{smallmatrix}\right]$.

I would like to use the Berry Essen bound, and for that we need to upper bound the quantity $\gamma=E[\|\Sigma^{-1/2}(X-\mu)\|_2^3]$.

I believe one should be able to show $$\gamma \le C\left(\tfrac1{\sqrt{p_1(1-p_1)}}+\tfrac1{\sqrt{p_2(1-p_2)}}+\tfrac1{\sqrt{\min\{p_1,p_2\}-p}}\right) , $$ for some universal constant $C>0$.

The symbolic computation of $\Sigma^{-1/2}$ is a bit unwieldy though, and so I wonder if there is some tricks I may use to arrive at this result more neatly?

Or if not, any proof would be appreciated.

Update: Using Pinelli's observation, we can compute $$\begin{align}\gamma |\Sigma|^{3/2} &= p[(1-p_1)(1-p_2)v]^{3/2} \\&+ (p_1-p)[(1-p_1)p_2(1-v)]^{3/2} \\&+ (p_2-p)[p_1(1-p_2)(1-v)]^{3/2} \\&+ (1-p_1-p_2+p)[p_1 p_2 v]^{3/2} , \end{align}$$ where $v = p_1+p_2-2p$ and $|\Sigma|=p_1p_2(1-v)-p^2$.

It seems like I forgot a factor $1/\sqrt{p}$. In fact it seems that bounds of $\gamma \le \frac{2} {\sqrt{p\,(\min\{p_1,p_2\}-p)}} $ or $\gamma \le \frac{1} {\sqrt{p}}+ \frac{2} {\sqrt{\min\{p_1,p_2\}-p}} $ are sufficient and correct.

| cite | improve this question | | | | |

Your inequality does not hold in general:

You don't need to compute to compute $\Sigma^{-1/2}$, because $\|\Sigma^{-1/2} x\|_2^2=x^T\Sigma^{-1}x$ for all $x\in\mathbb R^2$. Using this simple observation with e.g. $p=0$, $p_1=1/2$, $p_2=1/2-\epsilon$, and $\epsilon\downarrow0$, we find $$\gamma =\frac{\left(1-\epsilon -\epsilon ^2\right)^{3/2}}{\sqrt{\epsilon }}+\frac{1}{2} (1+\epsilon )^{3/2}+\frac{\left(1-\epsilon +2 \epsilon ^2\right)^{3/2}}{2 \sqrt{1-2 \epsilon }}\to\infty,$$ whereas $$\frac1{\sqrt{p_1(1-p_1)}}+\frac1{\sqrt{p_2(1-p_2)}}+\frac1{\sqrt{\min(p_1,p_2)-p}}\to4+\sqrt2.$$

| cite | improve this answer | | | | |
  • $\begingroup$ Good point, and good approach. It looks like the term I need is $\frac{1}{\sqrt{(p_1+p_2-2p)(1-p_1-p_2+2p)}}$ rather than $\frac{1}{\sqrt{\min\{p_1,p_2\}-p}}$. What do you think about that version? $\endgroup$ – Thomas Dybdahl Ahle Apr 19 at 10:34
  • $\begingroup$ @ThomasDybdahlAhle : I think the new version requires a rather different approach. Therefore and because your current question has been answered, the new version should be posted as a separate question. $\endgroup$ – Iosif Pinelis Apr 19 at 13:40
  • $\begingroup$ My conjecture was disproved, and you did point in a good direction, but I still don't have a useful upper bound, which was the main point of the question. Do you have a suggestion for how to state the new question without too much overlap with this one? $\endgroup$ – Thomas Dybdahl Ahle Apr 19 at 19:07
  • $\begingroup$ @ThomasDybdahlAhle : Your original question was fully answered. Therefore, I think any additional questions you may have should be posted separately. $\endgroup$ – Iosif Pinelis Apr 21 at 16:50

We have the simplex $0\le p, 0\le p_1-p, 0\le p_2-p, 0\le 1-p_1-p_2+p$. From this, we can deduce $v\in[0,1]$ and so we may bound

$$\begin{align} \gamma |\Sigma|^{3/2} &= p[(1-p_1)(1-p_2)v]^{3/2} \\&\quad+ (p_1-p)[(1-p_1)p_2(1-v)]^{3/2} \\&\quad+ (p_2-p)[p_1(1-p_2)(1-v)]^{3/2} \\&\quad+ (1-p_1-p_2+p)[p_1 p_2 v]^{3/2} \\&\le p[(1-p_1)(1-p_2)v] \\&\quad+ (p_1-p)[(1-p_1)p_2(1-v)] \\&\quad+ (p_2-p)[p_1(1-p_2)(1-v)] \\&\quad+ (1-p_1-p_2+p)[p_1 p_2 v] \\&=2|\Sigma| . \end{align}$$ In other words $\gamma\le2|\Sigma|^{-1/2}$.

This bound is tight except at the four 0-faces/corners of the simplex.

In particular, the determinant is 0 exactly in the 1-faces of the simplex (see the picture), and $|\Sigma|^{-1/2}$ approaches those as $1/\sqrt\epsilon$, which $\gamma$ does too.

The bound still isn't quite tight though, as it approaches the 0-faces/corners as $1/\epsilon$, while $\gamma$ approaches them as $1/\sqrt\epsilon$. (E.g. if we let $p=\epsilon, p_1=2\epsilon, p_2=3\epsilon$.)

enter image description here

| cite | improve this answer | | | | |

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.