I have two binary vectors $x$, and $y$, each with $n$ elements; Each element of $x$ and $y$ belongs to {-1, 1}, and is drawn from uniform random distribution.
How would I compute the probability of $x \cdot y == k$ and $\sum x == a$ and $\sum y == b$? where $k$, $a$, and $b$ are all intergers ranging from $-n$ to $n$.
I am able to compute the probability of $x \cdot y == k$ from combinatorial analysis, assuming (1) $-n \le k \le n$ and (2) $k \text{ mod } 2 == n \text{ mod } 2$, then $P(x \cdot y == k) = $ $n \choose {(n+k)/2}$ $ 2^{-n}$.
From here, I tried to derive the probability for $x \cdot y == k$ and $\sum x == a$ and $\sum y == b$, but I was stuck due to coupled relations between $x \cdot y$ and $\sum x$ and $\sum y$.
Let's put $$ \left\{ \matrix{ {\bf u} = \left( {1,1, \cdots ,1} \right)^T \quad {\bf u}^T {\bf u} = n \hfill \cr {\bf z} = {{{\bf x} + {\bf u}} \over 2}\quad {\bf w} = {{{\bf y} + {\bf u}} \over 2} \hfill \cr} \right. $$ so that $\bf z , \bf w$ are actual binary vectors.
Then $$ \eqalign{ & S_z = {\bf u}^T {\bf z} = {1 \over 2}S_x + {n \over 2}\quad S_w = {1 \over 2}S_y + {n \over 2} \cr & S_{zw} = {\bf z} \cdot {\bf w} = {\bf z}^T {\bf w} = {1 \over 4}\left( {{\bf x}^T + {\bf u}^T } \right)\left( {{\bf y} + {\bf u}} \right) = \cr & = {1 \over 4}\left( {{\bf x}^T {\bf y} + {\bf x}^T {\bf u} + {\bf u}^T {\bf y} + {\bf u}^T {\bf u}} \right) = \cr & = {1 \over 4}\left( {{\bf x}^T {\bf y} + S_x + S_y + n} \right) \cr & S_{zw} = {\bf z}^T {\bf w} = {\rm N}{\rm .}\,{\rm of}\,{\rm coincident}\,{\rm ones} \cr} $$ where $S_z, S_w$ are the respective number of ones and are integers.
So given two binary strings, with $S_z$ and $S_w$ ones, the number of strings with $S_{zw}$ coincident ones is readily computed.
We can rearrange $\bf z$ as to have all the $S_z$ ones on the same side (e.g. at the lower indices) and then consider the combinations of $\bf w$'s with a number $0 \le S_{zw} \le S_w$ of coincident ones.
There are totally $$\binom{n}{S_w}$$ different $\bf w$'s with $S_w$ ones.
Of these, those which have $S_{zw}$ ones in the first $S_z$ places and the remaining $n-S_{zw}$ in the last $n-S_z$ places are $$ N(S_{zw} \;\left| {\,n,S_z ,S_w } \right.) = \left( \matrix{ S_z \cr S_{zw} \cr} \right) \left( \matrix{ n - S_z \cr S_w - S_{zw} \cr} \right) $$ and the probability will be $$ p(S_{zw} \;\left| {\,n,S_z ,S_w } \right.) = {{\left( \matrix{ S_z \cr S_{zw} \cr} \right) \left( \matrix{ n - S_z \cr S_w - S_{zw} \cr} \right)} \over {\left( \matrix{ n \cr S_w \cr} \right)}} $$ wihich is a Hypergeometric distribution