Let $B_i(n,1/2)$ be independent identically distributed binomial random variables. I am interested in the asymptotic growth of the maximum of $n$ such random variables. In https://math.stackexchange.com/questions/590880/bounds-for-the-maximum-of-binomial-random-variables the asymptotics were shown to be bounded above by $\frac{n}{2}+ \sqrt{\frac{n}{2} \log_e n}$ and numerically shown to be bounded below by $\frac{n}{2}+ \sqrt{\frac{n}{2.5} \log_e n}$.
Is it possible to derive the exact asymptotic behaviour for the
maximum of $n$ such independent and identical $B_i(n,1/2)$ binomial random variables?
It seems (very) likely this is a solved problem but I haven't found where or by whom yet. I would be happy with a reference if that is available.
Best Answer
What you need in order to compute the constant is to find the correct $x_n$ so that $$P(B_1(n,1/2)>x_n)\sim \frac{1}{n}$$ In this case it holds (by a precise asymptotics computation, based on normal approximation and the fact that the variance is $n/4$) that, with $\bar x_n=x_n/\sqrt{n}$, $$P(B_1(n,1/2)>x_n)\sim \frac{C}{\bar x_n} e^{-2 \bar x_n^2}$$ So you should choose $$\bar x_n=\sqrt{(\log n)/2}-\frac{\log\log n+C'}{8\sqrt{(\log n)/2}}.$$ With this choice, you will get that $P(\max_{i=1}^n B_i(n,1/2)<x_n)\sim e^{-1}$. This $\log\log n$ correction maybe explains the numerical simulations mentioned in the OP. The fluctuations of the maximum are of order $1/\sqrt{\log n}$.