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? 



Probability two products are equal
I came across this problem a few days ago, and must say it was a lot of fun to think about. Thank you!


The following is, I believe, a quite complete solution of the problem for a "typical", general $M$, making no assumptions about the relative size of $n$ and $m$ (even $m>n$ is allowed), or about the rank of $M$. 


Like kodlu in his/her answer from Jan 5, I will start with slightly re-formulating the question: 


We want to find the probability $P(Ms=0)$, where the $n$ components of the vector $s=\frac{x-y}2$ are i.i.d. random variables which have values $1$ or $-1$ with probability $\frac1 4$ and value $0$ with probability $\frac1 2$. $P(Ms=0)$ can then be expressed as the expectation value of a product of Kronecker deltas for the $m$ components of $Ms$:
$$
P(Ms=0) = \left\langle \prod\_{i=1}^m \delta\_{0,\sum\_{j=1}^nM\_{ij}s\_j} \right\rangle\_s \ ,
\hspace{2cm} (1)
$$
where $\left\langle \cdots \right\rangle\_s$ indicates the average over all $s\_j$. 


For any integer $t$ with $|t|\leq n$ we can substitute $\delta\_{0,t} = \frac1{n+1} \sum\_{r=0}^n \omega^{rt}$ with the primitive $(n+1)^{\rm th}$ root of unity $\omega = {\rm e}^\frac{2\pi{\rm i}}{n+1}$ ("discrete Fourier transform"), so that $(1)$ becomes
$$
P(Ms=0) = \left\langle \prod\_{i=1}^m \left( \frac1{n+1} \sum\_{r\_i=0}^n \omega^{r\_i\sum\_{j=1}^n M\_{ij}s\_j} \right) \right\rangle\_s
= \left\langle \prod\_{i=1}^m \prod\_{j=1}^n \omega^{M\_{ij} r\_i s\_j} \right\rangle\_{r,s} \ ,
\hspace{2cm} (2)
$$
where in the second step the $r\_i$ have been re-interpreted as i.u.d. random variables with values in $\{0,...,n\}$, so that $\left\langle \cdots \right\rangle\_{r\_i} = \frac1{n+1} \sum\_{r\_i=0}^n (\cdots)$, and $\left\langle \cdots \right\rangle\_{r,s}$ indicates the simultaneous average over all $r\_i$ and $s\_j$. 


