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_i1\right \geq t \right) \end{align*}

$\begingroup$ 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 ? $\endgroup$– user83457Jul 18, 2016 at 10:26

$\begingroup$ 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$. $\endgroup$– Christian RemlingJul 18, 2016 at 17:09

$\begingroup$ @michael, I am interested in a small constant $t$, which does not scale with $p$ and $n$. $\endgroup$– tourzhaoJul 18, 2016 at 17:51
2 Answers
As commented by Michael, $S:=\sup\limits_{\mathbf{a}\in\Omega}\left\sum_{i}\delta_ia_ip\right$ can be expressed explicitly. Indeed, letting \begin{equation} k:=\sum_{i}\delta_i, \end{equation} 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(nk)}n\Big)$$ $$=0\vee\Big(1\frac{c(nk)}n\Big). $$ So, \begin{equation} S=S_1p\veeS_2p. \end{equation} The probability in question is $1Q$, where \begin{equation} Q:=P(S<pt)=P(S_1p\veeS_2p<pt). \end{equation} 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 6page 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{1p}p$. Then \begin{equation} Q=P\Big((1t)p+c1<\frac{ck}n<(1+t)p\Big). \end{equation} 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 \begin{equation} P\big((1t)np<k<(1+t)np\big), \end{equation} 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 $1Q$.
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{c1}{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 $pk/n\ge pt$, then we simply take $a_j=1/n$ to confirm that the $\sup$ is $\ge t$.
(2) If $pk/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}(nk)=1 . $$ Then $$ 1\frac{ka}{p}=1\frac{1}{p} + \frac{c}{np}(nk) = 1+ \frac{c1}{p}  \frac{ck}{np} > 1+ \frac{c1}{p}  c  ct . $$ I want this to be $\ge t$, and this is condition (1) rewritten, so we're done.

$\begingroup$ The condition $(1t)p+c1\ge(1+t)p$ is equivalent to $t\le\frac{c1}{2p}$. So, it follows from my answer that $Q=0$ and hence the probability $1Q$ in question is $1$ if $0\le t\le1\wedge\frac{1p}p\wedge\frac{c1}{2p}$. The latter condition is less restrictive than the condition $0\le t\le1\wedge\frac{c1}{c+1}(\frac{1}{p}  1)$  given that $c\ge1$. $\endgroup$ Jul 19, 2016 at 1:04

$\begingroup$ @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. $\endgroup$ Jul 19, 2016 at 1:06