Hi everyone,
Note: This question is a general case and edited version of my previous question ``How to obtain tail bounds for a sum of dependent and bounded random variables?''.
I am looking for tail bounds (preferably exponential) for a linear combination of dependent and bounded random variables.
consider $$K_{ij}=\sum_{r=1}^N\sum_{c=1}^N W_{ir}C_{rc}W_{jc}$$ where $i \neq j$, $W\in \{+1, -1\}$ and $W$ follows $\operatorname{Bernoulli}(0.5)$, and $C=\operatorname{Toeplitz}(1, \rho, \rho^2, \ldots, \rho^{N-1})$, $0 \leq \rho < 1$.
I will be to happy if you give me any pointer to how I can evaluate the moment generating function of $K_{ij}$ to have bound for $Pr\{K_{ij} \geq \epsilon\}\leq \min_s\exp(-s\epsilon)E[\exp(K_{ij}s)]$ based on chernoff bound.
For a hint I put the following case, that is in fact a special case of the above one. 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)$.
(Answer: As it is noted in Ori's comment, it 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.
