Maximum of $k$ binomial random variables? 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$?
 A: 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}.
$$
