1
$\begingroup$

Given a sequence of Rademacher random variables $\{X_k\}_{k\geq1}$. The definition of Rademacher random variables can be found in Inequality with Rademacher variables.

I was wondering how to prove that $\mathbb{P}\left(\frac{\sum X_i}{n}\geq x\right) \leq \exp(-nF(x))$ where $$F(x)=\frac{1}{2}(1-x)\ln(1-x)+\frac{1}{2}(1+x)\ln(1+x)\,.$$

My problem is I don't even know which way I should follow to prove it. The Hoeffding inequality looks useful. But I cannot find a starting point

$\endgroup$
1
$\begingroup$

This is very similar to the standard derivation of the Chernoff bound, with some nice simplifications coming from the knowledge that the summands are Rademacher.


Fix $x\in(0,1)$. Start like the proof of the Chernoff bound, using Markov's inequality: $$ \mathbb{P}\left\{ \sum_{k=1}^n X_k \geq nx \right\} = \mathbb{P}\left\{ e^{t\sum_{k=1}^n X_k} \geq e^{tnx} \right\} \leq \frac{\mathbb{E}[e^{t\sum_{k=1}^n X_k}]}{e^{tnx}} \tag{1} $$ for every $t> 0$. By independence of the $X_k$'s, we can thus write, for all $t>0$, $$ \mathbb{P}\left\{\frac{1}{n}\sum_{k=1}^n X_k \geq x \right\} \leq \frac{\mathbb{E}[\prod_{k=1}^n e^{t X_k}]}{e^{tnx}} =\frac{\prod_{k=1}^n\mathbb{E}[e^{t X_k}]}{e^{tnx}} =\frac{\cosh^n t}{e^{tnx}} = \left(\frac{\cosh t}{e^{tx}}\right)^n \tag{2} $$ the second-to-last equality using the expression of the MGF of a Rademacher r.v.. It only remains to choose $t>0$ to minimize the RHS. Studying the function $t\mapsto \frac{\cosh t}{e^{tx}}$ by differentiation shows that this minimum is achieved for $$ t^\ast \stackrel{\rm def}{=} \frac{1}{2}\ln\frac{1+x}{1-x}\,.\tag{3} $$ Plugging back into (2), this yields $$ \mathbb{P}\left\{\frac{1}{n}\sum_{k=1}^n X_k \geq x \right\} \leq \left(\frac{\cosh t^\ast}{e^{t^\ast x}}\right)^n = e^{-n F(x)} \tag{4} $$ where $$\begin{align*} F(x) &= \ln \frac{e^{t^\ast x}}{\cosh t^\ast} = \ln\left( \sqrt{1-x^2}\cdot e^{t^\ast x} \right) = \ln\left( \sqrt{1-x^2}\cdot e^{\frac{x}{2}\ln\frac{1+x}{1-x}} \right)\\ &= \frac{1}{2}\ln\left( (1+x)(1-x)\cdot e^{x\ln\frac{1+x}{1-x}} \right) = \frac{1}{2}\ln\left( (1+x) e^{x\ln(1+x)}\cdot (1-x)e^{-x\ln(1-x)} \right)\\ &= \frac{1}{2}\left( \ln(1+x) + x\ln(1+x) + \ln(1-x)-x\ln(1-x)\right) \\ &= \frac{1}{2}\left( (1+x)\ln(1+x)+(1-x)\ln(1-x)\right) \tag{5} \end{align*}$$ as sought.

$\endgroup$
  • $\begingroup$ It's very clear. Thanks. $\endgroup$ – YHH Apr 17 '18 at 16:02
  • $\begingroup$ @YHH You're welcome. $\endgroup$ – Clement C. Apr 17 '18 at 16:24

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.