<p>Are there results/techniques pertaining to the analysis of squares of random matrices ?</p>

<p>More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with equal probability. Now if we want to analyze for any $u,v \in \{-1,1\}^n$, we can make a case for concentration of the value of $u^TAv$ using chernoff bound arguements. However suppose now we want to analyze the value of $u^TA^2v$. This time due to a lot of dependencies among the variables a chernoff type arguement becomes difficult or at least I cannot see it straightaway. Could someone point me to an analysis for this scenario ?  </p>

CC BY-SA 3.0
2013-06-15T04:24:13.610Z
While this is not an answer, it seems that powers of such an A will become "more and more Gaussian": maybe this might yield a back of the envelope estimate for the behavior ?
Suresh Venkat
CC BY-SA 3.0
2013-06-15T17:11:08.843Z
Yes, thats what my guess is and I have been trying to formalize it exactly but havent got much progress yet .. was just wondering if there is already work on it
NAg
CC BY-SA 3.0
2013-06-15T17:30:27.433Z
There is the notion of subgaussian tails that is sufficient to prove a number of tail bounds on variables of this kind. It might be that you can show that the variables in A^2 have this property. See for example this paper by Matousek: http://dl.acm.org/citation.cfm?id=1400129
Suresh Venkat
CC BY-SA 3.0
2013-06-15T22:50:38.637Z
Thanks a lot for the links. Yes we would get that each entry in A^2 has a sub-gaussian tail, however I am not yet sure as to how to avoid the problem of dependence between these entries when we take their sum when computing uA^2v. The paper referred above does give a sub-gaussian behaviour result for sums of independent sub-gaussian variables. I am not sure how to avoid the dependence issues that arise here.
NAg
CC BY-SA 3.0
2013-06-16T06:12:10.110Z
again, I'm just wildly speculating, but maybe the dependency can be controlled and you can use a "weak dependence" chernoff bound (of which there are a few flavors)
Suresh Venkat
CC BY-SA 3.0
2013-06-16T06:14:22.530Z
Could you point me to a few of these ?
NAg
CC BY-SA 3.0
2013-06-16T08:12:12.857Z
I'd start with the book by Dubhashi and Panconesi and go from there. http://www.amazon.com/books/dp/1107606608
Suresh Venkat
CC BY-SA 3.0
2017-07-27T10:35:31.250Z
Did you try using the power Markov method of writing $E(u^TA^2v)^p$ as a sum of monomials and bounding each of them with their Gaussian analog? If you can bound the expected power, Markov's inequality will give you the tail bound.
Thomas Ahle
<pr.probability><randomness><matrices><chernoff-bound>
Squares of random binary matrices
NAg
# Squares of random binary matrices

(Asked by: username_0 on 2013-06-15)

Are there results/techniques pertaining to the analysis of squares of random matrices ?

More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with equal probability. Now if we want to analyze for any $u,v \in \{-1,1\}^n$, we can make a case for concentration of the value of $u^TAv$ using chernoff bound arguements. However suppose now we want to analyze the value of $u^TA^2v$. This time due to a lot of dependencies among the variables a chernoff type arguement becomes difficult or at least I cannot see it straightaway. Could someone point me to an analysis for this scenario ?

**Tags:** pr.probability, randomness, matrices, chernoff-bound

> **Comments:**
> **username_1**: While this is not an answer, it seems that powers of such an A will become "more and more Gaussian": maybe this might yield a back of the envelope estimate for the behavior ?  
> **username_0**: Yes, thats what my guess is and I have been trying to formalize it exactly but havent got much progress yet .. was just wondering if there is already work on it  
> **username_1**: There is the notion of subgaussian tails that is sufficient to prove a number of tail bounds on variables of this kind. It might be that you can show that the variables in A^2 have this property. See for example this paper by Matousek: http://dl.acm.org/citation.cfm?id=1400129  
> **username_0**: Thanks a lot for the links. Yes we would get that each entry in A^2 has a sub-gaussian tail, however I am not yet sure as to how to avoid the problem of dependence between these entries when we take their sum when computing uA^2v. The paper referred above does give a sub-gaussian behaviour result for sums of independent sub-gaussian variables. I am not sure how to avoid the dependence issues that arise here.  
> **username_1**: again, I'm just wildly speculating, but maybe the dependency can be controlled and you can use a "weak dependence" chernoff bound (of which there are a few flavors)  
> **username_0**: Could you point me to a few of these ?  
> **username_1**: I'd start with the book by Dubhashi and Panconesi and go from there. http://www.amazon.com/books/dp/1107606608  
> **username_2**: Did you try using the power Markov method of writing $E(u^TA^2v)^p$ as a sum of monomials and bounding each of them with their Gaussian analog? If you can bound the expected power, Markov's inequality will give you the tail bound.  

---

## 0 answers

