# Help with understanding the proof of Hoeffding's inequality?

I'm doing machine learning and now I'm struggling to understand the proof of Hoeffding's inequality. The proof I'm using for learning can be found here: Hoeffding proof

Now for starters what bothers me in the proof on page 1 is the selection of $T = \Theta(\displaystyle\frac{1}{\alpha^2}log\frac{1}{\delta})$. This is not clear enough for me...could someone clarify this? Another two points are the in the beginning of page 2. Why is

$Pr[|Y-E(Y)| \geq n\alpha] \leq Pr[Y-E(Y) \geq n\alpha] + Pr[|Y-E(Y)| \leq -n\alpha]$?

Also what inequality does the sentence "Observe that the expectation of Y does not appear in the upperbound." refer to? Also the rest of the derivation is unclear until the part

1.2.2 Using Moment Generating Function and Independence

Can anyone clarify these derivations for me? Note that I'm only interested in clarification for the end of first page and the beginning of the second page. If someone wants to explain the full proof more intuitively that will also be super! Thank you for any help!! =)

• The second term should be $Pr[Y-E(Y) \leq -n\alpha]$. In fact this expression is an equality. You see, $|X| \geq a$ iff $X \geq a$ or $X \leq -a$ and these are disjoint. Unless $a=0$. Mar 15 '13 at 8:28
• Thank you, sorry for the mistake, I fixed it. Thank you for that =) If it is equality then why does the proof write it as inequality? Mar 15 '13 at 8:37
• My guess is that if $\alpha = 0$, you are counting the zero case i.e. $Pr[Y-E(Y)=0]$ twice in RHS. But then LHS $= Pr[|Y-E(Y)|\geq 0]$ is always 1. Mar 15 '13 at 8:57
• Thank you for your answer, I appreciate a lot your help! =) I have just one problem with your answer :( If you look at the proof paper, the definition of the Hoeffding inequality states that $\alpha > 0$...now what? :D So the case (If I understand correctly) $Pr[Y−E(Y)=0]$ shouldn't happen...? am I mistaken or...? :) Mar 15 '13 at 9:09
• No. If Y is discrete, it can happen. But if you pick $\alpha > 0$, it won't be considered when you take $Pr[|Y-E[Y]| > n\alpha]$. If a proof uses an inequality(either $\leq$ or $\geq$, no strict ones) for it's arguments, and then someone shows it's an equality, the proof doesn't go wrong. Mar 15 '13 at 9:23

1) I explained in my comments why $$P(|X|\geq a) = P(X \geq a) + P( X \leq -a)$$ for $a>0$.
2) He is talking about the RHS of Hoeffding inequality. The statement that it does not depend on $E[Y]$ is a little nebulous. Because $$E[Y] = \sum_{k=1}^n E[X_k]$$ and each $E[X_i]$ depends on $R_i=b_i - a_i$. What he probably meant was that given the bounds $b_i$ and $a_i$, RHS doesn't depend additionally on the true values of $E[X_i]$ and hence $E[Y]$. In fact it doesn't even depend on $b_i$ and $a_i$ but instead their difference.
3) If $x,y \in [a,b]$, observe that the smallest value of $x-y$ is when $x=a$ and $y=b$ (the two extremes) and the largest is when $x=b$ and $y=a$. The range of x-y is therefore $[-(b-a),b-a] = [-R,R]$. If $X_i$ are independent, so is $Z_i = X_i-E[X_i]$.
Thus $$P(Y-E[Y] \geq n\alpha) = P(\sum_{k=1}^n (X_k - E[X_k]) \geq n\alpha)$$ $$= P(\sum_{k=1}^n Z_k \geq n\alpha)$$ $$= P(t\sum_{k=1}^n Z_k \geq tn\alpha)$$ For $t>0$.