(c) If you flip a coin 100 times, the probability of flipping exactly 30 heads is approx- imately 23 out of a million. Give an upper bound on the probability of flipping 30 Solution. Applying the bound above gives (23.10-) 100-30+1 100-2.30+1 The actual value is about 39.25. 10-6 Problem 6. Many of the best computer algorithms rely on randomization. However, gen- erating uniform, mutually independent random bits is not so easy!(The mathematician John von Neumann said, " Anyone who considers arithmetic methods of producing ran- dom digits is, of course, in a state of sin. Fortunately, some algorithms work equally well with pairwise-independent random bits, which are relatively"cheap". In particular, one can covert a set of mutually independent bits into an exponentially larger set of pairwise- independent random bits Let b be a set of n uniform mutually-independent o-1 random variables (a) let s be a nonempty subset of the bits in b. let the random variable s be the Xor of all the bits in S. Show that s is uniformly distributed on 0,1] (Hint: Let b be one of the bits in S and let sbe the XoR of all other bits in S. Solution Pr(s=0)=Pr(s=0nb=0)+Pr(s=l0b=1 =Pr(S=0)Pr(b=0)+Pr(s=1)Pr(b=1) 1 Pr(s=0)+Pr( 2(Pr(=0)+Pr(s=1) We first rewrite the events=0 and then use the independence of b and s. The remaining steps use the facts that b is 0 or 1 with equal probability and that sis either 0 or 1(with unknown probabilities). Since s =0 with probability 1/2,we must have s= I with probability 1 2 as well, so s is uniformly distributed on 10,11 (b)Now let T be another nonempty subset of bits in B. Let the random variable t be the XoR of all the bits in T Show that s and t are independent (Hint: Define s to be the Xor of bits in S-t, t' to be the XoR of bits in T-S, and to be the Xor of bits in SnT. Now consider three cases: (1)SnT=0, (2)SnT=S orS∩T=T,and(3)S∩T≠0,S,orT.)� 6 Problem Set 10 (c) If you flip a coin 100 times, the probability of flipping exactly 30 heads is approx￾imately 23 out of a million. Give an upper bound on the probability of flipping 30 or fewer heads. Solution. Applying the bound above gives: � 23 · 10−6 � 100 − 30 + 1 · 100 − 2 · 30 + 1 ≈ 40 · 10−6 The actual value is about 39.25 · 10−6 . Problem 6. Many of the best computer algorithms rely on randomization. However, gen￾erating uniform, mutually independent random bits is not so easy! (The mathematician John von Neumann said, “Anyone who considers arithmetic methods of producing ran￾dom digits is, of course, in a state of sin.”) Fortunately, some algorithms work equally well with pairwise­independent random bits, which are relatively “cheap”. In particular, one can covert a set of mutually independent bits into an exponentially larger set of pairwise￾independent random bits. Let B be a set of n uniform, mutually­independent 0­1 random variables. (a) Let S be a nonempty subset of the bits in B. Let the random variable s be the XOR of all the bits in S. Show that s is uniformly distributed on {0, 1}. (Hint: Let b be one of the bits in S and let s� be the XOR of all other bits in S.) Solution. Pr (s = 0) = Pr (s� = 0 ∩ b = 0) + Pr (s� = 1 ∩ b = 1) = Pr (s� = 0) Pr (b = 0) + Pr (s� = 1) Pr (b = 1) 1 1 = Pr (s� = 0) + Pr (s� = 1) 2 2 1 = (Pr (s� = 0) + Pr (s� = 1)) 2 1 = 2 We first rewrite the event s = 0 and then use the independence of b and s� . The remaining steps use the facts that b is 0 or 1 with equal probability and that s� is either 0 or 1 (with unknown probabilities). Since s = 0 with probability 1/2, we must have s = 1 with probability 1/2 as well, so s is uniformly distributed on {0, 1}. (b) Now let T be another nonempty subset of bits in B. Let the random variable t be the XOR of all the bits in T. Show that s and t are independent. (Hint: Define s� to be the XOR of bits in S − T, t � to be the XOR of bits in T − S, and i to be the XOR of bits in S ∩ T. Now consider three cases: (1) S ∩ T = ∅, (2) S ∩ T = S or S ∩ T = T, and (3) S ∩ T = ∅, S, or T.)