1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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) $\endgroup$ Oct 6 '19 at 19:03
  • 1
    $\begingroup$ 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..." $\endgroup$ Oct 6 '19 at 21:04
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.