Problem Set 10 Solution. We must show that Pr(s=ant=b)=Pr(s=a)Pr(t=b)for all a and b By the preceding problem part, Pr(s=a)=Pr(t= b)=1/2. So we really only need to show that for all a and b (s=ant=b)=1/4 Define random variables s t, and i as described above. These random variables are mutually independent since they are functions of mutually independent bits We can rewrite the quantity were trying to analyze, Pr(s =ant=b), in terms of these variables as follows Pr(s=ant=b)=Pr(=ant'=bni=0) +Pr(=a∩t=bni=1) Pr(s=a) Pr(t'=b Pr(i=0) +Pr(s=a)Pr(t'=b Pr(i=1) ow we ar the three cases: 1. If SnT=0, then Pr(i=0)=l and Pr(i=1)=0. However, the sets S-Tand T-Sare nonempty, so Pr(s=a)=Pr(t'=b)=1/2 by the preceding part Substituting into()gives Pr(s=a∩t=b) 1+ 2. If SnT=S, then S-T=0 and so Pr(s'=0)=l and Pr(s'=1)=0. The sets SnT and T-S are nonempty, so i and t' are uniformly distributed by the preceding part. Substituting into ()gives 11 Pr(s=a∩t=b)=0 If SnT=T, then a symmetric argument applies 3. If SnT#0,S, or T, then the sets S-T, T-S, and SnT are all nonempty. Therefore, s, t', and i are all uniformly-distributed. Substituting into()gives 1111111 Pr(s=ant=b) Therefore, s and t are independent (c) Explain how to construct a set of 2n-1 uniform, pairwise-independent 0-1 ran- dom variables from a set of n uniform, mutually-independent 0-1 random variables Solution. Take the sums of all nonempty subsets modulo 2. In the two preceding parts, we proved that these random variables are uniform and pairwise indepen dent (The quantity a1 XOR a2 XOR... XOR an is equal to(a1+a2+..+an)rem 2� � � � � Problem Set 10 7 Solution. We must show that Pr (s = a ∩ t = b) = Pr (s = a) Pr (t = b) for all a and b. By the preceding problem part, Pr (s = a) = Pr (t = b) = 1/2. So we really only need to show that for all a and b: Pr (s = a ∩ t = b) = 1/4 Define random variables s� , t � , and i as described above. These random variables are mutually independent since they are functions of mutually independent bits. We can rewrite the quantity we’re trying to analyze, Pr (s = a ∩ t = b), in terms of these variables as follows: Pr (s = a ∩ t = b) = Pr (s� = a ∩ t � = b ∩ i = 0) + Pr s� = a ∩ t � = b ∩ i = 1 = Pr (s� = a) Pr (t � = b) Pr (i = 0) + Pr (s� = a) Pr t � = b Pr (i = 1) (*) Now we analyze the three cases: 1. If S ∩T = ∅, then Pr (i = 0) = 1 and Pr (i = 1) = 0. However, the sets S −T and T − S are nonempty, so Pr (s� = a) = Pr (t � = b) = 1/2 by the preceding part. Substituting into (*) gives: 1 1 1 1 1 Pr (s = a ∩ t = b) = 1 + 0 = 2 · 2 · 2 · 2 · 4 2. If S ∩ T = S, then S − T = ∅ and so Pr (s� = 0) = 1 and Pr (s� = 1) = 0. The sets S ∩ T and T − S are nonempty, so i and t � are uniformly distributed by the preceding part. Substituting into (*) gives: 1 1 1 1 1 Pr (s = a ∩ t = b) = 0 · + 1 · = 2 · 2 2 · 2 4 If S ∩ T = T, then a symmetric argument applies. 3. If S ∩ T = ∅, S, or T, then the sets S − T, T − S, and S ∩ T are all nonempty. Therefore, s� , t � , and i are all uniformly­distributed. Substituting into (*) gives: 1 1 1 1 1 1 1 Pr (s = a ∩ t = b) = + = 2 · 2 · 2 2 · 2 · 2 4 Therefore, s and t are independent. (c) Explain how to construct a set of 2n − 1 uniform, pairwise­independent 0­1 ran￾dom variables from a set of n uniform, mutually­independent 0­1 random variables. Solution. Take the sums of all nonempty subsets modulo 2. In the two preceding parts, we proved that these random variables are uniform and pairwise indepen￾dent. (The quantity a1 XOR a2 XOR . . . XOR an is equal to (a1 + a2 + . . . + an) rem 2.)