Consider a random $n$ by $n$ matrix $M$ chosen uniformly over all $n$ by $n$ $(0,1)$ matrices and a random vector $v \in \{-1,0,1\}^n$ chosen uniformly as well. Let $X = Mv$.

What is $$P(X_i = 0 \mid \forall j < i \; X_j = 0 )\;?$$

Although the rows of $M$ are independent, this probability does not equal $P(X_i = 0)$ which is where I am stuck.


Since the rows of $M$ are independent, you're basically conducting $n$ independent probes of $v$. If $v$ has $k$ entries $+1$ and $l$ entries $-1$, the probability of its product with a row $r$ of $M$ being $0$ is $2^{-(k+l)}$ times the number of ways of selecting $k$ of the $k+l$ non-zero entries in $v$ and choosing $r$ to be $1$ when (entry is selected) XOR (entry is $+1$). (If this seems a bit complicated and out of the blue, you can unpack it as choosing $j$ entries that are $+1$ in $v$ and $j$ entries that are $-1$ in $v$ to be $1$ in $r$, summing over $j$ and then applying Vandermonde's identity.) Taking into account the a priori probability for $k$ entries to be $+1$ and $l$ entries to be $-1$, we get for the probability you're seeking

$$P(X_i = 0 \mid \forall j < i \; X_j = 0 )=\frac{\sigma_{i+1}}{\sigma_i}$$


$$ \sigma_i=\sum_{k+l\le n}\left(2^{-(k+l)}\binom{k+l}k\right)^i\binom n{k,l,n-k-l}\;. $$

The quotient tends to $1$ for $i\to\infty$, as you grow more and more certain that $v$ consists of all $0$s.

  • $\begingroup$ Sorry to be really dim but I thought I would plot your solution and realised I don't fully understand it. In particular, the sentence with the XOR in it. What is being XOR'ed with what? As I don't fully understand it I am not sure how to change it. For example, what happens if $P(v_i=0) = 1/2$ and $P(v_i= -1)= P(v_i = 1)$? $\endgroup$ – user66307 Jul 23 '15 at 14:55
  • 1
    $\begingroup$ @Lembik: I wouldn't blame you for not fully understanding that sentence :-) The two propositions in parentheses are being XORed. So if the entry is selected and it's $+1$, or if it's not selected and it's $-1$, the result is $0$, whereas if the entry is selected and it's $-1$, or it's not selected and it's $+1$, the result $1$. I think it will become clearer if you go through the detour of Vandermonde's identity; that's how I came up with it. $\endgroup$ – joriki Jul 24 '15 at 16:32
  • 1
    $\begingroup$ @Lembik: Regarding the non-uniform probabilities: The first part of the answer deals only with $M$ and assumes that its entries are uniformly chosen from $\{0,1\}$. The probabilities you propose to change only enter the calculation (implicitly) in the last equation, where the binomial coefficients express the uniform probabilities and the factor $3^{-n}$ is omitted because it cancels in the ratio $\sigma_{i+1}/\sigma_i$. For non-uniform probabilities $p_-$, $p_0$, $p_+$, you'd need to include a factor $p_+^kp_-^lp_0^{n-k-l}$. $\endgroup$ – joriki Jul 24 '15 at 16:36

Your Answer

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