Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 3 down vote favorite

We throw two coins in a row and thus get the event space $\{ZZ, WW, ZW, WZ\}$. Each of the 4 elementary events has a probability $1/4$. how can I construct 3 binary random variable $x_1$, $x_2$, $x_3$ about this event space, which are 2-fold independent, but not independent.

share|improve this question
That's a basic exercise in stochastics. What have you tried? – Raphael♦ Oct 30 '12 at 14:55
Hint: one solution has two of the random variables being the two coin tosses. – Yuval Filmus Oct 30 '12 at 14:57
I have no idea how to proceed. I am a stud in terms stochastics. – Queue Oct 30 '12 at 22:02
@Queue You can't expect us to solve the exercise for you. Make sure that you understand what the question is asking. If you don't understand some of the terms, ask. – Yuval Filmus Oct 30 '12 at 22:35

2 Answers

up vote 0 down vote

Consider an Exclusive-OR gate with inputs (logical variables) $x$ and $y$ and output $z = x\oplus y$. Suppose $x$ and $y$ are equally likely to take on values $0$ and $1$ and are independent, that is $$P\{x = a, y = b\} = P\{x = a\}P\{y = b\} = \frac{1}{4} ~~\text{for all} ~a, b \in \{0,1\}.$$ Then, $P\{z = 1\} = P\{x = 1, y = 0\} + P\{x=0, y = 1\} = \frac{1}{2}$ and so $$P\{x = 1, z = 1\} = P\{x = 1, x\oplus y = 1\} = P\{x = 1, y = 0\} = \frac{1}{4} = P\{x = 1\}P\{z=1\},$$ that is, $x$ and $z$ are also independent. Thus, we are led to the remarkable conclusion that the output $z$ of an Exclusive-OR gate is independent of its input $x$. A similar calculation shows that the output $z$ is also independent of input $y$, that is, the output of an Exclusive-OR gate is independent of its inputs!

Lest we accept the moral principle that the output of an Exclusive-OR gate does not depend on its inputs, let me say that this independence disappears if $P\{x = 1\}$ is not exactly $\frac{1}{2}$ but differs from $\frac{1}{2}$ by even an infinitesimal amount.

share|improve this answer
"moral principle" -- huh? – Raphael♦ Nov 2 '12 at 12:08
@Raphael I would have called it a Declaration of Independence if that term were not used elsewhere. The word independence has two different meanings in this problem. $x$ and $y$ might be physically independent meaning that they arise from sources that have nothing to do with each other. In this case, the model captures this by setting $P\{x=1,y=1\}=P\{x=1\}P\{y=1\}$ regardless of what $P\{x=1\}$ and $P\{y=1\}$ are. On the other hand, the independence of $x$ and $z$ is stochastic independence and is an artifact of the assignment of the values of $P\{x=1\}$ and $P\{y=1\}$; (continued) – Dilip Sarwate Nov 2 '12 at 14:08
@Raphael as I noted, takea different value for $P\{x=1\}$ and the independence disappears. This fact is often forgotten by some who then infer the existence of physical independence from the observed stochastic independence. The output of an Exclusive-OR gate always does depend physically on its inputs, but can be stochastically independent for suitable choice of probabilities. Physical independence is captured in the probability model as stochastic independence but proof of stochastic independence should not be used to infer physical independence, which I suggested, tongue-in-cheek, holds – Dilip Sarwate Nov 2 '12 at 14:15
@Dilip It may be that the physically generated entities are $x$ and $z$, and $y$ is computed by $y=x\oplus z$. The situation is entirely symmetric. Or perhaps $x,y,z$ are generated independently, but you only observe the result if $x\oplus y\oplus z=0$. – Yuval Filmus Nov 2 '12 at 15:26
@YuvalFilmus I regret that I am unable to understand what is meant by your comment and how it applies to my answer in which $z$ is the output of an XOR gate with inputs $x$ and $y$. Yes, $y = x \oplus z$ since $z = x\oplus y$, but the XOR gate does not compute $y$ from $x$ and $z$. – Dilip Sarwate Nov 3 '12 at 3:42
show 1 more comment
up vote 4 down vote

Let $E = \{ZZ,WW,ZW,WZ\}$. A binary random variable is a mapping $X\colon E \rightarrow \{0,1\}$. The probability of an event, say $X=0$, is defined as $$ \Pr[X = 0] =\frac{|\{e \in E : X(e) = 0\}|}{4}. $$ For example, let $C_1(ZZ)=C_1(ZW) = 0$, $C_1(WZ)=C_1(WW) = 1$. Then $\Pr[C_1=0]=1/2$.

Two (binary) random variables $X_1,X_2$ are independent if for every $b_1,b_2 \in \{0,1\}$, $$\Pr[X_1 = b_1 \text{ and } X_2 = b_2] = \Pr[X_1 = b_1] \Pr[X_2 = b_2]. $$ For example, if $C_2(ZZ) = C_2(WZ) = 0$ and $C_2(ZW) = C_2(WW) = 1$, then you can check that $C_1$ and $C_2$ are independent, by checking that $\Pr[C_1 = b] = \Pr[C_2 = b] = 1/2$ and $\Pr[C_1 = b_1 \text{ and } C_2 = b_2] = 1/4$. On the other hand, $C_1$ and $C_1$ are not independent since $\Pr[C_1 = 0 \text{ and } C_1 = 0] = 1/2$.

Similarly you can define when more than two random variables are independent. It should be clear that there are no three binary random variables $X_1,X_2,X_3$ with $\Pr[X_1 = 0] = \Pr[X_2 = 0] = \Pr[X_3 = 0] = 1/2$ which are independent, since that would imply $\Pr[X_1 = X_2 = X_3 = 0] = 1/8$, which is impossible (the only values that $\Pr$ can obtain are $0,1/4,1/2,3/4,1$). On the other hand, any three constant random variables are independent.

A set of random variables is $k$-wise independent if any $k$ of them are independent. The question asks you to find three random variables $X_1,X_2,X_3$ so that any two are independent, but all three aren't. My hint is that there is a solution with $X_1 = C_1$ and $X_2 = C_2$.

share|improve this answer
hmm and X3 = c2? – Queue Oct 31 '12 at 7:34
Yuval's answer is excellent. So here is only one remark. Following this answer you are left with filling a table with zeros and ones. The table has 4 columns for ZZ,ZW,WZ,WW - and 3 rows for your 3 random variables. Try to fill the table such that every row contains two 1s and such that if you add any two rows (vector-wise), there is exactly one 2. – A.Schulz Oct 31 '12 at 8:04
$X_3 = C_2$ doesn't work since $X_2,X_3 = C_2,C_2$ are not independent. – Yuval Filmus Oct 31 '12 at 13:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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