Question

Problem 3 Let Xi, X2,... , Xn be a sequence of binary, i.i.d. random variables. Assume P (Xi 1) P (Xi = 0) = 1/2. Let Z be a parity check on seluence Xi, X2, ,X,, that is, Z = X BX2 e (a) Is Z statistically independent of Xi? (Assume n> 1) (b) Are X, X2, ..., Xn 1, Z statistically independent? (c) Are X, X2,.., Xn, Z statistically independent? (d) Is Z statistically independent of Xi if P (X,-1) #1/2? You lnay take n-2 here.

Answer 1

$(a)~P(Z=1)=\frac{2^{n-1}}{2^n}=\frac{1}{2}\\ Z=1\Rightarrow X_i~takes~0~or~1,~i=1(1)n-1~but~choice~of~X_n~depends~on~X_{n-1}\\ then~P(Z=0)=\frac{1}{2}\\ P(X_1=1,Z=1)=\frac{2^{n-2}}{2^n}=\frac{1}{2^2}=P(X_1=1)P(Z=1)\\ Similarly,~P(X_1=0,Z=1)=P(X_1=0)P(Z=1),\\ ~P(X_1=1,Z=0)=P(X_1=1)P(Z=0),~P(X_1=0,Z=0)=P(X_1=0)P(Z=0).\\ Hence~X_1~and~Z~are~independent.\\ (b)~P(X_1=x_1,...,X_{n-1}=x_{n-1},Z=1)\\ =P(X_1=x_1,...,X_{n-1}=x_{n-1},x_n=x_{n-1})=\frac{1}{2^n}\\ =P(X_1=x_1)P(X_2=x_2)...P(X_{n-1}=x_{n-1})P(Z=z)\\ Hence~X_1,...,X_{n-1},Z~are~independent.\\ (c)~P(X_1=x_1,...,X_{n-1}=x_{n-1},X_{n}=0,Z=1)=0\neq\\ P(X_1=x_1)P(X_2=x_2)...P(X_{n-1}=x_{n-1})P(X_n=x_n)P(Z=z)=\frac{1}{2^{n+1}}\\ Hence~X_1,...,X_{n},Z~are~not~independent.\\ (d)~P(X_1=1,Z=0)=P(X_1=1,X_2=0)\\ =P(X_1=1)P(X_2=0),~since~X_i's~are~independent\\ =p(1-p)~(let~P(X_i=1)=p,~i=1(1)n)\\$

$P(Z=0)=P(X_1=1,X_2=0)+P(X_1=0,X_2=1)\\ =2p(1-p)~since~X_i's~are~iid\\ so,~if~p\neq 1/2,~then~P(X_1=1,Z=0)=p(1-p)\neq 2p^2(1-p)\\ Hence~X_1~and~Z~are~not~independent.$