Hoeffding's Inequality for sum of Bernoulli random variables

In the book High-Dimensional Probability, by Roman Vershynin, the Hoeffding's Inequality is stated as the following:

Let $$X_1,...,X_N$$ be independent symmetric Bernoulli random variables (e.i $$P(X=-1)=P(X=1)=1/2$$), and let $$a = (a_1,...,a_N) \in \mathbb R^N$$. Then, for any $$t \geq 0$$, we have $$P\left(\sum^N_{i=1}a_i X_i \geq t \right) \leq e^{\frac{-t^2}{2||a||_2^2}}$$

The author then claims that for a fair coin, one can transform the symmetric Bernoulli into a regular Bernoulli (e.g $$Y = 2X - 1$$) and use Hoeffding's Inequality to show that the probability of getting at least $$3N/4$$ heads in $$N$$ coin tosses has an exponential decay, hence:

$$P\left(\sum^N_{i=1}Y_i \geq\frac{3N}{4} \right) \leq e^{-\frac{N}{8}}$$

I've tried to arrive at such bound, but my calculations are yielding a differnt result. Here is what I've tried:

Since $$Y_i = 2X_i -1$$, therefore $$P\left(\sum^N_{i=1}Y_i \geq\frac{3N}{4} \right) = P\left(2\left(\sum^N_{i=1}X_i\right) - N \geq\frac{3N}{4} \right) = P\left(\sum^N_{i=1}X_i \geq\frac{7N}{8} \right) \leq e^{-\frac{7^2 N^2}{2\cdot 8^2 N}}$$

Can someone help me understand what I'm doing wrong and perhaps show how to properly do this?

• It's Hoeffding Jul 1, 2020 at 23:52
• unless i'm missing something, it looks like you have proved an ever stronger inequality, considering that -7^2/8^2<-1/8 Jul 2, 2020 at 0:29
• Hey Mike. There was an error in the calculation. Ive fixed it. But still, as you say, the bound is stronger. I wonder if it's correct though, since it differs from what the book shows. Cause I don't see why the book would give a weaker bound. Jul 2, 2020 at 10:55

The Bernoulli variable is actually $$X_i$$ not $$Y_i$$, so the correct probability for a fair coin to give more that $$\frac{3N}{4}$$ is $$P\left( \sum^N_{i=1}X_i \geq \frac{3N}{4} \right) \leq exp(-N/8)$$
$$P\left( \sum^N_{i=1}X_i \geq \frac{3N}{4} \right)= P\left( \sum^N_{i=1}\frac{(Y_i+1)}{2} \geq \frac{3N}{4} \right)=$$ $$= P\left( \sum^N_{i=1}Y_i \geq \frac{3N}{2}-N \right)\leq exp\left( \frac{-(\frac{3N}{2}-N)^2}{N} \right) = exp(-N/8)$$