12
$\begingroup$

I'm looking for a lower bound for the probability that an arbitrary convex combination of iid Bernoulli (p) random variables is at least p. My guess is p/k (for some constant k; k must be at least e, as noted by Matt below), but I'm happy with any positive lower bound that depends only on p.

For example, if p is slightly above 1/2, and the convex combination is simply the average of two variables, then the probability is slightly above 1/4 which is approximately p/2.

$\endgroup$
2
  • $\begingroup$ If p=0.7, the average of three variables exceeds p with probability only 0.343, which is < 0.7/2. $\endgroup$
    – user44143
    Aug 7, 2017 at 1:43
  • $\begingroup$ If p=exp(-1/n), then the average of n variables exceeds p with probability only 1/e. So if p/k is a lower bound, then k>=e. $\endgroup$
    – user44143
    Aug 7, 2017 at 2:17

4 Answers 4

5
$\begingroup$

To complement my other answer, I will show

Proposition 1 Let $\xi_k$ be a finite number of iid Bernoulli random variables of expectation $p > 1/2$, and let $a_k > 0$ be real numbers. Then ${\bf P}( \sum_k a_k \xi_k \geq p \sum_k a_k) \gg 1$.

By replacing $\xi_k$ with $1-\xi_k$ and $p$ with $1-p$, this is equivalent to

Proposition 2 Let $\xi_k$ be a finite number of iid Bernoulli random variables of expectation $p < 1/2$, and let $a_k > 0$ be real numbers. Then ${\bf P}( \sum_k a_k \xi_k \leq p \sum_k a_k) \gg 1$.

Let's prove Proposition 2. I found a number of arguments to treat various special cases, which when combined together was able to cover the general case as follows.

We will need a large absolute constant $C_0$.

Case 1: (high multiplicity) For every integer $n$, the number of $a_k$ in the dyadic interval $(2^{n-1}, 2^n]$ is either zero, or at least $C_0/p$.

