Say I have n independent variables $\{X_1,X_2 \dots X_n\}$ with Expectation 0 such that $Pr(|X_n| > \alpha) < e^{-\lambda \alpha}$. Can we produce chernoff type inequalities for the sum of these random variables ? One idea I have to use the variance of these random variables . Can we use the given property to bound the variance of these random variables ?

Thanks in advance

  • $\begingroup$ Can you elaborate on what you mean by "Chernoff-type?" I've heard many things referred to as Chernoff bounds... $\endgroup$ – gogurt Jun 27 '13 at 5:51

The hypothesis implies that the random variable $\mathrm e^{\mu|X_k|}$ is integrable for every $\mu\lt\lambda$ and every $k$. Fix some positive $\mu\lt\lambda$. By independence, the random variable $\mathrm e^{\mu(|X_1|+|X_2|+\cdots+|X_n|)}$ is integrable. By the triangular inequality, $\mathrm e^{\mu|X_1+X_2+\cdots+X_n|}\leqslant\mathrm e^{\mu(|X_1|+|X_2|+\cdots+|X_n|)}$ hence the random variable $\mathrm e^{\mu|X_1+X_2+\cdots+X_n|}$ is integrable. In particular, $P(|X_1+X_2+\cdots+X_n|\gt\alpha)\leqslant C_n\cdot\mathrm e^{-\mu\alpha}$ for some finite constant $C_n$.

| cite | improve this answer | |
  • $\begingroup$ Hi thanks for the answer. I am a but unclear about why $e^{\mu |X_1 + X_2 + \ldots X_n|}$ being integrable imply that $P(|X_1 + X_2 + \ldots X_n| > \alpha) \leq C_n.e^{-\mu \alpha}$. Also for my case since $C_n$ since it depends on n would need to be taken into account can we get a bound on it? $\endgroup$ – user1189053 Jun 27 '13 at 16:49
  • $\begingroup$ A trivial upper bound is $C_n\leqslant E(\mathrm e^{\mu|X_1|})E(\mathrm e^{\mu|X_2|})\cdots E(\mathrm e^{\mu|X_n|})$. This answers both your questions simultaneously. $\endgroup$ – Did Jun 27 '13 at 19:16

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.