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?
Best Answer
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) $$