3
$\begingroup$

I'm having trouble understanding how certain combinations of random variables can correlate. The problem is as follows:

I have a binary $m \times n$ matrix $A$ of full rank (over the finite field $\mathbb{F}_2$ with two elements), where each row has exactly $w$ $1$'s (i.e., their weights are all $w$).

I randomly pick an $n$-dimensional binary vector $\boldsymbol{v} = (v_0,\dots,v_{n-1}) \in \mathbb{F}_2^n$, where each $v_i$ is $1$ with probability $p$ and $0$ with probability $1-p$. The probability $p$ is assumed to be strictly smaller than $\frac{1}{2}$. Here, $v_i$ are all independent, so that picking $\boldsymbol{v}$ is seen as an i.i.d. Bernoulli process of probability $p$.

I am going to hash this vector $\boldsymbol{v}$ into an $m$-dimensional vector $\boldsymbol{v}' = (v'_0,\dots,v'_{m-1})$ by taking $\boldsymbol{v}' = A\boldsymbol{v}^T$ over $\mathbb{F}_2$. So, if I write the $i$th row of $A$ as $\boldsymbol{r}_i$, each $v'_i$ is the product $v'_i = \boldsymbol{r}_i\cdot\boldsymbol{v}^T$ between the $i$th row of $A$ and $\boldsymbol{v}$. In other words, I'm just taking the mod $2$ sum of some bits of $\boldsymbol{v}$.

Because the weight of $\boldsymbol{r}_i$ is assumed to be $w$, the probability $P(v'_i = 1)$ that the $i$th bit $v_i'$ of the hashed vector $\boldsymbol{v}'$ is $1$ is

$$P(v'_i = 1) = \sum_{x: \text{odd}}^{w}\binom{w}{x}p^x(1-p)^{w-x},$$

which is a constant if we fix $p$ and $w$, and is also uniform across all $v_i'$.

Now, if $A$ had linearly dependent rows, the hashed bits $v_i'$ are clearly not independent. My question is:

What if all rows of $A$ are linearly independent? Is $\boldsymbol{v}'$ an i.i.d. Bernoulli process with probability $P(v'_i = 1)$? If not, can I approximate it as one if $\boldsymbol{r}_i$ and $\boldsymbol{r}_j$ have only few $1$'s at the same columns for all $i \not=j$?

I remember I read in some research paper in electrical engineering that $\boldsymbol{v}'$ is i.i.d. Bernoulli if rows of $A$ are linearly independent, although I can't seem to remember where it was. (I found one recent paper that says this is the case: V. Toto-Zarasoa, A. Roumy, C. Guillemot, Maximum likelihood BSC parameter estimation for the Slepian-Wolf problem, IEEE Comm. Lett. 15 (2011) 232–234. It's Lemma 1 on the second page.) But now I think about it, this is counterintuitive (to me) because if two rows of $A$ have $1$ at the same column, that means that I took at least one same $v_i$ when hashing $\boldsymbol{v}$ for those two rows, so the corresponding $v_i'$ look correlated.

If my reasoning and Alecos Papadopoulos's answer are correct, the last part of the above question in boldface becomes essential. For instance, are there standard methods for evaluating how close or similar a given set of random variables like $\boldsymbol{v}'$ is to i.i.d. Bernoulli?

$\endgroup$
  • $\begingroup$ Thanks for the feedback. Regarding the "conjecture", it only applies to square matrices -you provided a counter-example using a non-square matrix. There are general standard methods to measure distance between distributions like the Kullback-Leibler distance, Hellinger distance etc (instances of "f-divergence"). But in order to apply these, we need to have the joint distribution of the $\boldsymbol{v}′$. Do we? $\endgroup$ – Alecos Papadopoulos Oct 27 '13 at 11:43
  • $\begingroup$ @AlecosPapadopoulos Thanks. My knowledge in statistics is very poor, and I had no idea what kind of thing is known about comparing two distributions etc. But I think I figured out where I should look. For instance, I just googled the definition of the Kullback-Leibler thingy, and it's just the difference of entropies. So, it looks like information theoretic approaches are the way to go for my problem. And I agree that this way of viewing the problem looks promising. $\endgroup$ – user31934 Oct 27 '13 at 22:39
  • $\begingroup$ (... cont.) I don't quite follow what you mean by "we need to have the joint distribution of the $\boldsymbol{v}'$," but I think I have enough information to find or come up with a satisfactory method on my own. Thanks. $\endgroup$ – user31934 Oct 27 '13 at 22:41
  • $\begingroup$ You 're welcome. Good luck with the matter. $\endgroup$ – Alecos Papadopoulos Oct 27 '13 at 22:43
2
$\begingroup$

1) Meta-issue:
I believe the OP should include in the title of the question a signal that something special is going on here - for example instead of "Are linear combinations of..." the title should read "Are $\mathbb{F}_2-$linear combinations of...", so that the reader gets the message that concepts may have special meanings in this specific question.

2) Bernoulli or not Bernoulli?
By $\mathbb{F}_2-$arithmetic, the sum of i.i.d Bernoulli rv's is not a Binomial, since all probabilities are condensed on the values $0$ and $1$. We first derive the binomial distribution and then add the probabilities of all even values of the support to the probability of $0$, and the probabilities of all odd values of the support to the probability of $1$ -and thus we obtain again a Bernoulli r.v. This is just to validate the probability mass function included in the OP's question. It is by construction a Bernoulli random variable, irrespective of how $P(v'_i = 1)$ is derived. Moreover if the number of $1$'s is the same in each row of the matrix $A$, then each $v'_i$ has an identical Bernoulli marginal distribution.

3) $\mathbb{F}_2-$ linear independence.
$\mathbb{F}_2-$ linear dependence does not look much like the "usual" concept of linear independence. To be able to obtain a square matrix of full row/column rank under $\mathbb{F}_2-$arithmetic, I conjecture that $w$, the number of $1$'s in each row, should be an odd number. Consider a square matrix $n\times n$ matrix $A$, and the first element of one of its rows, say $a_{i1}$. I reason as follows:
a) Assume $w$ is an even number.
a1) Assume $a_{i1} = 0$. Then in the remaining $n-1$ elements of the row, there exists an even number of $1$'s, which by $\mathbb{F}_2-$arithmetic will give us $0$. The rest of the elements of the row all also zero, so overall the sum of the $n-1$ elements will give $0$, i.e equal to the value of the first element.
a2) Assume $a_{i1} = 1$. Then in the remaining $n-1$ elements of the row, there exists an odd number of $1$'s, which by $\mathbb{F}_2-$arithmetic will give us $1$. The rest of the elements of the row are all zero, so overall the sum of the $n-1$ elements will give $1$, i.e again equal to the value of the first element.

