6.042/18.062J Mathematics for Computer Science April 26,2005
Srini Devadas and Eric Lehman
Problem Set 10 Solutions
Due,Monday,May 2 at 9 PM
Problem 1,Justify your answers to the following questions about independence,
(a) Suppose that you roll a fair die that has six sides,numbered 1,2,...,6,Is the
event that the number on top is a multiple of 2 independent of the event that the
number on top is a multiple of 3?
Solution,Let A be the event that the number on top is a multiple of 2,and let B be
the event that the number on top is a multiple of 3,We have,
3 2 1
Pr (A)· Pr (B) = = = Pr (A∩ B)
6
·
6 6
Therefore,these events are independent,
(b) Now suppose that you roll a fair die that has four sides,numbered 1,2,3,4,Is
the event that the number on top is a multiple of 2 independent of the event that the
number on top is a multiple of 3?
Solution,As before,let A be the event that the number on top is a multiple of 2,
and let B be the event that the number on top is a multiple of 3,Now,however,we
have,
2 1 1
Pr (A)· Pr (B) = =
4
·
4 8
But,
Pr (A∩ B) = 0
Since these results disagree,the events are not independent,
(c) Now suppose that you roll a fair die that has eight sides,numbered 1,2,...,8,
Again,is the event that the number on top is a multiple of 2 independent of the
event that the number on top is a multiple of 3?
Solution,As before,let A be the event that the number on top is a multiple of 2,and
let B be the event that the number on top is a multiple of 3,This time,we have,
4 2 1
Pr (A)· Pr (B) = =
8
·
8 8
And,
Pr (A∩ B) = 1/8
Therefore,these events are independent,
2 Problem Set 10
(d) Finally,suppose that you roll the fair,eight-sided die again,Let the random
variable X be the remainder when the number on top is divided by 2,and let the
random variable Y be the remainder when the number on top is divided by 3,Are
the random variables X and Y independent?
Solution,First,let’s tabulate the values of X and Y,
die roll X Y
1 1 1
2 0 2
3 1 0
4 0 1
5 1 2
6 0 0
7 1 1
8 0 2
Working from the table,we have,
2
Pr (X = 1 ∩ Y = 1) =
8
But,
4 3
Pr (X = 1) · Pr (Y = 1) =
8
·
8
3
=
16
Since these results con?ict,the random variables are not independent,
Problem 2,Philo T,Megabrain,a noted parapsychology researcher,has discovered an
amazing phenomenon! He puts a psychic on each side of an opaque,soundproof barrier,
Each psychic rolls a fair die,looks at it,and tries to guess what number came up on the
other die by telepathy,Since the dice are fair and independent,the psychics should guess
correctly only 1 time in 6,However,after extensive testing,Philo has discovered that they
actually do slightly better,
(a) Philo’s somewhat-arbitrary policy is to run the test over and over each day until
both psychics roll a 6 at the same time,Then he immediately halts testing for the
day,before the psychics make guesses,Explain the?aw in Philo’s experiment in
qualitative terms,
Solution,If a psychic sees a 6 on her own die,she knows not to guess that the other
die is a 6,
(b) If a psychic exploits this?aw optimally,with what probabilty can she guess the
number on the opposite die?
3 Problem Set 10
Solution,If she sees a 1,2,3,4,or 5,then her probability of guessing the other die
is the normal 1/6,However,if she sees a 6,then she knows that the other die is not
a 6,and so her probability of guessing the other die is 1/5,By the total probability
law,her probability of guessing the other die correctly in general is,
5 1 1 1 31
+ =
6
·
6 6
·
5 180
Problem 3,There is a set P consisting of 1000 people,
The favorite color of 20% of the people is blue,
The favorite color of 30% is green,
The favorite color of 50% is red,
(a) Suppose we select a set of two people {p
1
,p
2
}? P uniformly at random,Let the
random variables C
1
and C
2
denote their favorite colors,Are C
1
and C
2
indepen-
dent? Justify your answer,
Solution,No,For example,Pr (C
1
= blue) = 200/1000,However,
Pr (C
2
= blue | C
1
= blue) = 199/999
since 199 of the remaining 999 people like blue after one person who likes blue is
selected,
(b) Suppose we select a sequence of two people (p
1
,p
2
) ∈ P×P uniformly at random,
Let the random variables C
1
and C
2
denote their favorite colors,Now are C
1
and C
2
independent? Justify your answer,
Solution,Yes,Let c(n) be the color that the n-th person likes,The random vari-
ables p
1
and p
2
are independent,Functions of independent random variables are
independent,so C
1
= c(p
1
) and C
2
= c(p
2
) are independent,
Problem 4,Secret documents are disappearing from CIA headquarters,Some documents
are simply misplaced,But the Security Chief suspects that others are begin stolen by
Agent X and passed to the government of Liechtenstein to further its relentless pursuit of
global domination,Two inspectors are assigned to investigate the matter,
Inspector AM determines that the event that a document disappears during a given
day is independent of the event that Agent X is in headquarters that day,
Similarly,inspector PM determines that the event that a document disappears dur-
ing a given night is independent of the event that Agent X is around that night,
The Security Chief concludes that the event that a document disappears is independent
of the event that Agent X is present,Therefore,Agent X is probably innocent,
4 Problem Set 10
(a) Construct a probability model of the situation,State the inspectors’ determina-
tions and the Security Chief’s conclusion as probabilities,
Solution,Let the sample space S be a set of days and nights,De?ne the following
three events,
D = A secret document disappears
X = Agent X is at headquarters
A = It is daytime,
In these terms,Inspector AM says,
Pr (D ∩ X A) = Pr (D | A)· Pr (X A)| |
Inspect PM says,
Pr D ∩ X A = Pr D | A Pr X | A| ·
And the Security Chief concludes,
Pr (D ∩ X) = Pr (D)· Pr (X)
(b) Is the Security Chief’s reasoning correct? Justify your answer,
Solution,The security chief is wrong,For example,suppose that S consists of a
single day and a single night,
S = {day,night}
Assign night and day each probability 1/2,Now suppose that Agent X is around
during the night and a document disappears only at night,
D = {night}
X = {night}
A = {day}
Furthermore,suppose Pr (day) = Pr (night) = 1/2,These suppositions are consis-
tent with the inspectors’ determinations,
Pr (D ∩ X A) =
Pr (D ∩ X ∩ A)
= 0|
Pr (A)
Pr (D | A)· Pr (X A) =
Pr (D ∩ A) Pr (X ∩ A)
= 0|
Pr (A)
·
Pr (A)
Pr D ∩ X A =
Pr D ∩
X
∩ A
= 1|
Pr A
Pr X ∩ A
Pr D | A Pr X | A =
Pr D
∩
A
= 1·
Pr A
·
Pr A
?
5 Problem Set 10
However,the Security Chief’s conclusion is wrong,because:
Pr(D ∩ X) = Pr(night) = 1/2
But:
Pr(D)· Pr(X) = (1/2)· (1/2) = 1/4
So Agent X may be guilty after all!
Problem 5,Suppose you?ip n fair,independent coins,Let the random variable X be the
number of heads that come up,
(a) What is the exact value of Pr(X ≤ k),the probability of?ipping k or fewer heads?
Your answer need not be in closed form,
Solution.
n n n
+ +,.,+
k k?1 0
n
2
(b) Suppose k < n/2,Prove that,
n? k + 1
· Pr(X = k)Pr(X ≤ k) ≤
n? 2k + 1
(Upper bound your previous answer with an in?nite geometric sum and then eval-
uate the sum.)
Solution,We can upper bound the numerator in the preceding answer as follows,
n n n
+ +,.,+
k k? 1 0
n n
= +
k
n
+
k(k?1)
n
+
k(k?1)(k?2)
+,.,
n?k+1 (n?k+1)(n?k+2) (n?k+1)(n?k+2)(n?k+3)
k k k k
n k k
2
k
3
1 + + + +,.,≤
k
·
n? k + 1 (n? k + 1)
2
(n? k + 1)
3
n 1
=
k
k
·
1?
n?k+1
n n? k + 1
=
k
·
n? 2k + 1
(Note that the geometric sum converges only if k < n/2.) Therefore:
n? k + 1
Pr(X ≤ k) ≤
n? 2k + 1
· Pr(X = k)
6 Problem Set 10
(c) If you?ip a coin 100 times,the probability of?ipping exactly 30 heads is approx-
imately 23 out of a million,Give an upper bound on the probability of?ipping 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?rst 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,De?ne 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.)
7 Problem Set 10
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
De?ne 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 2
n
1 uniform,pairwise-independent 0-1 ran-
dom variables from a set of nuniform,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 a
1
XOR a
2
XOR,.,XOR a
n
is equal to (a
1
+ a
2
+,.,+ a
n
) rem 2.)
Srini Devadas and Eric Lehman
Problem Set 10 Solutions
Due,Monday,May 2 at 9 PM
Problem 1,Justify your answers to the following questions about independence,
(a) Suppose that you roll a fair die that has six sides,numbered 1,2,...,6,Is the
event that the number on top is a multiple of 2 independent of the event that the
number on top is a multiple of 3?
Solution,Let A be the event that the number on top is a multiple of 2,and let B be
the event that the number on top is a multiple of 3,We have,
3 2 1
Pr (A)· Pr (B) = = = Pr (A∩ B)
6
·
6 6
Therefore,these events are independent,
(b) Now suppose that you roll a fair die that has four sides,numbered 1,2,3,4,Is
the event that the number on top is a multiple of 2 independent of the event that the
number on top is a multiple of 3?
Solution,As before,let A be the event that the number on top is a multiple of 2,
and let B be the event that the number on top is a multiple of 3,Now,however,we
have,
2 1 1
Pr (A)· Pr (B) = =
4
·
4 8
But,
Pr (A∩ B) = 0
Since these results disagree,the events are not independent,
(c) Now suppose that you roll a fair die that has eight sides,numbered 1,2,...,8,
Again,is the event that the number on top is a multiple of 2 independent of the
event that the number on top is a multiple of 3?
Solution,As before,let A be the event that the number on top is a multiple of 2,and
let B be the event that the number on top is a multiple of 3,This time,we have,
4 2 1
Pr (A)· Pr (B) = =
8
·
8 8
And,
Pr (A∩ B) = 1/8
Therefore,these events are independent,
2 Problem Set 10
(d) Finally,suppose that you roll the fair,eight-sided die again,Let the random
variable X be the remainder when the number on top is divided by 2,and let the
random variable Y be the remainder when the number on top is divided by 3,Are
the random variables X and Y independent?
Solution,First,let’s tabulate the values of X and Y,
die roll X Y
1 1 1
2 0 2
3 1 0
4 0 1
5 1 2
6 0 0
7 1 1
8 0 2
Working from the table,we have,
2
Pr (X = 1 ∩ Y = 1) =
8
But,
4 3
Pr (X = 1) · Pr (Y = 1) =
8
·
8
3
=
16
Since these results con?ict,the random variables are not independent,
Problem 2,Philo T,Megabrain,a noted parapsychology researcher,has discovered an
amazing phenomenon! He puts a psychic on each side of an opaque,soundproof barrier,
Each psychic rolls a fair die,looks at it,and tries to guess what number came up on the
other die by telepathy,Since the dice are fair and independent,the psychics should guess
correctly only 1 time in 6,However,after extensive testing,Philo has discovered that they
actually do slightly better,
(a) Philo’s somewhat-arbitrary policy is to run the test over and over each day until
both psychics roll a 6 at the same time,Then he immediately halts testing for the
day,before the psychics make guesses,Explain the?aw in Philo’s experiment in
qualitative terms,
Solution,If a psychic sees a 6 on her own die,she knows not to guess that the other
die is a 6,
(b) If a psychic exploits this?aw optimally,with what probabilty can she guess the
number on the opposite die?
3 Problem Set 10
Solution,If she sees a 1,2,3,4,or 5,then her probability of guessing the other die
is the normal 1/6,However,if she sees a 6,then she knows that the other die is not
a 6,and so her probability of guessing the other die is 1/5,By the total probability
law,her probability of guessing the other die correctly in general is,
5 1 1 1 31
+ =
6
·
6 6
·
5 180
Problem 3,There is a set P consisting of 1000 people,
The favorite color of 20% of the people is blue,
The favorite color of 30% is green,
The favorite color of 50% is red,
(a) Suppose we select a set of two people {p
1
,p
2
}? P uniformly at random,Let the
random variables C
1
and C
2
denote their favorite colors,Are C
1
and C
2
indepen-
dent? Justify your answer,
Solution,No,For example,Pr (C
1
= blue) = 200/1000,However,
Pr (C
2
= blue | C
1
= blue) = 199/999
since 199 of the remaining 999 people like blue after one person who likes blue is
selected,
(b) Suppose we select a sequence of two people (p
1
,p
2
) ∈ P×P uniformly at random,
Let the random variables C
1
and C
2
denote their favorite colors,Now are C
1
and C
2
independent? Justify your answer,
Solution,Yes,Let c(n) be the color that the n-th person likes,The random vari-
ables p
1
and p
2
are independent,Functions of independent random variables are
independent,so C
1
= c(p
1
) and C
2
= c(p
2
) are independent,
Problem 4,Secret documents are disappearing from CIA headquarters,Some documents
are simply misplaced,But the Security Chief suspects that others are begin stolen by
Agent X and passed to the government of Liechtenstein to further its relentless pursuit of
global domination,Two inspectors are assigned to investigate the matter,
Inspector AM determines that the event that a document disappears during a given
day is independent of the event that Agent X is in headquarters that day,
Similarly,inspector PM determines that the event that a document disappears dur-
ing a given night is independent of the event that Agent X is around that night,
The Security Chief concludes that the event that a document disappears is independent
of the event that Agent X is present,Therefore,Agent X is probably innocent,
4 Problem Set 10
(a) Construct a probability model of the situation,State the inspectors’ determina-
tions and the Security Chief’s conclusion as probabilities,
Solution,Let the sample space S be a set of days and nights,De?ne the following
three events,
D = A secret document disappears
X = Agent X is at headquarters
A = It is daytime,
In these terms,Inspector AM says,
Pr (D ∩ X A) = Pr (D | A)· Pr (X A)| |
Inspect PM says,
Pr D ∩ X A = Pr D | A Pr X | A| ·
And the Security Chief concludes,
Pr (D ∩ X) = Pr (D)· Pr (X)
(b) Is the Security Chief’s reasoning correct? Justify your answer,
Solution,The security chief is wrong,For example,suppose that S consists of a
single day and a single night,
S = {day,night}
Assign night and day each probability 1/2,Now suppose that Agent X is around
during the night and a document disappears only at night,
D = {night}
X = {night}
A = {day}
Furthermore,suppose Pr (day) = Pr (night) = 1/2,These suppositions are consis-
tent with the inspectors’ determinations,
Pr (D ∩ X A) =
Pr (D ∩ X ∩ A)
= 0|
Pr (A)
Pr (D | A)· Pr (X A) =
Pr (D ∩ A) Pr (X ∩ A)
= 0|
Pr (A)
·
Pr (A)
Pr D ∩ X A =
Pr D ∩
X
∩ A
= 1|
Pr A
Pr X ∩ A
Pr D | A Pr X | A =
Pr D
∩
A
= 1·
Pr A
·
Pr A
?
5 Problem Set 10
However,the Security Chief’s conclusion is wrong,because:
Pr(D ∩ X) = Pr(night) = 1/2
But:
Pr(D)· Pr(X) = (1/2)· (1/2) = 1/4
So Agent X may be guilty after all!
Problem 5,Suppose you?ip n fair,independent coins,Let the random variable X be the
number of heads that come up,
(a) What is the exact value of Pr(X ≤ k),the probability of?ipping k or fewer heads?
Your answer need not be in closed form,
Solution.
n n n
+ +,.,+
k k?1 0
n
2
(b) Suppose k < n/2,Prove that,
n? k + 1
· Pr(X = k)Pr(X ≤ k) ≤
n? 2k + 1
(Upper bound your previous answer with an in?nite geometric sum and then eval-
uate the sum.)
Solution,We can upper bound the numerator in the preceding answer as follows,
n n n
+ +,.,+
k k? 1 0
n n
= +
k
n
+
k(k?1)
n
+
k(k?1)(k?2)
+,.,
n?k+1 (n?k+1)(n?k+2) (n?k+1)(n?k+2)(n?k+3)
k k k k
n k k
2
k
3
1 + + + +,.,≤
k
·
n? k + 1 (n? k + 1)
2
(n? k + 1)
3
n 1
=
k
k
·
1?
n?k+1
n n? k + 1
=
k
·
n? 2k + 1
(Note that the geometric sum converges only if k < n/2.) Therefore:
n? k + 1
Pr(X ≤ k) ≤
n? 2k + 1
· Pr(X = k)
6 Problem Set 10
(c) If you?ip a coin 100 times,the probability of?ipping exactly 30 heads is approx-
imately 23 out of a million,Give an upper bound on the probability of?ipping 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?rst 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,De?ne 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.)
7 Problem Set 10
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
De?ne 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 2
n
1 uniform,pairwise-independent 0-1 ran-
dom variables from a set of nuniform,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 a
1
XOR a
2
XOR,.,XOR a
n
is equal to (a
1
+ a
2
+,.,+ a
n
) rem 2.)
