Asymptotics of the maximum of binomial random variables

Question

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.

Answer 1

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

Answer 2

I don't know where this is given in detail, but the method is the same as that used to obtain the distribution of the maximum degree of a random graph with $p=1/2$. In this range, the fact that the degrees of a random graph are not independent has negligible consequences and the only thing that needs adjusting is that the degree of each vertex has distribution $B(n-1,1/2)$ rather than $B(n,1/2)$. (Probably that just moves the moves the distribution of the maximum by $1/2$.)

A place where the calculation is done in detail for random graphs is the book Random Graphs by Béla Bollobás. Basically it is along the lines of Ofer's answer. Once you identify the position of the interesting part of the distribution (see Ofer), choose some $x$ near there. Then use an approximation of the binomial distribution to obtain $P(\forall i~B_i(n,1/2)\le x) = P(B_1(n,1/2)\le x)^n$. If you keep enough terms you can subtract the value for $x$ from the value for $x+1$ to get the probability that the maximum is exactly $x$.