1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ $=(\sum_{r=1}^N W_r )^2$ $\endgroup$ Jun 2, 2011 at 21:07
  • $\begingroup$ Hence $K=(S-E(S))^2$ where $S$ is Binomial$(N,1/2)$? Standard Cramer exponential inequalities work well in this context. $\endgroup$
    – Did
    Jun 2, 2011 at 21:08
  • 1
    $\begingroup$ Frazad, it is customary to add a note when you edit a question in such a way that makes the answers/comments irrelevant. To the point - what is $K$ now? Each $K_{i,j}$ is still a product of 2 independent RVs. $\endgroup$ Jun 2, 2011 at 21:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.