0
$\begingroup$

This post derived the tail bound for the maximum of independent and identically distributed binomial r.v.'s based on normal approximation. Is there a similar result in the literature for finding the bounding constant (in the post, it is $x_n$) for the case where the binomial r.v.'s may not be identically distributed?

Mathematically, let $X_i\stackrel{indep}{\sim} Bin(n,p_i)$, $1\leq i\leq m$.

Is it possible to find a $c_{m,n}$, such that $P(\max_{1\leq i\leq m} X_i > c_{m,n})\to 0$ as $m,n\to\infty$, also assuming that $m=\mathcal{O}(n^r)$ for some $r>1$?

The condition at the end lets $m$ get larger at a rate faster than $n$. My gut also tells me that $c_{m,n}$ will depend on some function of the $p_i$'s (in addition to $m$ and $n$).

$\endgroup$
3
  • $\begingroup$ Of course it depends on $p_i$, if all $p_i$ are almost 0, this probability is small. We have $P(\max_{1\leq i\leq m} X_i > c)=1-\prod_{1\leq i\leq m}P(X_i\leq c)$, this should be useful for formulating concrete results $\endgroup$ Feb 23, 2017 at 5:50
  • $\begingroup$ That was the first step I tried but I'm having trouble getting anywhere productive for successive calculations. $\endgroup$ Feb 23, 2017 at 15:52
  • $\begingroup$ Continuing Fedor's line of reasoning, we can use Chernoff-type bounds to obtain $P(X_i \leq c) \leq e^{-f(c,p_i,n)}$, so the probability is at least $1 - \exp\left[ - \sum_{i=1}^m f(c,p_i,n) \right]$. For example, I think Hoeffding's gives $f(c,p_i,n) = 2(c - np_i)^2/n$. $\endgroup$
    – usul
    Mar 9, 2017 at 3:23

1 Answer 1

1
$\begingroup$

You can derive some conditions applying the Bernstein's trick. For any positive $t$, we have

$$ P\left( \max_{i\le m}X_i > c_{n,m}\right) = P\left( \exp\{t\max_{i\le m}X_i\} > e^{t c_{n,m}}\right) \le e^{-t c_{n,m}}E\left[ \max_{i\le m} e^{tX_i}\right] $$ Since $X_i$ follows a binomial distribution $$ E\left[ e^{tX_i}\right] = (1-p_i +p_ie^{t})^n \le \exp\{ p_i(e^t-1)n\}. $$ Bounding the maximum by the sum and denoting by $p_m$ the largest $p_i$, we have $$ P\left( \max_{i\le m}X_i > c_{n,m}\right) \le m\exp\{ p_m(e^t-1)n -tc_{n,m}\}. $$ Now, you can minimize on $t$ the right-hand side of the above inequality and finally impose some conditions over $\max_i p_i$, $m$ and $n$. This method is very useful when you know the distribution's MGF and have independence.

A wonderful and useful reference for concentration Inequalities and tail bounds like these is the book:

Concentration Inequalities: A Nonasymptotic Theory of Independence. S. Boucheron, G. Lugosi and P. Massart.

https://books.google.com.br/books/about/Concentration_Inequalities.html?id=ZG6OjgEACAAJ&redir_esc=y&hl=en

Hope it helps.

$\endgroup$
1
  • $\begingroup$ Thank you! I derived a weaker bound based on Hoeffding, assuming $\max_i p_i=1/2$ (specific to my problem). This is also great and I very much appreciate the reference. $\endgroup$ Mar 8, 2017 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.