Let $X = \{X_1, ..., X_k\}$ be a set of $k$ iid variables drawn from a binomial distribution: $X_i \sim B(n, p)$. How to calculate the upper bound of the expected value of $max(X_i)$?

Several related question (such as: Bounds for the maximum of binomial random variables or Maximum of Binomial Random Variables) give such estimates for cases when $n = k$. I am, however, interested in the general case.

  • 1
    $\begingroup$ Careful - interesting and difficult questions posed by new users on this site are usually CLOSED down with facile remarks like: "What have you tried?" Then, they go off and answer homework questions ... ? $\endgroup$ – wolfies Jul 19 '17 at 17:08

$\newcommand\P{\mathbb{P}}\newcommand\E{\mathbb{E}}\newcommand\ol{\overline}$Write $\ol X_{\max} = \max\{\ol X_i\} = \max\{\tfrac{1}{n} X_i\}$. We can compute $$ \P(\ol X_{\max} > p + t) = \P(\ol X_i > p + t \text{ for some } i=1,\ldots,k) \leq k\P(\ol X_1 > p + t) \leq k\,e^{-2nt^2} $$ by the union bound and Hoeffding's inequality. Denoting $(x)_+ = \max\{x,0\}$, this implies $$ \E \ol X_{\max} \leq p + \E(\ol X_{\max} - p)_+ = p + \int_0^\infty \P(X_{\max} > p + t)dt \leq p + k\sqrt{\frac{\pi}{8n}} $$ In terms of the original variables $X_{\max} = n\ol X_{\max}$, we have $$ \E X_{\max} \leq np + k\sqrt{\frac{n\pi}{8}} \leq np + \tfrac{2}{3}k\sqrt{n}. $$ Note that this is much weaker in terms of $k$ than the asymptotically correct bound $$ \E X_{\max} \asymp np + \sqrt{2p(1-p)} \sqrt{n\log k} $$ based on a normal approximation and the fact that if $Z_i\sim\mathcal{N}(0,1)$, $\E Z_{\max} \asymp \sqrt{2\log k}$, but it does give the right dependence on $n$.

  • $\begingroup$ how did you come up with the "asymptotically correct bound" $\endgroup$ – Rohit Pandey Feb 5 at 22:54

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.