Bounds for the maximum of binomial random variables

Solution 1:

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

Solution 2:

I was interested to see the accuracy of the upper bound proposed by Henry's neat solution. The following diagram illustrates:

• Red curve: Henry's upper bound of $\frac{n}{2}+ \sqrt{\frac{n}{2} \log_e n}$
• The blue dots: the actual exact expectation of the sample maximum, as $n$ increases from 1 to 200.

To my surprise, the upper bound appears to get worse (in an absolute sense) as $n$ gets larger ... not better.