## Appendix G Bound on the Upper Tail of the Binomial Cumulative Distribution Function--Part 2  
**Lemma A4**.: _Let \(0<\varepsilon<1\) and \(\varepsilon<\frac{k}{n}<1\). Then,_  
\[\sum_{j=k}^{n}\binom{n}{j}e^{j}(1-\varepsilon)^{n-j}\leq 2^{n\left[H(\frac{ k}{n})-T_{\varepsilon}(\frac{k}{n})\right]}\left[\frac{k(1-\varepsilon)}{k(1- \varepsilon)-(n-k)\varepsilon}\right]. \tag{106}\]  
Proof.: Recall that the equation of the tangent line to the binary entropy function \(H(\delta_{\beta})\) at the specific point \(\delta_{\beta}=\varepsilon\) is given by  
\[T_{\varepsilon}(\delta_{\beta})\] \[\stackrel{{(a)}}{{=}}H(\varepsilon)+(\delta_{\beta} -\varepsilon)\left.\frac{\mathrm{d}H(\delta_{\beta})}{\mathrm{d}\delta_{\beta }}\right|_{\delta_{\beta}=\varepsilon}\] \[\stackrel{{(b)}}{{=}}H(\varepsilon)+(\delta_{\beta} -\varepsilon)\log\left(\frac{1-\varepsilon}{\varepsilon}\right)\] \[=H(\varepsilon)+(\delta_{\beta}-\varepsilon)\left[\log(1- \varepsilon)-\log\varepsilon\right] \tag{107}\] \[\stackrel{{(c)}}{{=}}-\varepsilon\log\varepsilon-(1 -\varepsilon)\log(1-\varepsilon)+\delta_{\beta}\log(1-\varepsilon)-\delta_{ \beta}\log\varepsilon-\varepsilon\log(1-\varepsilon)+\varepsilon\log\varepsilon\] \[=-\varepsilon\log\varepsilon-\log(1-\varepsilon)+\varepsilon\log (1-\varepsilon)+\delta_{\beta}\log(1-\varepsilon)-\delta_{\beta}\log \varepsilon-\varepsilon\log(1-\varepsilon)+\varepsilon\log\varepsilon\] \[=-\log(1-\varepsilon)+\delta_{\beta}\log(1-\varepsilon)-\delta_{ \beta}\log\varepsilon\] \[=-\log(1-\varepsilon)+\delta_{\beta}\log(1-\varepsilon)-\delta_{ \beta}\log\varepsilon\] \[=-\delta_{\beta}\log(\varepsilon)-(1-\delta_{\beta})\log(1- \varepsilon),\]  
where \((a)\) holds by definition of a tangent line to a function at specific point, \((b)\) follows since derivative of the entropy function reads the negative of the logit function, i.e.,  
\[\frac{\mathrm{d}H(\delta_{\beta})}{\mathrm{d}\delta_{\beta}}=-\text{logit} \left(\delta_{\beta}\right)\triangleq-\log\left(\delta_{\beta}/(1-\delta_{ \beta})\right), \tag{108}\]  
for \(0<\delta_{\beta}<1\), and \((c)\) holds by definition of the entropy function, i.e.,  
\[H(\varepsilon)\triangleq-\varepsilon\log\varepsilon-(1-\varepsilon)\log(1- \varepsilon). \tag{109}\]  
Therefore, exploiting (108) we obtain,  
\[T_{\varepsilon}\left(\frac{k}{n}\right)=-\frac{k}{n}\log(\varepsilon)-(1- \frac{k}{n})\log(1-\varepsilon), \tag{110}\]which implies \(-nT_{\varepsilon}(\frac{k}{n})=k\log(\varepsilon)+(n-k)\log(1-\varepsilon)\). Thereby,  
\[2^{-nT_{\varepsilon}(\frac{k}{n})}=\varepsilon^{k}(1-\varepsilon)^{n-k}. \tag{101}\]  
Now, observe that the Binomial coefficient \(\binom{n}{k}\) where \(k\geq 1\) and \(n-k\geq 1\), can be upper bounded as follows ([34] see p. 353)  
\[\binom{n}{k}\leq 2^{nH(\frac{k}{n})}. \tag{102}\]  
Therefore,  
\[\frac{k(1-\varepsilon)}{k(1-\varepsilon)-(n-k)\varepsilon}\cdot \binom{n}{k}\varepsilon^{k}(1-\varepsilon)^{n-k}\stackrel{{(a)}} {{\leq}}\frac{k(1-\varepsilon)}{k(1-\varepsilon)-(n-k)\varepsilon}\cdot 2^{nH( \frac{k}{n})}\cdot\varepsilon^{k}(1-\varepsilon)^{n-k}\] \[\stackrel{{(b)}}{{\leq}}\frac{k(1-\varepsilon)}{k(1 -\varepsilon)-(n-k)\varepsilon}\cdot 2^{nH(\frac{k}{n})}\cdot 2^{-nT_{ \varepsilon}(\frac{k}{n})}=\left[\frac{k(1-\varepsilon)}{k(1-\varepsilon)-(n -k)\varepsilon}\right]\cdot 2^{n\left[H(\frac{k}{n})-T_{\varepsilon}(\frac{k}{n}) \right]}, \tag{103}\]  
where \((a)\) holds by (101), and \((b)\) follows by exploiting (101). Now, recalling (100), we obtain  
\[\sum_{j=k}^{n}\binom{n}{j}\varepsilon^{j}(1-\varepsilon)^{n-j}\leq\frac{k(1- \varepsilon)}{k(1-\varepsilon)-(n-k)\varepsilon}2^{n\left[H(\frac{k}{n})-T_{ \varepsilon}(\frac{k}{n})\right]}. \tag{104}\]  
This completes the proof of Lemma A4.