Let $B_i(n,1/2)$ be independent identically distributed binomial random variables. How can one derive lower and upper bounds for the expected value of the maximum of $n$ such random variables? I am especially interested in bounds for large $n$.
In a related question, Expectation of the maximum of gaussian random variables gives an upper bound for the maximum of $n$ gaussian i.i.d $\mathcal{N}(0,\sigma^2)$ random variables of
$$\mathbb{E}[Z] \leq \sigma \sqrt{ 2 \log n} .$$
Is it possible to translate this to my particular problem and can one get a lower bound too?
Best Answer
Yes it is possible to translate this bound to your particular problem:
The expected value of your binomial random variables is $\mu=\frac{n}{2}$ not $0$, and their standard deviation is $\sigma=\sqrt{\frac{n}{4}}$ so the corresponding upper bound for the maximum is $$ \mathbb{E}[Z] \leq \frac{n}{2}+ \sqrt{\frac{n}{2} \log_e n} .$$ This uses the Gaussian approximation to the binomial, which happens faster than the upper bound being approached.
You cannot get rid of the $\sqrt{\log n}$ term. As an illustration of how good this bound is, if $n=10^6$ then the upper bound would suggest about $502628.3$. In fact the expectation of the maximum value is about $502431.4$ which is about $\frac{n}{2}+ \sqrt{\frac{n}{2.337} \log_e n} $.