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*}

  • $\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$ – user83457 Jul 18 '16 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 Remling Jul 18 '16 at 17:09
  • $\begingroup$ @michael, I am interested in a small constant $t$, which does not scale with $p$ and $n$. $\endgroup$ – 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 \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(n-k)}n\Big)$$ $$=0\vee\Big(1-\frac{c(n-k)}n\Big). $$ So, \begin{equation} S=|S_1-p|\vee|S_2-p|. \end{equation} The probability in question is $1-Q$, where \begin{equation} Q:=P(S<pt)=P(|S_1-p|\vee|S_2-p|<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 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 \begin{equation} Q=P\Big((1-t)p+c-1<\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((1-t)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 $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.

  • $\begingroup$ 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$. $\endgroup$ – Iosif Pinelis Jul 19 '16 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$ – Christian Remling Jul 19 '16 at 1:06

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.