What is the tightest lower and upper bound for the expected maximum value of k IID Binomial(n, p) random variables I tried to derive it : $$Pr[max \leq C] = (\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^k$$ $$E[max] = \sum_{C = 1}^n C(pr[max \leq C] - pr[max \leq C - 1]) = \sum_{C = 1}^n c((\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^k - (\sum_{i = 0}^{C - 1} {n \choose i}p^i(1 - p)^i)^k)$$ $$= n(\sum_{i = 0}^n {n \choose i}p^i(1 - p)^i)^k - \sum_{C = 0}^{n - 1}(\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^k = $$ $$n - \sum_{C = 0}^{n - 1}(\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^k$$

But my brain is not braining and Im not able to get to tight and nice lower and upper bounds for the very general case of expected max of k IID random variables with distribution binomial(n, p), I did an initial search engine search and I could not find anything useful I'd appreciate it if you could let me know of trivial or famous bounds that Im missing here, thank you so much.

  • 1
    $\begingroup$ Are you familiar with the Chernoff/Hoeffding bounds? $\endgroup$ Commented May 19, 2022 at 16:24
  • $\begingroup$ yes Im familiar with them as black boxes (I.e. never derived them on my own just used them in proofs), and I have tried to find lower and upper bounds through those bounds but was wondering if there is any famous result for what to use that gives the best known bounds. Thank you so much $\endgroup$
    – Goli Emami
    Commented May 22, 2022 at 22:09


Your Answer

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