1
$\begingroup$

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

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

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
2
  • $\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
    Commented Jun 27, 2013 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
    Commented Jun 27, 2013 at 19:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .