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
    Consider posting this question in math.SE TOO. This question has a strong content in theoretical probability. You may find someone there that can answer it :)2011-06-03

0 Answers 0