Probability two products are equal I am interested in the following simple looking problem on which I am stuck.  Let $M$ be a fixed $m$ by $n$ matrix with $\pm1$ elements. Let $x$ and $y$  be two independently sampled  random $n$-dimensional vectors whose elements are chosen i.u.d. from $\{-1,1\}$.

Assuming that $m<n$ and both $m$ and $n$ are large, can we give a good
  estimate or bounds for $P(Mx = My)$?

Clearly $P(Mx= My) \geq P(x=y) = 2^{-n}$. 
Both $Mx$ and $My$ have elements which are distributed as a simple symmetric random walk and have covariance matrix $MM^T$. 
It feels like $\det(MM^T)$ should be part of any solution but this is just a guess and it doesn't work directly. I also attempted to solve the problem by relating the distributions of $Mx$ and $My$ to multivariate Gaussians but this didn't work out. 
Added Jan 5 2016
To narrow the question a little, let us assume that rank$(M) = m$.
Added Jan 8 2016
Is the question more tractable if all the rows of $M$ are orthogonal? 
 A: We note that the brute force way to determine the exact answer involves $O(m^2 2^n)$ operations, where you exhaustively evaluate and tabulate the results of $Mv$ for all $v \in \{-1, 1\}^n$, and you sum the squares of the counts. This answer improves upon the brute force answer by providing an intuitive elementary lower bound that can be quickly computed. 
