MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
$=(\sum_{r=1}^N W_r )^2$ – Ori Gurel-Gurevich Jun 2 '11 at 21:07
Hence $K=(S-E(S))^2$ where $S$ is Binomial$(N,1/2)$? Standard Cramer exponential inequalities work well in this context. – Did Jun 2 '11 at 21:08
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. – Ori Gurel-Gurevich Jun 2 '11 at 21:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.