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.

  • $\begingroup$ I take it we may not assume that the elements of $M$ are chosen (like $x$) independently and uniformly from $\{-1, 1\}$? $\endgroup$ – Brian Tung Dec 30 '15 at 7:07
  • $\begingroup$ @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. $\endgroup$ – dorothy Dec 30 '15 at 7:26

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.

  • $\begingroup$ 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? $\endgroup$ – dorothy Dec 30 '15 at 19:14
  • $\begingroup$ 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$. $\endgroup$ – BGM Dec 31 '15 at 8:34

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.