4
$\begingroup$

Note: I divide this question to two separated question not to be duplicate version.

I am looking for tail bounds (preferably exponential) for the sum of dependent and bounded random variables.

Consider $K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}W_{jc}$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ are i.i.d. random variables $\operatorname{Bernoulli}(0.5)$. How can I obtain an exponential bound over $Pr[K_{ij} \geq \epsilon] \leq \exp(?)$ where $\epsilon$ is a positive value.

Answer: $K_{ij}$ can be considered as the multiplication of two independent Binomial random variables, i.e., $K_{ij}=\left(\sum_{r=1}^N W_{ir}\right)\left(\sum_{c=1}^N W_{jc}\right)$, then the moment generating function can be evaluated and then by using the Chernoff we can have a tail bound for $K_{ij}$.

Thanks a lot in advance.

  • 0
    Consi$d$er posting this question in m$a$th.SE TOO. This question has a strong content in theoretical pro$b$ability. You may fin$d$ someone there th$a$t can answe$r$ it :)2011-06-03

0 Answers 0