As a preliminary observation, for fixed integer $n$ and vector $v$, we count the number of ways in which of $v^t x = v^t y$ where $v, x, y \in \{-1,1\}^n$. From elementary combinatorics, This count is $$ \sum_{i = 0}^{n} {n \choose i}^2$$, where $i$ ranges over the total counts of entries in which $x$ (and hence $y$) differs from fixed $v$.
Now we tackle the matrix case. Let $M$ be given. Let the column indices of M be partitioned into $J$ non-empty equivalence classes $K_1, ... K_J$ whereby two columns indices are in the same equivalence class iff they are +/-1 multiples of each other. In our notation, the $K_j$ are disjoint subsets of $\{1, ... n\}$, and $\displaystyle \sum_{j=1}^J |K_j| = n$. Denote each $M_j$ as the submatrix of $M$ restricted to the columns $K_j$, and denote the subvector of $x$ and $y$ restricted to columns in $K_j$ as $x_j$ and $y_j$. To result in $Mx = My$, it suffices that $M_j x_j = M_j y_j$ for all $j \in 1 \ldots J$. Because the criterion is not necessary, the subsequent bound we provide will not be tight. We proceed by manually counting, for each $j$, the number of times that $M_j x_j = M_j y_j$ holds for $x_j, y_j \in \{-1, 1\}^{|K_j|}$. Using the preliminary observation, this is $$ \sum_{i=0}^{|K_j|} {|K_j| \choose i}^2$$
The above provides the number of ways by which $M_j x_j = M_j y_j$ for a single $j$.  Across all columns, the total count of ways to specify $((x_1, \ldots x_J), (y_1, \ldots, y_J))$ is $$ \prod_{j=1}^J \sum_{i=0}^{|K_j|} {|K_j| \choose i}^2 $$.  Expressed as a probability, there are $2^{2n}$ ways for $x$ and $y$ to take values. Thus, we arrive at the lower bound
$$
P(Mx=My)\ge 2^{-2n} \prod_{j=1}^J \sum_{i=0}^{|K_j|} {|K_j| \choose i}^2 
$$
Given the equivalence classes, the running time of the above equation is $O(m+n)$. The time needed to identify the equivalence classes for the columns of $M$ is $O(mn \log(mn))$.
Examples:
Note that the bound is exact in some notable cases. When $M$ is square and has rank $n$, we have $J = n$, and the bound evaluates to:
$$2^{-2n} \prod_{j=1}^J \sum_{i=0}^{|K_j|} {|K_j| \choose i}^2 = 2^{-2n }\prod_{j=1}^{n} (1+1) = 2^{-n} $$.
When $M$ has rank 1, we have $J=1$ and the computation reduces to the preliminary observation
$$2^{-2n} \prod_{j=1}^J \sum_{i=0}^{|K_j|} {|K_j| \choose i}^2 = 2^{-2n }\sum_{i=0}^n {n \choose i}^2$$.
A: Not a complete answer, too long as a comment: Firstly, the difference of $x-y$ has entries in $\{-2,0,2\}$ but we can consider vectors over $\{-c,0,c\}$ for any $c>0$ by scaling, since all we care about is whether they belong to the nullspace.
What is the rank distribution of $M$? If $m\ll n$ it is likely to be $m$ or very nearly $M$. If we impose the uniform probability on the space of $m\times n$ $\{\pm 1\}$ matrices, and let $A$ have rows $a_1,\ldots,a_m$ ($M$ can be taken as a realization of $A$) we can argue recursively and find
$$
Pr[rank([a_1|\cdots|a_m])^{T}=k],\quad 1\leq k\leq m.
$$
Essentially think of it as a discrete Markov chain where $X_v=rank([a_1|\cdots|a_v])$ and given $X_v=k,$ we have $X_{v+1}=k+1$ with probability $2^{n-k}/2^n=2^{-k}$ and $X_{v+1}=k$ otherwise. The relative size of the orthogonal complement of the $k-$dimensional subspace spanned by $a_1,\ldots,a_v$ determine this probability distribution for $v=m.$
From here, the question becomes, for a fixed rank $k$ what is the probability that a $\{-1,0,1\}$ vector lies in the subspace determined by that rank. If you could stay in $\{-1,1\}$ (equivalently over $F_2$) the number of subspaces of a given rank is also known. Here, your  given $\{-1,0,1\}$  vector can actually be taken to be on the unit sphere to answer this question since if the Hamming weight of the vector is $w,$ we can normalize to a $\{-1/\sqrt{w},0,1/\sqrt{w}\}$-vector. Such a unit vector, if it was drawn at random from the set of all unit vectors would have an essentially gaussian  distribution of Hamming weight, with standard deviation $\sqrt{n}.$ 
I believe that concentration of measure would then imply that for $m\approx \log n$ with a fixed nonzero probability all unit vectors would be in a subspace of dimension $\log n$ and you'd only need to scale by the total number of subspaces of that dimension.
There are experts here who can answer this properly, I am sure.
A: I will consider $n$ even for simplicity, and try to argue for an approximate answer. The difference $z=x-y$ has independent identically distributed entries $z_i$ in $\{-2,0,2\}$ with distribution $Pr[z=-2]=Pr[z=+2]=1/4$ and $Pr[z=0]=1/2.$ Consider an arbitrary vector $a$ in $\{\pm 1\}.$ Then the sum $$\langle a, z\rangle=\sum_{i=1}^n a_i z_i$$ has terms $u_i=a_i z_i$ with the same distribution. Thus $\langle a, z\rangle$ has a multinomial distribution. Let $Z$ be the random variable denoting the number of $u_i=0.$ Then
$$
Pr[\langle a,z\rangle=0]=\sum_{0\leq Z\leq n:Z\equiv n~(mod~2)} 2^{-Z} \binom{n}{Z} Pr[number(u_i=+1)=(n-Z)/2],
$$
since the +1 and -1 must balance. From here we get
$$
Pr[\langle a,z\rangle=0]=\sum_{0\leq Z\leq n:Z\equiv n~(mod~2)} 2^{-n} \binom{n}{Z} \frac{\binom{n-Z}{(n-Z)/2}}{2^{n-Z}},
$$
which simplifies to
$$
Pr[\langle a,z\rangle=0]=\sum_{0\leq Z\leq n:Z\equiv n~(mod~2)}   \frac{\binom{n}{Z} \binom{n-Z}{(n-Z)/2}}{2^{2n-Z}}=\frac{\Gamma(\frac{1}{2}+n)}{\sqrt{\pi}\Gamma(n+1)}\stackrel{\triangle}{=} q_n
$$
and this is asymptotic to $1/\sqrt{\pi n}$ as $n$ gets large.i
The answer would be $$Pr[\langle a_i,z\rangle=0],\quad i=1,\ldots,m$$which would be $q_n^m$ if independence could be assumed.
Edit: Under the assumption that the rows $a_i$ are orthogonal, consider two such rows $a,a'$ and let $W$ be the number of coordinates where $a$ and $a'$ have matching entries (both -1 or both +1). Since $a,a'$ are orthogonal, $W=n/2$ and $n$ must be even under the orthogonality assumption. Let $I_W\subset\{1,\ldots,n\}$ be the support of the coordinates where equality is achieved. 
Since $a$ and $a'$ are orthogonal we can (by multiplying coordinates of $a$ and $a'$ by $-1$ if necessary) assume $a$ to be the all 1 vector and $a'$ to have (say) its first $n/2$ coordinates +1 and the rest -1. 
Given $a$ is orthogonal to $z$, it is clear that if the sum of the coordinates of $z$ on the first $n/2$ components is $S$, it is $-S$ on the second $n/2$ components. Multiplying componentwise by entries of $a'$ this would give $2S$. Thus, for
both $a$ and $a'$ to be orthogonal to $z$ the coordinates of $z$, $S=0$ is needed. This is a similar sum as before, but on $n/2$ coordinates, so
$$Pr[\langle a,z\rangle=0]\times Pr[\langle a',z\rangle=0~|~\langle a,z\rangle=0]=q_n q_{n/2}$$
Proceeding by induction with the same kind of coordinate partitioning, and assuming $2^{m-1}$ divides $n$, one should get
$$Pr[\langle a_1,z\rangle=0]\times Pr[\langle a_2,z\rangle=0~|~\langle a,z\rangle=0] \times \cdots \times \quad \quad \quad $$ $$ Pr[\langle a_m,z\rangle=0~|~\langle a_1,z\rangle=0, \ldots, \langle a_{m-1},z\rangle=0]=q_n q_{n/2} q_{n/4} \cdots q_{n/2^{m-1}}$$
