# WLOG Assumption in Hoeffding's inequality proof: $||a||_2 = 1$

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

• If you're just asking what the underlying property is... note that the inequality is of the form $f(a,t) \leq g(a,t)$ where both $f,g$ are homogeneous of the same order (which is the property you used in your justification) Oct 6 '19 at 19:03
• I would say either just "scale invariance" or "since both left and right hand sides are unchanged when $t$ and the $a_i$s are rescaled..." Oct 6 '19 at 21:04

## 1 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}$$.