7
$\begingroup$

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

$\endgroup$
3
  • $\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, 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$ Jul 18, 2016 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, 2016 at 17:51

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\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$ 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy