# Application of Hoeffding inequality

Let $Y_i$ be i.i.d Rademacher random variables such that $\mathbb P(Y_i=1)=\mathbb P(Y_i=-1)=1/2$. The Hoeffding inequality syas that For any $a_1,...,a_n \in \mathbb R$ and t>0, we have $$\mathbb P(\sum_{i\leq n} a_iY_i\geq t)\leq exp(-t^2/2\sum_{i\leq n}a_i^2)$$.

Suppose that the random variables $X_1,...,X_n,X'_1 ,...,X_n'$ n are independent and, for all $i \leq n$, $X_i$ and $X_i'$ have the same distribution. Now I want to use the Hoeffding's inequality to prove the following. $$\mathbb P(\sum_{i\leq n}(X_i-X_i')\geq(2t\sum_{i\leq n}(X_i-X_i')^2)^{1/2})\leq e^{-t}.$$

I coundn't find suitable $a_i$ so that the Hoeffding inequality applies. Can anyone help me out?

I'll first rename the second $t$ to $T:$ $$\mathbb P(\sum_{i\leq n}(X_i-X_i')\geq(2T\sum_{i\leq n}(X_i-X_i')^2)^{1/2})\leq e^{-T}.$$
The trick is to note that because $X_i-X'_i$ has a symmetrical distribution about $0$, it has the same distribution as $|X_i-X'_i| \cdot Y_i$ where $Y_i$ is an independent Rademacher variable. So we can take $a_i=|X_i-X'_i|$ and apply Hoeffding's inequality conditioned on $a_1,\cdots,a_n,$ with $T=t^2/2\sum a_i^2.$
• The $a_i$ I found was $|X_i-X_I'|/(\sum_{i\leq n}(X_i-X_i')^2)^{1/2}$, but this is a random variable rather than a real number. Does Hoeffding inequality still apply in this case? – Judith Lee Oct 12 '17 at 12:40
• Yes, you can apply the inequality conditioned on $a_1,\dots,a_n.$ To be more explicit you could write $\mathbb P[...]=\mathbb E[\mathbb P[\dots|a_1,\dots,a_n]]\leq e^{-T}.$ The scaling doesn't really matter, but one advantage of my $a_i$ is that it works even if $\mathbb P[X_i=X_i']>0$ for all $i$ (i.e. discrete variables). – Dap Oct 12 '17 at 17:50