Context: We know that $u_{1},...,u_{N}$ is a sequence of iid random variables, $U(s)=\mathbb{E}_{u_{n}}(e^{su_{n}})$.
We can assume that we have already proven that $\mathbb{P}[u\geq\alpha]\leq(e^{-s\alpha}U(s))^{N}$, where $0<\alpha<1$
Task: Supose $\mathbb{P}[u_{n}=0]=\mathbb{P}[u_{n}=1]=\frac{1}{2}$ (fair coin).
I must do three things:
- Evaluate $U(s)$
- Minimize $e^{-s\alpha}U(s)$
Conclude from 1, 2 that for $0<\epsilon<\frac{1}{2}$ => $\mathbb{P}[u\geq\mathbb{E}(u)+\epsilon]\leq2^{-\beta N}$, knowing that
a. $\beta=1+(\frac{1}{2}+\epsilon)\log_{2}(\frac{1}{2}+\epsilon)+(\frac{1}{2}-\epsilon)\log_{2}(\frac{1}{2}-\epsilon)$
b. $\mathbb{E}(u)=\frac{1}{2}$
Solutions for 1,2:
ad 1. $U(s)=\mathbb{E}_{u_{n}}[e^{su_{n}}]=e^{s*0}\mathbb{P}[u_{n}=0]+e^{s*1}\mathbb{P}[u_{n}=1]=\frac{1}{2}(1+e^{s})$
ad 2. Now, I'm ready to minimize $e^{-s\alpha}U(s)=\frac{1}{2}e^{-s\alpha}+\frac{1}{2}e^{s(1-\alpha)}$ , so I set the derivative equal to $0$, yielding
$$(e^{-s\alpha}U(s))'=(\frac{1}{2}e^{-s\alpha}+\frac{1}{2}e^{s}e^{-s\alpha})'=(\frac{1}{2}e^{-s\alpha}+\frac{1}{2}e^{s(1-\alpha)})'=-\frac{\alpha}{2}e^{-s\alpha}+(\frac{1}{2}-\frac{\alpha}{2})e^{s(1-\alpha)}=0\\(\frac{1}{2}-\frac{\alpha}{2})e^{s(1-\alpha)}=\frac{\alpha}{2}e^{-s\alpha}\\(1-\alpha)e^{s(1-\alpha)}=\alpha e^{-s\alpha}\\\frac{(1-\alpha)}{\alpha}\frac{e^{s(1-\alpha)}}{e^{-s\alpha}}=1\\\frac{(1-\alpha)}{\alpha}e^{s(1-\alpha)}e^{s\alpha}=\frac{\alpha}{1-\alpha}\\e^{s(1-\alpha)+s\alpha}=\frac{\alpha}{1-\alpha}\\e^{s}=\frac{\alpha}{1-\alpha}\\\ln(e^{s})=\ln(\frac{\alpha}{1-\alpha})\\s=\ln(\frac{\alpha}{1-\alpha})$$
Problem with 3: I went the path:
Let $0<\alpha=\mathbb{E}(u)+\epsilon<1$ , where $\mathbb{E}(u)=\frac{1}{2}$ in $\mathbb{P}[u\geq\alpha]\leq(e^{-s\alpha}U(s))^{N}\\\mathbb{P}[u\geq\mathbb{E}(u)+\epsilon]\leq(e^{-s(\mathbb{E}(u)+\epsilon)}U(s))^{N}$
where $U(s)=\frac{1}{2}(1+e^{s})$
Because we are interested in the tightest bound I assumed that
$s=\ln(\frac{\alpha}{1-\alpha})$
For the RHS of the inequality skipping the Nth power yielding this
$$e^{-s(\alpha)}U(s)=\frac{1}{2}e^{-s\alpha}(1+e^{s})=\frac{1}{2}e^{-s\alpha}(1+e^{s})=\frac{1}{2}e^{-ln(\frac{\alpha}{1-\alpha})(\alpha)}(1+e^{\ln(\frac{\alpha}{1-\alpha})})=\frac{1}{2}(\frac{\alpha}{1-\alpha})^{-\alpha}(1+\frac{\alpha}{1-\alpha})=\\=\frac{1}{2}(\frac{1-\alpha}{\alpha})^{\alpha}(1+(\frac{1-\alpha}{\alpha})^{-1})=\frac{1}{2}(\frac{1-\alpha}{\alpha})^{\alpha}+\frac{1}{2}(\frac{1-\alpha}{\alpha})^{\alpha-1}=\\=\frac{1}{2}2^{(\frac{1}{2}+\epsilon)\log_{2}(\frac{\frac{1}{2}-\epsilon}{\frac{1}{2}+\epsilon})}+\frac{1}{2}2^{(\epsilon-\frac{1}{2})\log_{2}(\frac{\frac{1}{2}-\epsilon}{\frac{1}{2}+\epsilon})}=\\=2^{(\frac{1}{2}+\epsilon)(\log_{2}(\frac{1}{2}-\epsilon)-\log_{2}(\frac{1}{2}+\epsilon))-1}+2^{(\epsilon-\frac{1}{2})(\log_{2}(\frac{1}{2}-\epsilon)-\log_{2}(\frac{1}{2}+\epsilon))-1}$$
I plotted (a) $2^{-\beta N}$ and (b) $2^{(\frac{1}{2}+\epsilon)(\log_{2}(\frac{1}{2}-\epsilon)-\log_{2}(\frac{1}{2}+\epsilon))-1}+2^{(\epsilon-\frac{1}{2})(\log_{2}(\frac{1}{2}-\epsilon)-\log_{2}(\frac{1}{2}+\epsilon))-1}$ and I got the same plot. I cannot transform the complex equation (b) to (a).
Could anyone give me a hint how to complete 3?
P.S. I'm not a mathematician or statistician so please forgive me if I make basic errors.
Thanks to @Did's help, the solution for 3 might look like this:
Let $0<\alpha=\mathbb{E}(u)+\epsilon<1$ , where $\mathbb{E}(u)=\frac{1}{2}$ in $\mathbb{P}[u\geq\alpha]\leq(e^{-s\alpha}U(s))^{N}\\\mathbb{P}[u\geq\mathbb{E}(u)+\epsilon]\leq(e^{-s(\mathbb{E}(u)+\epsilon)}U(s))^{N}$
where $U(s)=\frac{1}{2}(1+e^{s})$
Because we are interested in the tightest bound I assumed that
$s=\ln(\frac{\alpha}{1-\alpha})$
For the RHS of the inequality skipping the Nth power yielding this
$e^{-s(\alpha)}U(s)=\frac{1}{2}e^{-s\alpha}(1+e^{s})=\frac{1}{2}e^{-s\alpha}(1+e^{s})=\frac{1}{2}e^{-ln(\frac{\alpha}{1-\alpha})(\alpha)}(1+e^{\ln(\frac{\alpha}{1-\alpha})})=\frac{1}{2}(\frac{\alpha}{1-\alpha})^{-\alpha}(1+\frac{\alpha}{1-\alpha})\\=\frac{1}{2}\frac{\alpha^{-\alpha}}{(1-\alpha)^{-\alpha}}(\frac{1}{1-\alpha})=\frac{1}{2}\alpha^{-\alpha}(1-\alpha)^{\alpha}(1-\alpha)^{-1}=\frac{1}{2}\alpha^{-\alpha}(1-\alpha)^{\alpha-1}$
Using the above equtation I want $2^{-\beta N}=(e^{-s(\alpha)}U(s))^{N}$, hence
$2^{-\beta N}=(e^{-s(\alpha)}U(s))^{N}\\2^{-\beta}=e^{-s(\alpha)}U(s)\\2^{-\beta}=\frac{1}{2}\alpha^{-\alpha}(1-\alpha)^{\alpha-1}\\\log_{2}(-\beta)=\log_{2}(\frac{1}{2}\alpha^{-\alpha}(1-\alpha)^{\alpha-1})\\-\beta=\log_{2}(\frac{1}{2})+\log_{2}(\alpha^{-\alpha})+\log_{2}((1-\alpha)^{\alpha-1})\\-\beta=-1-\alpha\log_{2}(\alpha)+(\alpha-1)\log_{2}(1-\alpha)\\\beta=1+\alpha\log_{2}(\alpha)+(1-\alpha)\log_{2}(1-\alpha)$
Since $\alpha=\mathbb{E}(u)+\epsilon=\frac{1}{2}+\epsilon$
$\beta=1+(\frac{1}{2}+\epsilon)\log_{2}(\frac{1}{2}+\epsilon)+(\frac{1}{2}-\epsilon)\log_{2}(\frac{1}{2}-\epsilon)$
What was to show.