How to prove error of ensemble model by using the Hoeffding's inequality? Under Binary classification situation,
error between function $f$ and basic learner(classifier) $h_i(x)$ is
$$P(h_i(x)≠f(x))=\mathcal{E}.$$
It is assumed that $T$ basic classifiers are combined by a voting method, and if more than half of the basic classifiers get the correct answer, it is assumed that the ensemble classifier gives the correct answer.
(Assume $T$ is odd integer for convenience.)
$$H(x) = \operatorname{sign}\left(\sum_{i=1}^T h_i(x)\right)$$
If the error rates of the basic classifier are assumed to be independent of each other, the error rate of the ensemble classifier can be known by the Hoeffding's inequality.
$$ P(H(x) ≠ f(x)) = \sum_{k=0}^{\lfloor T/2\rfloor} {}_T \mathrm{ C }_k (1-\mathcal{E})^k \mathcal{E}^{(T-k)} \le \exp\left(-\frac{1}{2}T(1-2\mathcal{E})^2\right).$$
I can't understand how the result(exponential part) is derived.
I think $\lfloor T/2\rfloor = \frac{(T-1)}{2}$ because $T$ is odd integer by the assumption above.
and given basic concept of the Hoeffding's inequality of binary classification is
$$P(H(n) \le k) = \sum_{i=0}^{k} {}_n \mathrm{ C }_i \: p^i (1-p)^{(n-i)}
\le \exp\left(-2\mathcal{E}^2n\right), \; (k=(p- \mathcal{E})n \; \textrm{and} \; \mathcal{E}>0).$$
 A: Hoeffding's inequality is for a sum of independent variables $S_T = \sum_{i=1}^T X_i$ where $a_i \leq X_i \leq b_i$
$$P(S_T - E[S_T] \geq t) \leq \exp \left(- \frac{2t^2}{\sum_{i=1}^T (b_i - a_i)^2}\right).$$

*

*You have a sum of (presumably) independent Bernoulli variables so $a_i = 0$ and $b_i$ = 1 and $\sum_{i=1}^T (b_i - a_i)^2 = T. $

*$S_T = T-H_T$ is a binomial distributed variable with $E[S_T] = T(\mathcal{E})$

*Instead of $H_T \leq  \lfloor T/2 \rfloor = (T-1)/2$ we can look for the condition $T - S_T \leq (T-1)/2 $ or $S_T \geq (T+1)/2.$

*If you use $t =(T+1)/2 - E[S_T]$ then the condition from Hoeffding's inequality $$S_T - E[S_T] \geq t$$ becomes $$S_T - E[S_T] \geq (T+1)/2 - E[S_T]$$ or $$S_T  \geq (T+1)/2.$$
Filling in these values for $t$, $a_i$, $b_i$ gives
$$P\left(S_T  \geq  \frac{T-1}{2}\right) \leq \exp \left(-2 \frac{\left( \frac{T+1}{2} - T\mathcal{E}\right)^2}{T}\right) < \exp \left(-2 \frac{\left( \frac{T}{2} - T\mathcal{E}\right)^2}{T}\right) = \exp \left(-2 T\left( \frac{1}{2} - \mathcal{E}\right)^2\right).$$
