"minimize $e^{-s\alpha} U(s)$ with respect to $s$ for fixed $\alpha$"

Question

I'm trying to learn machine learning using the book "Learning From Data".

I'm working through the exercises and problems of the book and I got stuck at problem 1.9 on page 37, which is about deriving the Chernoff bound.

I got through parts (a) and (b), and worked out the proof for:

$u_1, ..., u_N$ iid random variables, $u = \frac{1}{N}\sum_{n=1}^N u_n$ and $U(s) = \mathbb{E}_{u_n}(e^{su_n})$ for any $n$, then

$$\mathbb{P}[u \geq \alpha] \leq (e^{-s\alpha} U(s))^N$$

Part (c) asks about a fair coin, where $\mathbb{P}[u_n = 0] = \mathbb{P}[u_n = 1] = \frac{1}{2}$.

I'm supposed to "evaluate $U(s)$ as a function of $s$, and minimize $e^{-s\alpha}U(s)$ with respect to $s$ for fixed $\alpha$, $0<\alpha<1$.

I don't have the slightest idea how to tackle that question. Do I need to summon notions such as "moment generating functions"?

Intuitively, it feels like it only depends on $u_n$ compared to $\alpha$, although I'm probably wrong.

Answer 1

$U(s)$ is defined as ${\mathbb E}(e^{su_n})$ so indeed it is the moment generating function of the random variable $u_n$. But this is easy to evaulate, since $u_n$ takes only two values, $0$ and $1$, with equal probability. So $$ U(s):={\mathbb E}(e^{su_n}) = \sum_k e^{sk}{\mathbb P}(u_n=k)=e^0{\mathbb P}(u_n=0)+ e^s{\mathbb P}(u_n=1)=\frac12(1+e^s)\tag1. $$ Now multiply (1) by $e^{-s\alpha}$, regard the result as a function of $s$, and find the value of $s$ that minimizes. You can use calculus to do the minimization, treating $\alpha$ as a constant.