Imagine you have $k$ random variables $X_1,…,X_k$ drawn i.i.d. from a binomial distribution $B(n,1/2)$. For any $\epsilon > 0$, the probability that the maximum of these $k$ draws is above $(1-\epsilon) n$
$$
\Pr[\max_i X_i > (1-\epsilon) n] = 1- \Pr[X_k \leq (1-\epsilon) n]^k = 1 -\left( \sum_{i=0}^{\lfloor (1-\epsilon) n) \rfloor} \binom{n}{i} (1/2)^n\right)^k.$$
I want to show that if $k$ is chosen large enough (possibly larger than $n^s$ for some integer $s$), then
$$\Pr[\max_i X_i > (1-\epsilon)n] \geq 1- \frac{1}{\sqrt{n}}.$$
I know from previous questions (Bounds for the maximum of binomial random variables) that if $k = n$ this is unlikely to be the case, but is it true for $k = n^s$ for some power $s$?
Best Answer
See that: $$ \mathbb P[X_k \leq (1-\epsilon) n]^k=(1- \mathbb P[X_k > (1-\epsilon) n])^k\leq \exp(-k\mathbb P[X_k > (1-\epsilon) n]). $$ But then: $$ \mathbb P[X_k > (1-\epsilon) n]=\sum_{i=\lceil (1-\epsilon) n \rceil}^n\binom{n}{i}=\sum_{i=0}^{\lceil \epsilon n \rceil}\binom{n}{i}\geq \sum_{i=0}^{\lceil \epsilon n \rceil}(\frac {n}{{\lceil \epsilon n \rceil}})^i, $$ where the last inequality follows from $\binom{n}{m}\geq (\frac nm)^m$ and using $i\leq{\lceil \epsilon n \rceil}$. Define: $$ f(n,\epsilon)=\sum_{i=0}^{\lceil \epsilon n \rceil}(\frac {n}{{\lceil \epsilon n \rceil}})^i. $$
It is enough to find $k$ such that: $$ \exp(-kf(n,\epsilon))\leq \frac 1{\sqrt n}. $$ which is: $$ k\geq \frac{1\log n}{2f(n,\epsilon)}. $$ Therefore if $k$ is bigger than $\displaystyle\frac{\log n}{2c^n}$ for $c=(\frac 1\epsilon)^\epsilon$, then the inequality is satisfied where the following inequality is used for such derivation: $$ {f(n,\epsilon)}=\sum_{i=0}^{\lceil \epsilon n \rceil}(\frac {n}{{\lceil \epsilon n \rceil}})^i\geq (\frac 1{\epsilon})^{n\epsilon}. $$
Let's explore another approach to the problem. The problem involves approximation of first $m=n(1-\epsilon)$ binomial coefficients. There are nice bounds if $m\leq \frac n2$, i.e., if $\epsilon>\frac 12$. You can look at here for some of the existing bounds where $m\frac 12$ appears mostly as a condition for those bounds.
Intuitively according to law of large numbers, asymptotically $\frac{X_i}{n}$ is a.e. $\frac 12$ for all $i$ and so is the maximum. Therefore for $\epsilon<\frac 12$, the probability goes to zero, which is when $n\to\infty$ first.
Below I give one proof for the case $\epsilon>\frac 12$.
First suppose that $\epsilon>\frac 12$.
Suppose that $Y_i$'s are 0-1 Bernoulli random variables with $p=\frac 12$. Then the binomial random variable $B(n,\frac 12)$ can be written as $\sum _{i=1}^n Y_i$. Define $Z_i=Y_i-\frac 12$ (zero-mean Bernoulli RV taking $+\frac 12,-\frac 12$ as values). We have: $$ \mathbb P[X_k \leq (1-\epsilon) n]=\mathbb P[\sum_{i=1}^n Y_i\leq (1-\epsilon)n]= \mathbb P\big[\sum_{i=1}^n Z_i\leq (\frac 12-\epsilon)n\big]. $$ Using Hoeffding inequality, one can get: $$ \mathbb P\big[\sum_{i=1}^n Z_i\leq (\frac 12-\epsilon)n\big]\leq \exp(-2(\frac 12-\epsilon)^2n), $$ which shows: $$ \mathbb P[\max_i X_i > (1-\epsilon) n]\geq 1-\exp(-2k(\frac 12-\epsilon)^2n). $$ For $k\geq \frac 1{4(\frac 12-\epsilon)^2}\frac{\log n}{n}$, we have: $$ \mathbb P[\max_i X_i > (1-\epsilon) n]\geq 1-\frac 1{\sqrt n}. $$