Probability distribution for a matrix vector product

Consider a fixed (non-random) $2$ by $n$ matrix $M$ whose elements are chosen from $\{-1,1\}$. Assume $n$ is even. I am trying work out what the probability mass function of $Mx$ is when $x$ is a random vector with elements chosen independently and uniformly at random from $\{-1,1\}$.

Each of the two elements of $y = Mx$ is distributed as a simple symmetric random walk. This is true no matter what $M$ is. We can therefore give the marginal probability distribution explicitly as:

$$P(y_i = k) = {n \choose (n+k)/2}\frac{1}{2^n},\;\; k \in \{-n, -n+2,\dots, n-2, n\}$$

However these marginal probabilities don't tell the whole story as there will typically be some dependence between the two elements of $y$ which depends on the values in $M$.

Is it possible to write an explicit formulation for the probability mass function of $y$?

I think we can set the first row of $M$ to be all $1$s without loss of generality which may simplify the question.

• I take it we may not assume that the elements of $M$ are chosen (like $x$) independently and uniformly from $\{-1, 1\}$? – Brian Tung Dec 30 '15 at 7:07
• @BrianTung Yes, you are right. $M$ is fixed and not-random. I expect that the probability mass function of $y$ will depend on $M$ somehow. – dorothy Dec 30 '15 at 7:26

1 Answer

I try to calculate the conditional pmf $\Pr\{Y_2 = y_2|Y_1 = y_1\}$. You are given that

$$Y_i = \sum_{j=1}^n m_{ij}X_j, i = 1, 2$$ A trivial case is that when $m_{1j}=m_{2j} ~~\forall j \in \{1, 2, \ldots, n\}$, then $Y_1 = Y_2$ and you do not have a joint pmf in that case. Suppose not, let $$Y_2 = Y_1 + D$$ Then $$D = Y_2 - Y_1 = \sum_{j=1}^n (m_{2j} - m_{1j})X_j$$ Again if $m_{1j} = m_{2j} ~~ \exists j$, that particular summand $(m_{2j} - m_{1j})X_j$ vanish and we are not interested in it. If not, we have $m_{1j} = -m_{2j}$ and thus $$\Pr\{(m_{2j} - m_{1j})X_j = -2\} = \Pr\{(m_{2j} - m_{1j})X_j = 2\} = \frac {1} {2}$$ which means that the unconditional distribution of $D$ again is a location-scale Binomial. Let $$\mathcal{C} = \{(m_{1j}, m_{2j}): m_{1j} = -m_{2j}, j = 1, 2, \ldots, n\}$$ and $$c = \frac {1} {2} \sum_{j=1}^n |m_{2j} - m_{1j}|$$ be the number of elements in $\mathcal{C}$. Then $$\Pr\{D = d\} = \binom {c} {\frac {2c + d} {4}} \frac {1} {2^c}, d = -2c, -2c+4, \ldots, 2c$$ But this is still not the interesting case as we want to know the conditional distribution of $Y_2|Y_1 = y_1$, which has the same distribution of $y_1 + D|Y_1 = y_1$ - i.e. we are interested in the conditional distribution $D|Y_1 = y_1$. Note that given $Y_1 = y_1$, the number of $m_{1j}X_j$ equals to $1$ is given by $$\frac {n + y_1} {2}$$ as indicated in the binomial coefficient, and the number of of $m_{1j}X_j$ equals to $-1$ is given by $$n - \frac {n + y_1} {2} = \frac {n - y_1} {2}$$ Let $R$ be the number of $m_{1j}X_j$ equals to $1$ and $(m_{1j}, m_{2j})\in \mathcal{C}$, then $R$ follows a hypergeometric distribution, with pmf $$\Pr\{R = r|Y_1 = y_1\} = \frac {\displaystyle \binom {\frac {n + y_1} {2}} {r} \binom {\frac {n - y_1} {2}} {c-r}} {\displaystyle \binom {n} {c} }$$ Here the support of $R$ is given by the two constraints \begin{align*} & 0 \leq r \leq \frac {n + y_1} {2} \text{ and } 0 \leq c - r \leq \frac {n - y_1} {2}\\ \Rightarrow & \max\left\{0, c-\frac {n - y_1} {2} \right\}\leq r \leq \min\left\{\frac {n + y_1} {2}, c\right\} \end{align*} Finally note that $$D = -2R + 2(c-R) = 2c - 4R$$ Therefore the conditional pmf of $D|Y_1 = y_1$ is \begin{align*} \Pr\{D = d|Y_1 = y_1\} & = \Pr\{2c - 4R = d|Y_1 = y_1\} \\ & = \Pr\left\{R = \frac {2c - d} {4}\bigg|Y_1 = y_1\right\} \\ & = \frac {\displaystyle \binom {\frac {n + y_1} {2}} {\frac {2c - d} {4}} \binom {\frac {n - y_1} {2}} {\frac {2c + d} {4}}} {\displaystyle \binom {n} {c} }, d = 2\max\{-n-y_1+c, -c\}, \ldots, 2\min\{c, n-y_1-c\} \end{align*} Then you can express the joint pmf as \begin{align*} \Pr\{Y_1 = y_1, Y_2 = y_2\} & = \Pr\{Y_1+D = y_2|Y_1 = y_1\}\Pr\{Y_1 = y_1\} \\ & = \Pr\{D = y_2 - y_1|Y_1 = y_1\}\Pr\{Y_1 = y_1\} \end{align*} Sorry this post is long and may contain careless typos/mistakes. Please help to check if this is correct.

• Thank you for this. I haven't worked through all the details yet. Do you think the approach would stretch to $3$ by $n$ matrices too? – dorothy Dec 30 '15 at 19:14
• Yesterday when I try to tackle this problem, the main idea I have is try to find out how the given location of $Y_1$ and the distinct number of pairs in $M$ will restrict the support of $Y_2$. I have think of whether the approach can be generalized in higher dimension, but I have no time to do that yet. If the approach is correct for 2 rows, then maybe you can try to extend it: given the location of $Y_1, Y_2$ and some features of $M$, how will that restrict the support of $Y_3$. – BGM Dec 31 '15 at 8:34