I'm studying machine learning and I'm stuck on a very simple proof. I'm going to explain the background, but in the end I just want to prove an inequality.
Suppose I have $K$ classifiers that are trained with the same dataset and each of them have an accuracy $1 - \epsilon > 0.5$. Also suppose that errors are independent, i.e., if a classifier makes a mistake on the classification of a sample, then we can say nothing about the outcomes of the other classifiers. The idea is that each classifier, given an input sample $\mathbf{x}$ outputs the class it belongs to $y$ (according to that classifier, which can make mistakes). Then, let $y_i\,i = 1, \dots, K$ be the final answer of each classifier and $y_i \in \{0, 1\}$ I take the final answer of the ensemble of classifiers to be the $y$ which comes out the most.
I want to prove that, under the assumption that $\epsilon \leq 0.5$, then the accuracy of the ensemble is greater than the accuracy of any classifier ($1 - \epsilon$).
So, being errors independent, I wrote that $$P(E \geq \left\lceil\frac{K}{2}\right\rceil) = 1 - \sum_{i = 0}^{\left\lceil\frac{K}{2}\right\rceil - 1} \binom{K}{i} \epsilon^i(1 - \epsilon)^{K - i}$$ which is the probability that the entire ensemble makes exactly or more than $\left\lceil\frac{K}{2}\right\rceil$ mistakes (if K is odd and more than $\left\lceil\frac{K}{2}\right\rceil$ classifier make the wrong guess, then the majority is wrong; if K is even and exactly $\left\lceil\frac{K}{2}\right\rceil = \frac{K}{2}$ classifiers make the wrong guess, there is no majority, so I could pick a random class, but let's just say the guess is wrong in that case, just as an initial approximation).
So the accuracy of the ensemble is $1 - P(E \geq \left\lceil\frac{K}{2}\right\rceil) = \sum_{i = 0}^{\left\lceil\frac{K}{2}\right\rceil - 1} \binom{K}{i}\epsilon^i(1 - \epsilon)^{K - i}$ and I need to prove that $\sum_{i = 0}^{\left\lceil\frac{K}{2}\right\rceil - 1} \binom{K}{i}\epsilon^i(1 - \epsilon)^{K - i} > 1-\epsilon$ and I'm stuck at proving this inequality.