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$?

  • $\begingroup$ How do you draw the subsets? All $2^n$ equally likely? When you say "without replacement" does that mean the distribution of $S_2$ (say) depends on the choice you made for $S_1$? Or are we to understand the question to be about the max of $k$ independent binomial r.v.s, each with parameters $n$ and $1/2$? $\endgroup$ – kimchi lover Aug 27 '17 at 17:56
  • $\begingroup$ You are right this makes it confusing. Its the max of k independent binomials with parameters n and 1/2. $\endgroup$ – Asterix Aug 27 '17 at 18:48
  • $\begingroup$ I edited the question to be about the maximum of k binomial random variables, and added a link to a previous question on the topic $\endgroup$ – Asterix Aug 27 '17 at 19:54
  • $\begingroup$ Thanks! I'll look into it this evening. $\endgroup$ – kimchi lover Aug 27 '17 at 19:56

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.