So if $w=even$, the $\mathbb{F}_2-$sum of the $n-1$ columns will always equal the $n$-th column, depriving us of full rank.

b) Assume $w$ is an odd number.
b1) Assume $a_{i1} = 0$. Then in the remaining $n-1$ elements of the row, there exists an odd number of $1$'s, which by $\mathbb{F}_2-$arithmetic will give us $1$. The rest of the elements of the row all zero, so overall the sum of the $n-1$ elements will give $1$, i.e different to the value of the first element.
b2) Assume $a_{i1} = 1$. Then in the remaining $n-1$ elements of the row, there exists an even number of $1$'s, which by $\mathbb{F}_2-$arithmetic will give us $0$. The rest of the elements of the row all also zero, so overall the sum of the $n-1$ elements will give $0$, i.e again different than the value of the first element.

So it appears that $w= odd$, is at least a necessary condition to have a matrix $A$ of full column/row rank.

4) Stochastic (in)dependence in the $\mathbb{F}_2-$world.
Does the characteristics of $\mathbb{F}_2-$field affect the concept of stochastic (in)dependence? No. Two r.v.'s are independent if and only if their joint distribution is the product of their marginals. Meaning, the conditional distributions must equal the unconditional ones. Maybe the way operations work in the $\mathbb{F}_2-$field produces some unexpected results? Let's see: Assume that we have a square $A$ matrix that has $\mathbb{F}_2-$ linearly independent rows. The column vector process $\boldsymbol{v}'$, say of dimension $5\times 1$ is written

$$\boldsymbol{v}' = A\boldsymbol{v} = \left[\begin{matrix} v_1'(v_0,...)\\ v_2'(v_0,...)\\ v_3'(v_0,...)\\ v_4'(v_0,...)\\ v_5'(v_0,...)\\ \end{matrix}\right]$$

Now assume that $w=3$ and, say, that the $1$'s in $A$ as dispersed such that we have

$$ v_2' = v_0+v_1+v_5,\qquad v_4' = v_2+v_3+v_5$$

Consider the conditional probability (under $\mathbb{F}_2-$ arithmetic)

$$P_{\mathbb{F}_2}(v_2' =1\mid v_4'=0) = P_{\mathbb{F}_2}(v_0+v_1+v_5 =1\mid v_2+v_3+v_5=0)$$

If the conditioning statement is to affect the probabilities of $v_2'$, it will do so through $v_5$: the fact that $v_2+v_3+v_5=0$ must affect the probabilities related to $v_5$. Under the "usual" arithmetic this would be obvious: it would mean that $v_5$ should equal zero. What happens under $\mathbb{F}_2-$ arithmetic? We can examine $$P_{\mathbb{F}_2}(v_5 =1\mid v_2+v_3+v_5=0) = \frac{P_{\mathbb{F}_2}(\{v_5 =1\}\land \{v_2+v_3+v_5=0\})}{P_{\mathbb{F}_2}(v_2+v_3+v_5=0)}$$

