Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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 at 8:44
    
@UwF Yes they are all i.i.d. –  octonots Mar 30 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 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 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 at 9:07

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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 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 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 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 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 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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