# Tail bound for maximum of independent (but not identical) binomial random variables

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

• 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 – Fedor Petrov Feb 23 '17 at 5:50
• That was the first step I tried but I'm having trouble getting anywhere productive for successive calculations. – stats134711 Feb 23 '17 at 15:52
• 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$. – usul Mar 9 '17 at 3:23

## 1 Answer

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.

• 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. – stats134711 Mar 8 '17 at 21:44