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

Improve this question
$\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$
    – Fedor Petrov
    Commented 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$
    – stats134711
    Commented 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
    Commented Mar 9, 2017 at 3:23

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – stats134711
    Commented Mar 8, 2017 at 21:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .