0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Judith Lee Oct 12 '17 at 12:40
  • $\begingroup$ 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). $\endgroup$ – Dap Oct 12 '17 at 17:50

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.