Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a random variable $U$ equal to the sum of $j$ identical, independent other random variables $U_1$ through $U_j$, all of which have mean 0. $j$ is going to be a very big number. For some constant $s$ that's between 0 and 0.4, $\forall i \in [1, j], \left| U_i \right| < \frac{log~j}{s}$.

Now, for some other constants $k$ and $c$, I want to use a Chernoff bound to show that $U$ is bounded by $\frac{c\sqrt{j \log k} \log j}{s}$ with extremely high probability.

I started with the Chernoff bound, then scaled it to allow for random variables of any size, not just from 0 to 1.

$$ P(S > \mu + \alpha) \le e^{-2m\alpha^2} \\ P(U > j\alpha\frac{\log j}{s}) \le e^{-2m\alpha^2} \text{ since there exist j of the $U_j$ variables, each bounded by $\frac{\log~j}{s}$.} \\ $$

However, I'm not sure where to go from here. Am I on the right track? How can I manipulate this expression to the bound I want for $U$?

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.