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.



Convex combination iid Bernoulli random variables
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](https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem), 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.


