Massachusetts Institute of Technology Handout 61 6.042J/18.062J: Mathematics for Computer Science December 4, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 10 Solutions

Problem 1. (15 points) Compute the probabilities of the following three events and determine which one is most likely. Assume that the dice are fair, 6-sided, and mutually independent.

(a) Rolling at least one 6 when six dice are rolled.

The probability of rolling a 6 on a particular die is \frac{1}{6}. The probability of not rolling a 6 on a particular die is \frac{5}{6}, since this is the complementary event. The probability of not rolling a 6 on any of six dice is (\frac{5}{6})^{6}, since the numbers rolled are mutually independent. The probability of rolling a 6 on some die is therefore 1 − (\frac{5}{6})^{6} = 0.665 . . ..

(b) Rolling at least two 6’s when twelve dice are rolled.

The probability of rolling two or more 6’s is 1 minus the probability of rolling zero or one 6’s. The probability of rolling zero 6’s is (\frac{5}{6})^{12}, arguing as before. The probablity of rolling exactly one 6 is

12 · \frac{1}{6} · (\frac{5}{6})^{11}

since there are 12 ways to choose the die that comes up 6, the probability of this die coming up 6 is \frac{1}{6}, and the probability of the remaining dice all coming up in the range 1 to 5 is (\frac{5}{6})^{11}. Overall, the probability of rolling two or more sixes is therefore

1 − (\frac{5}{6})^{12} − 12 · \frac{1}{6} · (\frac{5}{6})^{11} = 0.618 ….

(c) Rolling at least three 6’s when eighteen dice are rolled.

Arguing as before, the probability of rolling at least three 6’s is

1 − (\frac{5}{6})^{18} − 18 · \frac{1}{6} · (\frac{5}{6})^{17} − \binom{18}{2} · (\frac{1}{6})^{2} · (\frac{5}{6})^{16} = 0.597 ….

The first event is most likely.

Problem 2. (15 points) Let random variables X and Y be the outcomes of two dice rolls. Assume that the dice are fair, 6-sided, and independent. Each problem part below lists two random variables derived from X and Y. State whether or not these two random variables are independent and briefly sketch a justification for your answer.

(a) X and Y^{2}

These random variables are independent. For all x, y,

Pr(X = x ∩ Y^{2} = y) = Pr(X = x ∩ Y = \sqrt{y})
= Pr(X = x) · Pr(Y = \sqrt{y})
= Pr(X = x) · Pr(Y^{2} = y)

The second equation uses the independence of X and Y.

(b) X + Y and X − Y

These random variables are not independent. For example:

Pr(X + Y = 2) = \frac{1}{36}
Pr(X − Y = 0) = \frac{1}{6}
Pr(X + Y = 2 ∩ X − Y = 0) = \frac{1}{36}
≠ \frac{1}{36} · \frac{1}{6}

(c) ⌊\frac{X−1}{2}⌋ + ⌊\frac{Y −1}{2}⌋ and (X mod 2) + (Y mod 2)

These random variables are independent. The quantities ⌊\frac{X−1}{2}⌋ and (X mod 2) are independent, and so are the analogous expressions involving Y.

Pr (⌊\frac{X − 1}{2}⌋ = a) = \frac{1}{3}  a ∈ \{0, 1, 2\}
Pr (X mod 2 = b) = \frac{1}{2}  b ∈ \{0, 1\}
Pr (⌊\frac{X − 1}{2}⌋ = a ∩ X mod 2 = b) = \frac{1}{6}  a ∈ \{0, 1, 2\}, b ∈ \{0, 1\}
= \frac{1}{3} · \frac{1}{2}

Thus, the above expressions involve four mutually independent random variables; two are summed in the first expression and two are summed in the second. Consequently, the two expressions are independent.

Problem 3. (15 points) Let S and T be independent random variables with a countable range R. Let g be a function with domain and range R. Prove that S and g(T) are independent.

We must prove that for all x, y ∈ R,

Pr(S = x ∩ g(T) = y) = Pr(S = x) · Pr(g(T) = y).

Let g^{−1}(y) be the set of all values that the function g maps to y. Then the event that g(T) = y is identical to the event that T ∈ g^{−1}(y).

Pr (S = x ∩ g(T) = y) = Pr (S = x ∩ T ∈ g^{−1}(y))
= Pr (S = x ∩ ( ⋃_{z∈g^{−1}(y)} T = z))

= Pr ( ⋃_{z∈g^{−1}(y)} (S = x ∩ T = z))
= ∑_{z∈g^{−1}(y)} Pr (S = x ∩ T = z)
= ∑_{z∈g^{−1}(y)} Pr(S = x) · Pr(T = z)
= Pr(S = x) · ∑_{z∈g^{−1}(y)} Pr(T = z)
= Pr(S = x) · Pr(T ∈ g^{−1}(y))
= Pr(S = x) · Pr(g(T) = y)

The third step uses the fact that set intersection distributes over set union. The independence of S and T is used in the fifth step.

Problem 4. (20 points) In this problem, we consider various approaches to preserving and magnifying randomness.

A random bit is a random variable taking on only the values 0 and 1. An unbiased random bit takes on the values 0 and 1 with equal probability. Let x and y be bits. The expression x XOR y is called the exclusive-or of x and y. This expression is equal to 0 if x = y and equal to 1 if x ≠ y.

(a) Prove that the XOR of an unbiased random bit and an arbitrarily biased random bit is an unbiased random bit. Assume that the two bits are independent.

Let x be an unbiased random bit, and let y be random bit that is equal to 0 with probability p.