Now, obviously $P(Ms=0)$ has not the same value for all $(-1,1)$-matrices $M$ of a given size $m \times n$. As an example, if $M$ has rank $1$ (i.e., each of its column vectors is equal to either $v$ or $-v$, with some fixed $(-1,1)$-vector $v$) then the problem is equivalent to the case $m=1$, and the result is 
$$
P(Ms=0) = 2^{-n} \sum\_{l=0}^{\lfloor n/2 \rfloor} 2^{-2l} \begin{pmatrix} {n} \\ {2l} \end{pmatrix} \begin{pmatrix} {2l} \\ {l} \end{pmatrix} \ ,
\hspace{2cm} (3)
$$ 
whereas usually it will be much smaller (for instance, if $M$ has rank $n$ then trivially $P(Ms=0) = 2^{-n}$). Thus $(2)$ cannot be evaluated without further assumptions on $M$. Alternatively, we can try to calculate a "typical" value of $(2)$, assuming that $M$ itself is a random sample out of a distribution of matrices with i.i.d. matrix elements $M\_{ij}$, and averaging $P(Ms=0)$ over this distribution. This approach leads to
$$
\Big\langle P(Ms=0) \Big\rangle\_M
= \left\langle \prod\_{j=1}^n \prod\_{i=1}^m \left\langle \omega^{M\_{ij} r\_i s\_j} \right\rangle\_M \right\rangle\_{r,s}
= \left\langle \prod\_{j=1}^n \prod\_{i=1}^m \frac{ \omega^{r\_i s\_j} + \omega^{-r\_i s\_j} }2 \right\rangle\_{r,s} \ .
\hspace{1cm} (4)
$$
Note that we have also changed the order of the product operations over $i$ and $j$ here. Now the average over the $s\_j$ can be performed easily: for each $j$, 
$$
\left\langle \prod\_{i=1}^m \frac{ \omega^{r\_i s\_j} + \omega^{-r\_i s\_j} }2 \right\rangle\_{s\_j}
= \frac1 2 \left( 1 + \prod\_{i=1}^m \frac{\omega^{r\_i} + \omega^{-r\_i}}2 \right) \ ,
$$
which is independent of $j$, so that 
$$
\Big\langle P(Ms=0) \Big\rangle\_M
= 2^{-n} \left\langle \left( 1 + \prod\_{i=1}^m \frac{\omega^{r\_i} + \omega^{-r\_i}}2 \right)^n \right\rangle\_{r} \ .
\hspace{2cm} (5)
$$
To evaluate the right hand side of $(5)$ we expand the $n^{\rm th}$ power, 
$$
\Big\langle P(Ms=0) \Big\rangle\_M
= 2^{-n} \sum\_{k=0}^n \begin{pmatrix} {n} \\ {k} \end{pmatrix} 2^{-km} \prod\_{i=1}^m \left\langle \Big( \omega^{r\_i} + \omega^{-r\_i} \Big)^k \right\rangle\_{r} \ ,
\hspace{2cm} (6)
$$
and likewise the $k^{\rm th}$ power in $(6)$: 
$$
\left\langle \Big( \omega^{r\_i} + \omega^{-r\_i} \Big)^k \right\rangle\_{r}
= \sum\_{l=0}^k \begin{pmatrix} {k} \\ {l} \end{pmatrix} \left\langle \omega^{(k-2l)r\_i} \right\rangle\_{r}
= \begin{cases} \begin{pmatrix} {k} \\ {k/2} \end{pmatrix} , \ k\ {\rm even} \\ \quad \ 0 \ , \quad k\ {\rm odd} \end{cases}
\ ,
\hspace{2cm} (7)
$$
where $\left\langle \omega^{(k-2l)r\_i} \right\rangle\_{r} = \delta\_{k,2l}$ has been used. Inserting $(7)$ into $(6)$ then leads to 
$$
\Big\langle P(Ms=0) \Big\rangle\_M
= 2^{-n} \sum\_{l=0}^{\lfloor n/2 \rfloor} 2^{-2lm} \begin{pmatrix} {n} \\ {2l} \end{pmatrix} \begin{pmatrix} {2l} \\ {l} \end{pmatrix} ^m \ .
\hspace{2cm} (8)
$$
Note the close similarity to Eq. $(3)$. 
The $l=0$ term in $(8)$ yields $\big\langle P(Ms=0) \big\rangle\_M = 2^{-n} $, which is the lower bound mentioned in the question. For large $n$, $m$, and $l$, Stirling's approximation gives to leading order 
$$
2^{-2lm} \begin{pmatrix} {n} \\ {2l} \end{pmatrix} \begin{pmatrix} {2l} \\ {l} \end{pmatrix} ^m 
\sim \sqrt{\frac{n}{4\pi l(n-2l)}} \ {\rm e}^{n I(\frac{2l}n)} (\pi l)^{-\frac m2}
\ ,
\hspace{2cm} (9)
$$
where $I(p)$ denotes the "information entropy" of a 2-state system with probabilities $p$ and $1-p$: 
$$
I(p) = - p \ln(p) - (1-p) \ln(1-p) \ .
\hspace{2cm} (10)
$$
Note that the divergence of the right hand side of $(9)$ for $l \to 0$ is an artefact due to Stirling's approximation; the original expression on the left hand side has a $l \to 0$ limit equal to $1$. 
To find the dominant term(s) in the sum of $(8)$, we look for the maximum of the exponential part of $(9)$ as a function of $l$, disregarding for the moment the square root. 
That is, setting $p = \frac{2l}n$ and $q = \frac{m}n$, we look for the maximum of 
$$
{\rm e}^{n \left( I(p) - \frac q 2 \ln\frac{\pi p n}2 \right)}
\hspace{2cm} (11)
$$
as a function of $p \in ]0,1]$. The sum in $(8)$ is either dominated (for large enough $q$) by the $l=0$ term $1$, or otherwise by a term with $l \approx \frac{pn}2$, where $p$ is a solution of the equation 
$$
\frac q{2p} = I'(p) = \ln\frac{1-p}p \ .
\hspace{2cm} (12)
$$
If $q$ is larger than about $0.56$, $(11)$ has no solution $p \in ]0,1]$. For $q$ smaller than about $0.56$ there are two solutions, the smaller of the two corresponding to a local minimum of ${\rm e}^{n \left( I(p) - \frac q 2 \ln\frac{\pi p n}2 \right)}$ and the larger one to a local maximum. For large $n$, this local maximum dominates the sum in $(8)$ if and only if $I(p) - \frac q 2 \ln\frac{\pi p n}2 > 0$ for this $p$ value. For large $n$, the maximal $q$ that meets this criterion decreases logarithmically with increasing $n$, so in that case we may assume $\frac q{2p} \ll 1$ and thus obtain $p \approx \frac1 2$ from $(12)$. Inserting this back into the exponential expression $(11)$ yields an estimate of its maximum for large $n$, $m$, and $l$
$$
\max\_{p \gg \frac1n} \left\{ {\rm e}^{n \left( I(p) - \frac q 2 \ln\frac{\pi p n}2 \right)} \right\} 
\approx {\rm e}^{n \left( \ln2 - \frac q 2 \ln\frac{\pi n}4 \right)} \ .
\hspace{2cm} (13)
$$
Finally, we can combine this with $(8)$, $(9)$ and obtain, to leading order for large $n$, 
$$
2^{n} \Big\langle P(Ms=0) \Big\rangle\_M
\approx 1 + \sqrt{\frac{2}{\pi n}} \ {\rm e}^{n \left( \ln2 - \frac q 2 \ln\frac{\pi n}4 \right)} 
= 1 + 2^{n-\frac1 2} \left( \frac{\pi n}4 \right)^{-\frac{qn+1} 2}
\ .
\hspace{2cm} (14)
$$
As long as the exponent in $(13)$ is negative, i.e. $q > \frac{\ln4}{\ln\frac{\pi n}4}$ (or $m > n \frac{\ln4}{\ln\frac{\pi n}4} $), the first term $=1$ in $(14)$ dominates, which means that only the trivial solution $s=0$ of $Ms=0$ has nonnegligible probability. Otherwise, the second term dominates, quantifying how the number of solutions increases when $m$ becomes small enough compared to $n$. 


