0
$\begingroup$

Let $X_1, X_2, \ldots X_n$ be independent random variables, can we apply the Chernoff Bound Theorem to bound $E\left[\sum_i \Theta( \widehat{X_{i}}))\right]$ if $\Theta( \widehat{X_{i}}) : \widehat{X_{i}} \rightarrow \mathbb{R}$, i.e, $\Theta(\widehat{X_{i}})$ is a mapping from the random variable to a real number?

Thus, is the following Chernoff Bound applicable in the above scenario? $$ P\left[\sum_i \Theta( \widehat{X_{i}})\leq(1-\epsilon) E\left[\sum_i \Theta( \widehat{X_{i}}))\right] \right] \leq e^{-\frac{\epsilon^2}{2} E\left[\sum_i \Theta( \widehat{X_{i}}))\right] } $$

Additionally, would the same Chernoff Bound be applicable for $E\left[\sum_i a_i \cdot \Theta( \widehat{X_{i}}))\right]$, where $a_i$ is a real numbered constant from the set $A$?

$\endgroup$
2
  • $\begingroup$ Are you sure you quote Chernoff bound correctly? en.wikipedia.org/wiki/Chernoff_bound $\endgroup$
    – van der Wolf
    Commented Apr 15 at 8:33
  • $\begingroup$ this is another version of the Chernoff Bound I found in lecture notes @vanderWolf $\endgroup$
    – ephemeral
    Commented Apr 15 at 8:37

1 Answer 1

Reset to default
2
$\begingroup$

I think McDiarmid inequality is what you are looking for. https://en.wikipedia.org/wiki/McDiarmid%27s_inequality

$\endgroup$
2
  • $\begingroup$ Isn't this a function of all Random variables? What i've stated is the sum of function of individual random variables, would this inequality be useful here? $\endgroup$
    – ephemeral
    Commented Apr 15 at 12:23
  • $\begingroup$ The inequality is more general than what you need. A function of individual random variables is in particular a function of all random variables. The result applies to your case. $\endgroup$
    – Ibrahim
    Commented Apr 17 at 16:31

You must log in to answer this question.

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