# Does $Mv$ converge to i.i.d in some sense?

I am not a professional mathematician so please excuse me if my question is not phrased correctly.

I am interested in the following simple sounding problem.

Consider a random $n$ by $n$ $0$-$1$ matrix $M$ where $M_{i,j} = 1$ with probability $1/2$ and $0$ otherwise. Now choose a single random $0$-$1$ vector $v$ where $v_i=1$ with probability $1/2$. I can write down a precise formula for the probability distribution of $u=Mv$. However, I would like to argue that for large $n$ the distribution of $u_i$ becomes very close (perhaps converges to in some sense) to i.i.d. $Bin(n,1/4)$.

My hand wavy intuition which might also reveal my motivation a bit more is that each $u_i$ is tightly concentrated around its mean (as is the number of $1$s in $v$ and each row of $M$). Under these circumstances knowledge of $u_i$ tells you almost nothing about $v$ and hence almost nothing about other $u_j$. In other words the $u_i$ are in some sense very close to being independent with high probability.

Is there some way in which this can be formalized?

Here is an example of what I would like to do. Say we have a set $S$ of $2^n$ $0$-$1$ vectors chosen i.u.d. and for each we compute the product $Y_i=MS_i$ (I have overloaded the notation as here $S_i$ and $Y_i$ refer to the $i$th vector not the $i$th element within a vector). Let us make the matrix $M$ $m$ by $n$, that is potentially non-square, but still $0$-$1$ and each $M_{i,j}$ is i.u.d. as before. I would like to work out the expected number of distinct $Y_i$ for large $n$ and $m$. The number of rows $m$ will typically be smaller than $n$ but not by too much. I would like to be able to argue as if each element of $Y_i$ were independent to make the math easier. I only care about large $n,m$ approximations.

• Are all the coefficients of $M$ and $v$ independent? Without some information about the joint law of the coefficients it is difficult to say much... – UwF Mar 30 '14 at 8:44
• @UwF Yes they are all i.i.d. – octonots Mar 30 '14 at 8:50
• There are several different questions here; one is "is each of the $u_i$ separately $Bin(n,1/4)$" (yes), another is "are the $u_i$ independent from each other?" (no, not always, I guess), and a third (if I read between the lines) is "does some result such as a LLN/CLT hold as if they were independent?". Maybe you should try and make the last one more explicit: what kind of properties do you need from them? What is your ultimate goal? – Federico Poloni Mar 30 '14 at 8:52
• It might help to note that, conditioned on the number of ones in $v$ (say there are $k$ of them), the $u_i$ are distributed i.i.d. $Bin(k,1/2)$. – usul Mar 30 '14 at 8:57
• @FedericoPoloni It is the third type of question I am interested in as you suggest. I will add a more specific example of how I would like to use this. – octonots Mar 30 '14 at 9:07

If I understood well, you are asking this:

What is the limit distribution as $n$ tends to infinity of $u=Mv$ for $M$ a uniform random $0-1$ matrix of size $n\times n$ and $v$ a uniform random vector of size $n\times 1$ ?

If you fix a coordinate $i$ and you ask for the distribution of $u^n_i$ is easy. $u^n_i\doteq\sum_{j=1}^n M_{i,j}v_j=\sum_{j=1}^n X_j$ where $X_j$ are i.i.d. random variables with $\mathbb{P}(X_j=0)=3/4$ and $\mathbb{P}(X_j=1)=1/4$ (i.e. is the sum of $n$ (1/4, 3/4)-Bernoulli random variables). Then $Z_i^n\doteq \sqrt{n}(u_i^n/n-1/4)$ converges in distribution to $N(0,(3/16)^2)$ as $n$ tends to infinity by the CLT.

About the independency...a simple calculation shows that the correlation between $Z^n_i$ and $Z^n_j$ for $i\neq j$ is $1/3.$ So there is no asymptotic independence even in this case.

• Thank you. However, I am even more confused than I was now. What do we know about the expected number of distinct $Y_i$ in this case? – octonots Apr 2 '14 at 16:35
• This question can be difficult. It is not trivial to prove that as $n$ tends to infinity the matrix $M$ will become non invertible almost surely. So, if you fix a big $n$ and a matrix $M$ of size $n\times n,$ this just says that the probability of obtaining two $Y_i$'s equals is greater that the probability of having two $v_i$'s equals. – user39115 Apr 2 '14 at 17:00
• Your last question is very interesting and I am not able to answer it (I m far from that). – user39115 Apr 2 '14 at 17:08
• The observation about the probability of a matrix being non-invertible does tell you something about the square case but I am not sure what it tells you about the non-square case. – octonots Apr 2 '14 at 17:39
• I cannot answer you precisely, but it is intuitive that the probability increases as the matrix is less square'', and it has a unique minimum at the square one. The extremes cases are easy. – user39115 Apr 2 '14 at 17:50

Unless I miss something or have made a simple mistake, a direct computation shows that $Var(u_i)=3n/16$ and $Cov(u_i,u_j)=n/16$ for $i\ne j$. So $Corr(u_i,u_j)=1/3$ for $i\ne j$ no matter what $n$ is. So there is no asymptotic independence.

Yes, variance tends to zero, so there is concentration.

• Thank you. I added a comment to @user39115's answer explaining my confusion. – octonots Apr 2 '14 at 16:41