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.



Does $Mv$ converge to i.i.d in some sense?
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.