Roughly speaking this is the regime where the central limit theorem applies. In this case we can proceed by the Berry-Esseen inequality, which lets one estimate $$ {\bf P}( \sum_k a_k \xi_k \geq p \sum_k a_k) = \frac{1}{2} + O( \frac{p \sum_k a_k^3}{(p \sum_k a_k^2)^{3/2}} ).$$ If, for each $n$, we let $c_n$ be the number of $k$ for which $a_k \in (2^{n-1},2^n]$, we can write the right-hand side as $$ \frac{1}{2} + O( p^{-1/2} \frac{\sum_n 2^{3n} c_n}{(\sum_n 2^{2n} c_n)^{3/2}} ).$$ By hypothesis, each $c_n$ is either zero or at least $C_0/p$, so we can bound $$ 2^{3n} c_n \leq (C_0/p)^{-1/2} 2^{2n} c_n (\sum_{n'} 2^{2n'} c_{n'})^{1/2} $$ so the previous expression becomes $\frac{1}{2} + O( C_0^{-1/2} )$, and the claim follows for $C_0$ large enough.

Case 2: (low multiplicity) For every integer $n$, the number of $a_k$ in the dyadic interval $(2^{n-1}, 2^n]$ is at most $C_0/p$.

Here the Bernoulli variables are mostly zero and one can proceed using the first and second moment methods, after first applying a dyadic decomposition.

Let $n_0$ be the integer such that $p \sum_k a_k \in (2^{n_0-1}, 2^{n_0}]$. It will suffice to show that $$ {\bf P}( \sum_k a_k \xi_k \leq 2^{n_0-1} ) \gg_{C_0} 1.$$

The number of $k$ with $a_k > 2^{n_0-C_0}$ is at most $2^{C_0} / p$, and hence $$ {\bf P}( \sum_{k: a_k > 2^{n_0-C_0}} a_k \xi_k = 0 ) \geq (1-p)^{2^{C_0}/p} \gg_{C_0} 1.\qquad(1)$$ Next, for any $m \geq C_0$, we consider the random variable $$ \sum_{k: 2^{n_0-m-1} < a_k \leq 2^{n_0-m}} a_k \xi_k.$$ There are at most $C_0/p$ elements in this sum, so the second moment of this variable can be computed as $$ {\bf E} ( \sum_{k: 2^{n_0-m-1} < a_k \leq 2^{n_0-m}} a_k \xi_k )^2 \ll C_0^2 2^{2n_0-2m}.$$ By Markov's inequality we thus have $$ {\bf P} ( \sum_{k: 2^{n_0-m-1} < a_k \leq 2^{n_0-m}} a_k \xi_k \geq 2^{n_0-m/2} ) \ll C_0^2 2^{-m}.\qquad(2)$$

Applying the union bound to (2) for all $m \geq C_0$ and combining with (1) (using independence), we obtain the claim (if $C_0$ is large enough).

Case 3: (general case)

In this case we can partition the $k$ into two classes ${\mathcal K}_1$, ${\mathcal K}_2$, one of which is in the low multiplicity case and one of which is in the high multiplicity case. By the preceding cases we have

$${\bf P}( \sum_{k \in {\mathcal K}_1} a_k \xi_k \leq p \sum_{k \in {\mathcal K}_1} a_k) \gg 1$$ and $${\bf P}( \sum_{k \in {\mathcal K}_2} a_k \xi_k \leq p \sum_{k \in {\mathcal K}_2} a_k) \gg_{C_0} 1$$ so by independence we conclude $${\bf P}( \sum_k a_k \xi_k \leq p \sum_k a_k) \gg_{C_0} 1$$ as required.

$\endgroup$
1
  • 1
    $\begingroup$ I simplified the proof of Proposition 2. See answer below. $\endgroup$
    – Ron P
    Aug 19, 2017 at 8:52
10
$\begingroup$

One can get a bound which is within a constant of the optimal bound using the following

Paley-Zygmund type inequality Let $X$ be a real random variable with mean zero and finite fourth moment, that is not identically zero. Then $$ {\bf P}(X > 0) \geq \frac{({\bf E} X^2)^2}{4 {\bf E} X^4}.$$

Proof
By Holder we have $$ {\bf E} X^2 1_{X>0} \leq ({\bf E} X^4)^{1/2} {\bf P}(X>0)^{1/2} \quad (1)$$ and $$ {\bf E} X 1_{X>0} \leq ({\bf E} X^4)^{1/4} {\bf P}(X>0)^{3/4}$$ and hence by the mean zero hypothesis $$ {\bf E} |X| 1_{X<0} \leq ({\bf E} X^4)^{1/4} {\bf P}(X>0)^{3/4}.$$ Hence by Holder again $$ {\bf E} X^2 1_{X<0} \leq ({\bf E} |X| 1_{X<0})^{2/3} ({\bf E} |X|^4)^{1/3} \leq ({\bf E} X^4)^{1/2} {\bf P}(X>0)^{1/2} $$ which on summing with (1) gives $$ {\bf E} X^2 \leq 2 ({\bf E} X^4)^{1/2} {\bf P}(X>0)^{1/2}$$ hence the claim. $\Box$

(It should be possible to improve the constant $4$ a bit by using the fact that the fourth moment has to be shared between the positive and negative components of $X$, but I have not tried to optimise this. The extremal relationship between ${\bf P}(X>0)$, ${\bf E} X^2$, and ${\bf E} X^4$ is probably coming from the case $X = \xi - p$ of a normalised Bernoulli random variable $\xi$. One can also obtain a comparable bound by applying the usual Paley-Zygmund inequality to $(X - \sqrt{\theta {\bf E} X^2})^2$ for some parameter $0 < \theta < 1$ that one can optimise in.)

In your situation, writing $X = \sum_i a_i (\xi_i - p)$ for the normalised sum of Bernoulli variables $\xi_i$, $X$ has mean zero, variance $p(1-p) \sum_i a_i^2$, and fourth moment $$ 6 \sum_{i<j} a_i^2 a_j^2 (p(1-p))^2 + \sum_i a_i^4 (p (1-p)^4 + (1-p) p^4)$$ $$ \leq \max( 3(p(1-p))^2, p (1-p)^4 + (1-p) p^4) \sum_{i,j} a_i^2 a_j^2$$ $$ = \max( 3p^2 (1-p)^2, p(1-p)(1-3p+3p^2)) (\sum_i a_i^2)^2$$ and hence $$ {\bf P}(X>0) \geq \frac{1}{4 \max( 3, (1-3p+3p^2)/p(1-p) )}$$ which is asymptotic to $p/4$ as $p \to 0$, or $(1-p)/4$ as $p \to 1$. One should be able to improve the constant $4$ with a bit more effort.

$\endgroup$
3
  • $\begingroup$ Thanks a lot! That was the missing bit in our Economics paper on the uniform rate of assimilation of new inovations in complex markets. $\endgroup$
    – Ron P
    Aug 7, 2017 at 18:45
  • $\begingroup$ I couldn't figure out why this bound is within a constant of the optimal bound. I can see it when p is bounded away from 1, but not when p is close to 1. $\endgroup$
    – Ron P
    Aug 10, 2017 at 11:39
  • $\begingroup$ Fair point, the bound is not sharp when p is close to 1. This requires a rather different argument, which I will post separately. $\endgroup$
    – Terry Tao
    Aug 11, 2017 at 2:49
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Nice use of the FKG inequality! $\endgroup$
    – Terry Tao
    Aug 21, 2017 at 15:53
  • $\begingroup$ Thanks! I learned a lot from your answers and comment. Amended the answer by including a reference to FKG inequality. $\endgroup$
    – Ron P
    Aug 22, 2017 at 12:10
0
$\begingroup$

Maybe this will be also handy - there is an optimal result by Liggett (using the Erdos-Ko-Rado theorem):

https://books.google.lt/books?id=psqFNlngZDcC&pg=PA50&lpg=PA50&dq=liggett+bernoulli+erdos+ko+rado&source=bl&ots=mmYEzFbSUl&sig=ACfU3U290899jh4r7ejZoFm8BIqFQpcfFQ&hl=en&sa=X&ved=2ahUKEwisvJP4jbjlAhUl_SoKHcH1BXwQ6AEwAnoECAoQAQ#v=onepage&q=liggett%20bernoulli%20erdos%20ko%20rado&f=false

$\endgroup$
10
  • $\begingroup$ Can you elaborate, TOM? $\endgroup$
    – Ron P
    Oct 27, 2019 at 11:33
  • $\begingroup$ Ligett proved that for independent Bernoulli random variables $X_1, X_2, \ldots, X_n$ with parameter p. Let S be a convex combination of these variables. Then $$\mathbb{P}(S\geq 1/2) \geq p.$$ $\endgroup$
    – TOM
    Oct 28, 2019 at 14:02
  • $\begingroup$ The latter bound is sharp as equality is achieved by taking just one such random variable. $\endgroup$
    – TOM
    Oct 28, 2019 at 14:02
  • $\begingroup$ I forgot to add that this is true only for $p\geq \frac{1}{2}$. $\endgroup$
    – TOM
    Oct 29, 2019 at 2:17
  • $\begingroup$ since links are not permanent can you please write out your answer explicitly? $\endgroup$
    – kodlu
    Oct 29, 2019 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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