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 '20 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$
    – Mike Hawk
    Jul 2 '20 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 '20 at 10:55

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


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.