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, 2019 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, 2019 at 21:04

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .