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

Question

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.

Answer 1

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.

Answer 2

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.