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 ans $s \geq 0$.

For a hint you can look at my another question entitled as ``How to obtain tail bounds for a sum of dependent and bounded random variables?'' which is a special case of this problem where $C_{rc}=1, 1 \leq c \leq N, 1 \leq r \leq N$. Thanks a lot in advance.


This is Hanson Wright. Let $\sigma=W_i$ and $\sigma' = W_j$ then by Jelani's Lecture Notes:

$$ \Pr[|\sigma^T C \sigma'|>\lambda] = O(\exp(-c\lambda^2/\|C\|_F^2) + \exp(-c'\lambda/\|C\|^2)). $$

where $c$ and $c'$ are some constants.

Here $\|C\|_F^2=N\sum_{i=0}^{N=1} \rho^{2i}=N\frac{p^{2N}-1}{\rho^2-1}$ is the Frobenius norm, and $\|C\|=\sum_{i=0}^{N-1}\rho_i=\frac{\rho^N-1}{\rho-1}$ is the spectral norm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.