I am reading a book where it proves Hoeffding's inequality for symmetric Bernoulli distribution (r.v $X$ takes values -1 or 1 with probabilities $\frac{1}{2}$ each.
The theorem says:
Let $X_1, X_2, \dots, X_N$ be independent symmetric Bernoulli random variables, and let $a = (a_1, \dots, a_N) \in \mathbb{R}^N$. Then for any $t \geq 0$ we have
$$ \mathbb{P} \left\{ \sum_{i=1}^{N} a_i X_i \geq t \right\} \leq \exp\left(- \frac{t^2}{2||a ||^2_2}\right)$$
The proof begins with: "We can assume without loss of generality that $||a||_2 = 1$. I have some vague understanding of why we can assume this WLOG but struggling to communicate it in concrete way. For now, my thought process is following:
We can divide both side inside LHS by $||a||_2$ and write the above inequality as following:
$$\mathbb{P} \left\{ \sum_{i=1}^{N} \frac{a_i}{||a||_2} X_i \geq \frac{t}{||a||_2} \right\} \leq \exp\left(- \frac{1}{2}\left(\frac{t}{||a||}\right)^2\right)$$
Substituting $\frac{a_i}{||a||_2} = b_i$ and $t' = \frac{t}{||a||}$, we get following:
$$ \mathbb{P} \left\{ \sum_{i=1}^{N} b_i X_i \geq t' \right\} \leq \exp\left(- \frac{t'^2}{2}\right)$$
But verbally how should I explain why this WLOG is valid?hoe
Best Answer
Suppose that the inequality $$ \tag{*}\mathbb{P} \left\{ \sum_{i=1}^{N} a_i X_i \geq t \right\} \leq \exp\left(- \frac{t^2}{2 }\right) $$ holds for all $t\geq 0$ and all $a_1,\dots,a_N$ such that $\sum_{i=1}^Na_i^2=1$.
Now let $a_1,\dots,a_N\in\mathbb R$ and $t\gt 0$. We want to prove that
$$\tag{**}\mathbb{P} \left\{ \sum_{i=1}^{N} a_i X_i \geq t \right\} \leq \exp\left(- \frac{t^2}{2||a ||^2_2}\right).$$ If $\sum_{i=1}^Na_i^2=0$, there is nothing to prove, since all the involved terms are zero. If $\sum_{i=1}^Na_i^2\neq 0$, we can indeed (as said in the opening post) deduce (**) from (*) by applying the latter inequality to $\widetilde{a_i}=a_i/\sqrt{\sum_{j=1}^Na_j^2}$ and $ \widetilde{ t}=t/\sqrt{\sum_{j=1}^Na_j^2}$.