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?

  • 1
    $\begingroup$ It's Hoeffding $\endgroup$ Jul 1, 2020 at 23:52
  • 2
    $\begingroup$ unless i'm missing something, it looks like you have proved an ever stronger inequality, considering that -7^2/8^2<-1/8 $\endgroup$ Jul 2, 2020 at 0:29
  • $\begingroup$ 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. $\endgroup$ Jul 2, 2020 at 10:55

1 Answer 1


After quite sometime I realized what is wrong with the calculations in the question and how to get the correct result. First, the error in the above calculation.

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)$$

Now, here is the proper solution:

$$ 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) $$


You must log in to answer this question.

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