Pr(x XOR y = 0) = Pr(x = 0 ∩ y = 0) + Pr(x = 1 ∩ y = 1)
= Pr(x = 0) · Pr(y = 0) + Pr(x = 1) · Pr(y = 1)
= \frac{1}{2} · p + \frac{1}{2} · (1 − p)
= \frac{1}{2}

(b) Prove that there is no function mapping two unbiased, independent random bits to three unbiased, mutually-independent random bits.

Assume for the purpose of contradiction that such a function exists. The event that both input bits are equal to zero occurs with probability \frac{1}{4}. In this event, the three output bits take on some values. This implies that the three output bits take on these values with probability at least \frac{1}{4} and not \frac{1}{8}, which contradicts the assumption that the three output bits are unbiased and mutually independent.

(c) Describe a function mapping two unbiased, independent random bits to three unbiased, pairwise-independent random bits. No proof is necessary.

Let a and b be unbiased, independent bits. Then x = a, y = b, and z = a XOR b are unbiased, pairwise-independent bits.

Problem 5. (5 points) Let the random variable R be equal to the number of heads that come up when four mutually independent, fair coins are flipped.

(a) Compute the probability distribution function for R. That is, determine Pr(R = k) for all k.

Pr(R = 0) = \frac{1}{16}
Pr(R = 1) = \frac{4}{16}
Pr(R = 2) = \frac{6}{16}
Pr(R = 3) = \frac{4}{16}
Pr(R = 4) = \frac{1}{16}

(b) Compute the cumulative distribution function for R. That is, find Pr(R ≤ k) for all k.

Pr(R ≤ 0) = \frac{1}{16}
Pr(R ≤ 1) = \frac{5}{16}
Pr(R ≤ 2) = \frac{11}{16}
Pr(R ≤ 3) = \frac{15}{16}
Pr(R ≤ 4) = \frac{16}{16}

Problem 6. (20 points) 6.042 TA Alex Duran is teaching Theory Pig a fun new game. Theory Pig is very excited because he finally has a friend who will “play nice”. Here is how the game works. Alex repeatedly flips a fair coin. If the sequence HT T comes up on three consecutive throws, then the game is over and Theory Pig wins. However, if the sequence HHT comes up on three consecutive throws, then the game is over and Alex wins. Though the game seems completely fair, Theory Pig is still a slightly suspicious of Alex because of an earlier duct tape incident.

Find the probability that Theory Pig wins the game; that is, find the probability that the sequence HT T appears before the sequence HHT in a sequence of fair coin tosses.

Let p be the probability that HT T appears before HHT. For the first two flips, the sequences HH, HT, T H, and T T are equally likely. Let p_{xy} be the probability that the sequence HT T appears before the sequence HHT, given that the two most recent flips were x and y. Therefore, we have:

p = \frac{1}{4}(p_{HH} + p_{HT} + p_{T H} + p_{T T})

We can interrelate the four variable on the right side of this equation by considering the outcome of the next flip. For example, suppose the last two flips were HT. With probability \frac{1}{2}, the next flip is a T. Conditioned on this sequence of flips, HT T appears before HHT with probability 1. On the other hand, with probability \frac{1}{2}, the next flip is H. In this case, HT T appears before HHT with probability p_{T H}, since the last two flips were T H. This reasoning gives the equation p_{HT} = \frac{1}{2} + \frac{1}{2}p_{T H}. By similar arguments, we obtain the following system of linear equations.

p_{HH} = \frac{1}{2} · 0 + \frac{1}{2} · p_{HH}
p_{HT} = \frac{1}{2} · 1 + \frac{1}{2} · p_{T H}
p_{T H} = \frac{1}{2} · p_{HT} + \frac{1}{2} · p_{HH}
p_{T T} = \frac{1}{2} · p_{T T} + \frac{1}{2} · p_{T H}

The solution to this system is p_{HH} = 0, p_{T H} = \frac{2}{3}, p_{T H} = \frac{1}{3}, and p_{T T} = \frac{2}{3}. Substituting these four values into the first equation gives p = \frac{1}{3} for Theory Pig’s chance of winning the game.

There are at least two alternative approaches. First, one could find the set of all winning outcomes for one player and sum the probabilites of these outcomes. Second, one could find the sets of winning outcomes for both players and show that one has twice the probability of the other.

Problem 7. (10 points) The 6.042 staff received the following comment about the midterm exam.

From: grzzwk@xoros19.gammaquad.plnt
To: 6042-staff@theory.lcs.mit.edu
Subject: midterm exam
Thank you for announcing our state military secrets on your midterm
exam.
Well, you might as well know that each of our ferocious Tostitomatics
has a million components.  True, each component has a 50% chance of

failing during the arduous flight from Xoros 19 to Earth.  However,
failures occur mutually independently, and only 51% of the components
must remain functional for a Tostitomatic to survive the journey.
Clearly the number of component failures on a typical Tostitomatic
will be right around 50%--- maybe a bit more, maybe a little less.
Since the number of compoments that must remain functional is also
very close to 50%, obviously about half of our massively armed
Tostitomatics will entering earth orbit shortly.  Won't that be fun!
\Grzzwk

Give a good estimate of the probability that a Tostitomatic survives the journey.

A Tostitomatic survives the journey if at most 49% of the components fail. This is equal to F_{1000000, \frac{1}{2}} (0.49n), where F is the cumulative distribution function for the binomial distribution. We use the following bound and approximation:

F_{n,p}(αn) ≤ \frac{1 − α}{1 − \frac{α}{p}} · f_{n,p}(αn)

f_{n,p}(αn) ≈ \frac{2^{(α log_{2}(\frac{p}{α})+(1−α) log_{2}(\frac{1−p}{1−α}))·n}}{\sqrt{2πα(1 − α)n}}

By substitution, the probability that a Tostitomatic survives the journey is about 2.78·10^{−89}.