Probability distribution for a three row matrix vector product

Question

Consider a fixed (non-random) $3$ 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 three 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 three 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.

Example:

In order to give a concrete worked example, let

$$M = \begin{pmatrix} -1 & 1 & -1 & -1 & 1\\ -1 & 1 & 1 & 1 & 1\\ -1 & -1 & 1 & 1 & 1\\ \end{pmatrix}.$$

In this case the probability mass function is as follows. In each pair the first item is the vector $y$ and the second number is its probability.

[((-5, -1, 1), 0.03125), ((-3, -3, -1), 0.0625), ((-3, 1, -1), 0.03125), ((-3, 1, 3), 0.0625), ((-1, -5, -3), 0.03125), ((-1, -1, -3), 0.0625), ((-1, -1, 1), 0.125), ((-1, 3, 1), 0.0625), ((-1, 3, 5), 0.03125), ((1, -3, -5), 0.03125), ((1, -3, -1), 0.0625), ((1, 1, -1), 0.125), ((1, 1, 3), 0.0625), ((1, 5, 3), 0.03125), ((3, -1, -3), 0.0625), ((3, -1, 1), 0.03125), ((3, 3, 1), 0.0625), ((5, 1, -1), 0.03125)]

This is a follow-up to Probability distribution for a matrix vector product . It seems the first interesting case is in fact $3$ rows not $2$.

Answer 1

The distribution does not change if we multiply all the entries of a single column by $-1,$ nor if we exchange two columns, so we can always bring $M$ into a form that starts with $w_1$ times the column $(1\ 1\ 1)^T$ followed by $w_2$ times the column $(1\ {-1}\ 1)^T$ followed by $w_3$ times $(1\ 1\ {-1})^T$ and ends with $w_4$ times the column $(1\ {-1}\ {-1})^T.$ The numbers $w_i$ are deterministic and known, and their sum is $n.$

$$M=\left(\begin{matrix} 1&1&\ldots&1&1&\ldots&1&1&\ldots&1&1\\ 1&1&\ldots&-1&-1&\ldots&1&1&\ldots&-1&-1\\ 1&1&\ldots&1&1&\ldots&-1&-1&\ldots&-1&-1\\ \end{matrix}\right)$$

Now $y=Mx$ is a linear combination of these four columns with random coefficients $c_1,$ $c_2,$ $c_3$ and $c_4.$

$$Mx=c_1\left(\begin{matrix}1\\1\\1\\ \end{matrix}\right)+c_2\left(\begin{matrix}1\\-1\\1\\ \end{matrix}\right)+c_3\left(\begin{matrix}1\\1\\-1\\ \end{matrix}\right)+c_4\left(\begin{matrix}1\\-1\\-1\\ \end{matrix}\right)=\left(\begin{matrix}c_1+c_2+c_3+c_4\\c_1-c_2+c_3-c_4\\c_1+c_2-c_3-c_4\\ \end{matrix}\right)$$

Here $c_1$ is the sum of the first $w_1$ components of the random vector $x,$ $c_2$ is the sum of the next $w_2$ components, $c_3$ the sum of the next $w_3$ and $c_4$ the sum of the last $w_4.$ The coefficients are independent and the distribution of $c_i$ is the fortune of a gambler after tossing a coin $w_i$ times. The explicit form of that distribution resembles the marginal distribution in your question:

$$P[c_i = j] = {w_i \choose (w_i+j)/2}\frac{1}{2^{w_i}},\;\; j \in \{-w_i, -w_i+2,\dots, w_i-2, w_i\}$$

The distribution $P\left[y=(k\ l\ m)^T\right]$ is then given by

$$P\left[(c_1+c_2+c_3+c_4=k)\wedge(c_1-c_2+c_3-c_4=l)\wedge(c_1+c_2-c_3-c_4=m)\right]$$

These three events are not independent but we can solve the three equations in four unknowns using an integer parameter $t$ (and knowing that $k,l,m$ and $n$ almost surely have the same parity):

$$\eqalign{ c_1&=t\\ c_2&=\frac{k+m}2-t\\ c_3&=\frac{k+l}2-t\\ c_4&=t-\frac{l+m}2\\ }$$

and we can rewrite our probability in terms of the independent $c_i$ as

$$\eqalign{ P\left[y=\left( \begin{matrix}k\\ l\\ m\\ \end{matrix} \right)\right] &=\sum_tP\left[c_1=t\right]P\left[c_2=\frac{k+m}2-t\right]P\left[c_3=\frac{k+l}2-t\right]P\left[c_4=t-\frac{l+m}2\right]\\ &=2^{-n}\sum_t{w_1 \choose (w_1+t)/2}{w_2 \choose (w_2+\frac{k+m}2-t)/2}{w_3 \choose (w_3+\frac{k+l}2-t)/2}{w_4 \choose (w_4+t-\frac{l+m}2)/2} }$$

The range of the summation index $t$ is in principle that of $c_1,$ i.e., the set $\{-w_1,-w_1+2,\ldots,w_1-2,w_1\}$ but in practice many of the terms will be zero because of restrictions on the other $c_i.$

Let us see how this works out in your example matrix $M.$ First flip the signs in columns 1, 3 and 4 so that the top row has only positive entries. Then move the fifth column to the front and we obtain

$$M=\left( \begin{matrix} 1&1&1&1&1\\ 1&1&1&-1&-1\\ 1&1&-1&-1&-1\\ \end{matrix} \right)$$

so we have $n=5,$ $w_1=2,$ $w_2=0,$ $w_3=1$ and $w_4=2.$

We will repeat the second example from your numerical evaluation of the distribution, i.e., we compute $P[y=(-3\ -3\ -1)^T].$

We have $k=-3,$ $l=-3$ and $m=-1.$ From the fact that $c_2=0$ we see that the only value of $t$ contributing to the sum is $(k+m)/2=-2.$ So we get

$$P[y=(-3\ -3\ -1)^T]=2^{-5}{2 \choose 0}{0 \choose 0}{1 \choose 0}{2 \choose 1}=1/16,$$

which confirms your computation.