# Uniform Concentration Bounds on Weighted Sum of i.i.d. Bernoulli Random Variables

Let $\delta_1,...,\delta_n$ be $n$ independent identically distributed Bernoulli random variables with $\mathbb{P}(\delta_1=1)=p$. We consider a set $\Omega = \{\mathbf{a}:=(a_1,...,a_n)~|~a_i\in [0,c/n],~\sum_{i}a_i=1\}$, where $c$ is a generic constant. What is the best upper bound for the following probability? \begin{align*} \mathbb{P}\left(\sup_{\mathbf{a}\in\Omega}\left|\frac{1}{p}\sum_{i}\delta_ia_i-1\right| \geq t \right) \end{align*}

• I think you can do the sup more or less explicitly, but when I do it I don't get an idea of the range of t in which you are interested. What is it ? – user83457 Jul 18 '16 at 10:26
• I think this probability is just equal to $1$, under mild extra assumptions on $p,c,n$. For a typical outcome, with roughly the expected number of $\delta_j$'s equal to $1$, we could take those $a_j=0$ or something of this sort. For an atypical outcome, we don't need to do much of anything, we can just take $a_j=1/n$, and again the sum won't be close to $1$. – Christian Remling Jul 18 '16 at 17:09
• @michael, I am interested in a small constant $t$, which does not scale with $p$ and $n$. – tourzhao Jul 18 '16 at 17:51

As commented by Michael, $S:=\sup\limits_{\mathbf{a}\in\Omega}\left|\sum_{i}\delta_ia_i-p\right|$ can be expressed explicitly. Indeed, letting $$k:=\sum_{i}\delta_i,$$ one has $$S_1:=\max\limits_{\mathbf{a}\in\Omega}\sum_{i}\delta_ia_i=1\wedge\frac{ck}n$$ and $$S_2:=\min\limits_{\mathbf{a}\in\Omega}\sum_{i}\delta_ia_i=1-\max\limits_{\mathbf{a}\in\Omega}\sum_{i}(1-\delta_i)a_i= 1-\Big(1\wedge\frac{c(n-k)}n\Big)$$ $$=0\vee\Big(1-\frac{c(n-k)}n\Big).$$ So, $$S=|S_1-p|\vee|S_2-p|.$$ The probability in question is $1-Q$, where $$Q:=P(S<pt)=P(|S_1-p|\vee|S_2-p|<pt).$$ The exact expression for this probability is very complicated, depending on a large number of cases involving the variables $c, p, n, t$; see the 6-page expression in https://www.dropbox.com/s/2jhj2pi3v8o1d2b/Mathematica.pdf?dl=0 . Note that for $\Omega\ne\emptyset$, it is necessary that $c\ge1$.

Since you said that $t$ is "small", let us assume, for instance, that $0\le t\le1\wedge\frac{1-p}p$. Then $$Q=P\Big((1-t)p+c-1<\frac{ck}n<(1+t)p\Big).$$ In particular, if $c$ is close to $1$ (so that all $a_i$'s are close to $\frac1n$), then this expression for $Q$ is close to $$P\big((1-t)np<k<(1+t)np\big),$$ the probability that $k=\sum_{i}\delta_i$ (which has the binomial distribution with parameters $n$ and $p$) takes a value in an interval symmetric about the expected value of $k$. Now you can use any of the known bounds on the tail probabilities for the binomial distribution to bound $1-Q$.

This is an expanded version of my comment above. The probability equals $1$ if we make the mild extra assumption that $t\le 1$ and $$t\le \frac{c-1}{c+1}\left(\frac{1}{p} - 1\right) \quad\quad\quad\quad (1)$$ (you wrote you wanted small $t$).

First of all, by the symmetry of the maximization, to find the sup, it suffices to discuss the case where $\delta_j=1$ for $j=1,2,\ldots , k$, and $\delta_j=0$ otherwise, for some $k$. So we're maximizing $$\left| \frac{1}{p} \sum_{j=1}^k a_j - 1 \right| .$$ There are two cases: (1) If $|p-k/n|\ge pt$, then we simply take $a_j=1/n$ to confirm that the $\sup$ is $\ge t$.

(2) If $|p-k/n|< pt$, then I really want to take $a_j=0$ for $j\le k$. I can't always do this because I also must keep the sum equal to $1$, but if it is admissible, then obviously the sup is $\ge 1\ge t$.

If $a_j=0$ for $j\le k$ is not possible, then I do the next best thing: I'll take $a_j=a$ for $j\le k$, with $a>0$ minimal. In other words, $$ka + \frac{c}{n}(n-k)=1 .$$ Then $$1-\frac{ka}{p}=1-\frac{1}{p} + \frac{c}{np}(n-k) = 1+ \frac{c-1}{p} - \frac{ck}{np} > 1+ \frac{c-1}{p} - c - ct .$$ I want this to be $\ge t$, and this is condition (1) rewritten, so we're done.

• The condition $(1-t)p+c-1\ge(1+t)p$ is equivalent to $t\le\frac{c-1}{2p}$. So, it follows from my answer that $Q=0$ and hence the probability $1-Q$ in question is $1$ if $0\le t\le1\wedge\frac{1-p}p\wedge\frac{c-1}{2p}$. The latter condition is less restrictive than the condition $0\le t\le1\wedge\frac{c-1}{c+1}(\frac{1}{p} - 1)$ -- given that $c\ge1$. – Iosif Pinelis Jul 19 '16 at 1:04
• @IosifPinelis: Yes, it's obvious from my argument that I'm not attempting to find optimal conditions, I'm just making the general point that the prob is $1$ essentially always. – Christian Remling Jul 19 '16 at 1:06