2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ The assumption that $n$ is even is redundant, and in fact your example violates it. $\endgroup$ – Justpassingby Jan 7 '16 at 12:52
  • $\begingroup$ @Justpassingby Thank you. Question fixed. $\endgroup$ – dorothy Jan 7 '16 at 12:53
1
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, this is very interesting but I am not sure I get all the details yet. Would it possible to show a small worked example please? $\endgroup$ – dorothy Jan 7 '16 at 10:24
  • $\begingroup$ I made the derivation slightly more explicit, please ask specific questions about anything not clear yet. In the meantime I am working on an example. $\endgroup$ – Justpassingby Jan 7 '16 at 11:08
  • 1
    $\begingroup$ Example done. Fire away with more questions now. $\endgroup$ – Justpassingby Jan 7 '16 at 11:40
  • $\begingroup$ This is very interesting and the worked example is great. I will have to study it and come back with questions but thank you again. $\endgroup$ – dorothy Jan 7 '16 at 12:18
  • 1
    $\begingroup$ Then the sum has a single term corresponding to $t=0.$ $\endgroup$ – Justpassingby Jan 7 '16 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.