The possible values of $v_2+v_3+v_5$ under $\mathbb{F}_2-$ arithmetic are enter image description here

from which we get the following contingency table

enter image description here

Therefore $$P_{\mathbb{F}_2}(v_5 =1\mid v_2+v_3+v_5=0) = \frac{2p^2(1-p)}{(1-p)^3+3p^2(1-p)}=\frac{2p^2}{1-2p+4p^2} \neq p$$ except when $p=1/2$ - but the set up explicitly specifies that $p<1/2$ . So we conclude that $$P_{\mathbb{F}_2}(v_5 =1\mid v_2+v_3+v_5=0) \neq P_{\mathbb{F}_2}(v_5 =1)$$

and so $$P_{\mathbb{F}_2}(v_2' =1\mid v_4'=0) \neq P_{\mathbb{F}_2}(v_2' =1)$$

I have shown that, in general, the elements of the vector process $\boldsymbol{v}'$ are not independent (although they have identical marginals), even under $\mathbb{F}_2$-arithmetic. I have found and read the lemma in the paper the OP mentions. There is no actual proof, just a verbal assertion that they are independent, due to the $\mathbb{F}_2$-linear independence of the rows of $A$. Hopefully, I am mistaken, but for the moment it appears the assertion is not valid.

5) Now what?
Not much. The joint distribution of the random vector will depend on how the $1$'s are allocated in matrix $A$. Without a specific form, the various measures of distance between distributions become vacuous. Intuitively, if $w$ is small relative to the length of the rows of $A$, then one can expect/hope, that the dependence will be relatively weak, and so pretending that the vector is i.i.d. won't hurt much... but without knowing the joint distribution, one cannot really tell... Copulas for discrete r.v.'s suffer from identification issues... I am still thinking about it, but I am not optimistic.

$\endgroup$
  • $\begingroup$ Yep. That's what I meant except that each $v_i'$ is an element of $\mathbb{F}_2$, so the sum is modulo $2$ (i.e., bits are xor'd). So we only have $P(v_i'=i)$ for $i=0,1$. If an simpler form of the probability mass function is of relevance here, I can prove $P(v_i'=1)=\frac{1-(1-2p)^w}{2}$ (and $P(v_i'=0)=1-P(v_i'=1)$) for any $w$. And that's about all I could figure out myself when I asked this. As you say, I also think $v_i'$ are correlated so $\boldsymbol{v}'$ can't be i.i.d. Bernoulli. $\endgroup$ – user31934 Oct 26 '13 at 14:00
  • $\begingroup$ (...cont.) But, for instance, Lemma 1 of this paper on data compression appeared in IEEE Comm. Lett. says otherwise. They claim that $v_i'$ are independent because rows of $A$ are linearly independent, which I thought was a mistake on the authors' side, although I might be missing something obvious. In any case, if I'm correct here, I should be able to prove that $v_i'$ and $v_j$ are not independent directly by showing $P(v_i'=1)P(v_j'=1)\not=P(v_i'=1\cap v_j'=1)$, for example. $\endgroup$ – user31934 Oct 26 '13 at 14:00
  • $\begingroup$ (...cont.2) So, the question is the one I asked last: If not, can I approximate it as one if $r_i$ and $r_j$ have only few 1's at the same columns for all $i\not=j$? For example, are there known standard methods for evaluating how close a given distribution like $\boldsymbol{v}'$ is to i.i.d. Bernoulli? Thanks for your help. I wanted to upvote your answer, but please wait until I get 10 more reps! $\endgroup$ – user31934 Oct 26 '13 at 14:02
  • $\begingroup$ This is a case where different backgrounds make communication fail. The "...an element of $\mathbb{F}_2$, so the sum is modulo $2$ (ie bits are xor'd)..." was completely lost to me (and I am not even sure exactly what that means), because the information "each row has exactly $w$ $1$'s" was so clear and definite. So can you please take the matrix $A$ that appears in my answer and write it as you meant it to be written? Then maybe I can do something more about the question. $\endgroup$ – Alecos Papadopoulos Oct 26 '13 at 18:30
  • $\begingroup$ To make it as elementary as possible, what I mean is that computation should be $0+0=1+1=0$, $1+0=0+1=1$, $0\cdot1=1\cdot0=0\cdot0=0,$ and $1\cdot1=1$, that is, addition is the "mod 2 sum" in the elementary math language (or the "exclusive OR" operation in the elementary comp sci language). And multiplication is the natural, commutative one: you multiple anything by $0$, and you get $0$. And multiplying by $1$ doesn't change anything. And you don't care if it's $a\cdot b$ or $b\cdot a$; they're the same. For example, $1+1+0+1=1$. $\endgroup$ – user31934 Oct 26 '13 at 19:05

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.