CS70 Discrete Mathematics and Probability Theory, Fall 2018
Your First Name:
SIGN Your Name:
Your Exam Room:
Name of Person Sitting on Your Left:
Name of Person Sitting on Your Right: Name of Person Sitting in Front of You: Name of Person Sitting Behind You:
Instructions:
Your Last Name:
Your SID Number:
Midterm 2
8:00-10:00pm, 31 October
(a) As soon as the exam starts, please write your student ID in the space provided at the top of every page! (We will remove the staple when scanning your exam.)
(b) There are 6 double-sided sheets (11 numbered pages) on the exam. Notify a proctor immediately if a sheet is missing. Do not write any answers on page 12; it will not be scanned.
(c) We will not grade anything outside of the space provided for a question (i.e., either a designated box if it is provided, or otherwise the white space immediately below the question). Be sure to write your full answer in the box or space provided! Scratch paper is provided on request; however, please bear in mind that nothing you write on scratch paper will be graded!
(d) The questions vary in difficulty, so if you get stuck on any question it may help to leave it and return to it later.
(e) On questions 1-2: You must give the answer in the format requested (e.g., True/False, an expression, a statement.) An expression may simply be a number or an expression with a relevant variable in it. For short answer questions, correct, clearly identified answers will receive full credit with no justification. Incorrect answers may receive partial credit.
(f) On questions 3-6, you should give arguments, proofs or clear descriptions if requested. If there is a box you must use it for your answer.
(g) You may consult one two-sided “cheat sheet” of notes. Apart from that, you may not look at any other materials. Calculators, phones, computers, and other electronic devices are NOT permitted.
(h) You may, without proof, use theorems and lemmas that were proven in the notes and/or in lecture.
(i) You have 120 minutes: there are 6 questions on this exam worth a total of 128 points.
[exam starts on next page]
Your SID Number:
1. True/False [No justification; answer by shading the correct bubble. 2 points per answer; total of 26 points.
No penalty for incorrect answers.]
(a) Are the following sets countable? Answer YES or NO for each set by shading the appropriate bubble.
YES NO
n ~ ~ n n ~
~ n
~ n
The set of all functions from N to {0, 1}. 2pts The set of all finite subsets of N. 2pts The set of all irrational numbers in the interval [0, 1]. 2pts The set of all possible Google search terms. 2pts The set of all undirected graphs with a finite number of vertices. 2pts
(b) Answer each of the following questions TRUE or FALSE by shading the appropriate bubble. TRUE FALSE
~ n
~ n
~ n
Any two distinct polynomials, each of degree at most d, can have at most d points in common. 2pts
Every function over GF(p) can be represented as a polynomial of degree at most p − 1. 2pts
There exists a fixed computer program P such that no program can decide for any given input x 2pts whether P halts on x.
n ~ForanytwosetsAandB,ifthereexistsaninjectionf:A→Bandasurjectiong:B→A, 2pts then |A| = |B|.
~ nForanytwosetsAandB,ifthereexistsaninjectionf:A→Bandaninjectiong:B→A, 2pts then |A| = |B|.
~ n
~ n
n ~
For any two finite sets A and B, if there exists a surjection f : A → B such that |f−1(x)| = m 2pts for all x ∈ B, then |A| = m|B|. (Here f−1(x) denotes the preimage of x.)
Let A and B be events on the same probability space, and suppose P[A] = 3 and P[B] = 1 . Then 2pts
itmustbethecasethat 1 ≤P[A∩B]≤ 1. 42
Consider a fair coin and a biased coin. One of the two coins is chosen at random and tossed twice. 2pts The outcomes of the two tosses are independent.
42
Page 2
Your SID Number:
2. Short Answers [Answer is a single number or expression; write it in the box provided: anything outside the box will not be graded; no justification necessary. 3 points per answer; total of 45 points. No penalty for incorrect answers.]
(a) Suppose that P (x) is a real polynomial of degree 2 that has zeros at x = 0 and x = 2 and also passes 3pts through the point (1, 1). What is the value of P (3)?
−3. [SinceP isofdegree2andhaszerosat0and2,itmustbeoftheformP(x) = cx(x−2). Furthermore, P (1) = 1 implies c = −1. Hence, P (3) = −3(3 − 2) = −3.]
(b) How many polynomials over GF(17) of degree at most 5 pass through the points (0, 0), (1, 3) and 3pts (2, 5)? (You may leave your answer as an unevaluated expression.)
173. [A polynomial of degree at most five is fully determined by 6 points. Three are given, so we need to specify three more. For each of these three points, there are 17 possible values our polynomial can take.]
(c) A message consisting of n = 3 packets, each of which is an integer mod 11, is transmitted over an unreliable channel. We use the Berlekamp-Welch encoding scheme (over GF(11)) to protect against k = 1 error. The n + 2k = 5 packets received are (1, 1), (2, 2), (3, 0), (4, 2), (5, 8). After running the interpolation procedure, we recover the error polynomial E(x) = x − 1 and the product polynomial Q(x) = P (x)E (x) = 2×3 + 8×2 + 8x + 4. Answer the following two questions.
(i) Which one of the five received packets was (possibly) corrupted? 3pts (1, 1). [By definition, E(x) = x − e1 where e1 is the x-value of the possibly corrupted packet.]
(ii) What was the original value of the corrupted packet? 3pts (1, 8). [From polynomial division, we find that P (x) = Q(x)/E(x) ≡ 2×2 − x + 7 (mod 11),
andhenceP(1)≡2−1+7≡8 (mod 11).]
(d) Alice and Bob are playing poker using a standard deck of cards. How many ways are there to deal 5 3pts
cards each to Alice and Bob (where the order of the cards does not matter)?
5247, 5210, or the so-called multinomial coefficient 52 = 52! . [We first choose 5
5 5 10 5 42,5,5 42!5!5!
cards for Alice, and then choose 5 out of the remaining cards for Bob. Alternatively, we first choose 10 cards from the deck, and then choose five of those selected cards for Alice and give the remaining five to Bob.]
(e) How many permutations of {1, . . . , n} are there with exactly k fixed points, where 1 ≤ k < n? Ex- 3pts press your answer in terms of Dm, the number of derangements of {1, . . . , m}.
nDn−k . [We first need to choose the k fixed points, and then permute the remaining n − k points so k
that none is mapped to itself.]
[Q2 continued on next page]
Page 3
Your SID Number:
(f) Suppose a random number generator returns a number in {0, 1, . . . , 9} with uniform probability, and you run it 100 times to generate a 100-digit number (possibly with leading zeros).
(i) What is the probability that the 100-digit number contains the digit 7 more than 50 times? (You 3pts should leave your answer as a summation.)
100 100 1 k 9 100−k . [Each run of the random number generator samples 7 with prob- k=51 k 10 10
ability 1 and some number other than 7 with probability 9 , so the total number of 7’s in 100 10 10
trials is distributed as a Binomial(100, 1 ) random variable.] 10
(ii) What is the probability that the 100-digit number contains either no 0-digits or no 1-digits? (You 3pts should leave your answer as an unevaluated expression.)
2 · 9 100 − 8 100. [Let A and B respectively denote the event of observing no 0-digits and no 10 10
1-digits. Then, by the inclusion-exclusion principle, we obtain P[A∪B] = P[A]+P[B]−P[A∩B]. TheanswernowfollowsfromP[A]=P[B]=9 100 andP[A∩B]=8 100.]
(g) You have a fair 6-sided die, and also a loaded 6-sided die that shows 6 with probability 1/2 and 1, 2, 3, 4, 5 with probability 1/10 each. One of the two dice is chosen uniformly at random and rolled once. Let A be the event that 6 is observed.
(i) What is P[A]? 3pts 1 . Let B be the event that the biased die is chosen. Then, P[A] = P[A|B]P[B] + P[A|B]P[B] =
3
1 · 1 + 1 · 1 = 1. 22623
(ii) What is P[ Loaded die was chosen | A ]? 3pts 11
3
10 10
3. P[B|A]=P[A∩B]=22 =3. 4 P[A] 1 4
(h) Let X ∼ Bernoulli( 1 ) and let Y be a random variable with probability distribution P[Y = 1] = 1 and 3pts 22
P[Y = 2] = 1 . Assuming that X, Y are independent, find P[X < Y ]. 2
3. Theevent(X < Y)istheunionoftheevent(Y = 2)andtheevent(Y = 1)∩(X = 0). By 4
independence,P[(Y =1)∩(X=0)]=1·1 =1.Also,theevents(Y =2)and(Y =1)∩(X=0) 224
are disjoint. Hence, P[X < Y ] = P[Y = 2] + P[(Y = 1) ∩ (X = 0)] = 1 + 1 = 3 . 244
(i) Let X be a random variable with probability distribution P[X = −8] = 1, P[X = −4] = 1, 3pts
P[X = 4] = 1. Find E[2X]. 4
111 −6. E[2X]=2E[X]=2· −8·4 −4·2 +4·4 =−6.
42
[Q2 continued on next page]
Page 4
Your SID Number:
(j) Suppose m balls are thrown uniformly at random into n bins (one ball at a time). What is the expected 3pts number of bins that have exactly one ball in them?
m 1 − 1 m−1 . Let Ik n
n P[Ik =1]=n k=1 k=1
be the indicator that bin k has exactly one ball. Then, E[n Ik ] = k=1
m· 1 1− 1m−1. n n
(k) The problem Finite takes as input a program P and decides whether the set of inputs on which P loops 3pts forever is finite (or empty). The following pseudo-code gives a reduction from the Halting Problem,
Halt, to Finite. Fill in the blanks to make the reduction behave correctly.
Test-Halt(P,x)
let P’ be a program that, on every input, runs P on x
if Test-Finite(P’) then return "yes"
else return "no"
[P ′ halts on all inputs if and only if P (x) halts, so if Test-Finite(P’) returns “yes”, then P (x) halts, and if Test-Finite(P’) returns “no”, then P (x) does not halt.]
(l) We say that programs P1, P2 differ on input x if one of the programs halts and the other loops forever 3pts on x. The problem InfDiff takes as input two programs, P1 and P2, and decides whether there are infinitely many inputs x on which P1, P2 differ. The following pseudo-code gives a reduction from the Halting Problem, Halt, to InfDiff. Fill in the blank to make the reduction behave correctly.
Test-Halt(P,x)
let P1 be a program that, on every input, runs P on x
let P2 be a program that, on every input, loops forever if Test-InfDiff(P1,P2) then return "yes" else return "no"
[If P(x) loops forever then P1 loops forever on all inputs, and if P(x) halts then P1 halts on all inputs. Since P2 loops forever on all inputs, P1 and P2 will differ on infinitely many inputs if and only if P (x) halts.]
Page 5
Your SID Number:
3. Modifying Secrets [All answers to be justified. Total of 12 points.]
Alice sets up a secret sharing scheme with her n friends Bob1, . . . , Bobn, in which each Bobi gets a point (xi, yi) where yi = P (xi) for a fixed polynomial P over a field GF(q), where q > 2n. The secret is kept at P (0) = s. When Alice is distributing these points to the Bobs, an adversary Eve can tamper with the points, and thus change the value of the secret that will be recovered. For each scenario in (a)–(c) below, give the value of the new secret that will be recovered; your answers may depend on s or on P . In each case, prove that your answer is correct.
(a) Eve replaces each point (xi, yi) with (xi, 2yi + 1). 4pts
The recovered secret is : In the original scheme, a subset of k of the Bobs would reconstruct the unique polynomial P (x) of degree at most k − 1 passing through k of the points
(xi, yi), for some k. After tampering, the Bobs reconstruct instead the unique polynomial Q(x) (over GF(q)) of degree at most k − 1 that passes through the points (xi, 2yi + 1); and we can see that Q(x) = 2P (x) + 1 since both of these polynomials have degree at most k − 1 and agree on k points: Q(xi ) = 2yi + 1 = 2P (xi ) + 1; so they must be the same polynomial. To recover the secret, the Bobs compute Q(0) = 2P (0) + 1 = 2s + 1.
An alternative (more complicated) approach is to use Lagrange interpolation. Assuming w.l.o.g. that the Bobs who are doing the reconstruction are labeled i = 1, . . . , k, they will reconstruct a polynomial Q of degree at most k − 1 via
k
Q(x) = (2yi + 1)∆i(x), (1)
2s + 1 (mod q)
i=1
where as usual the basis polynomials are given by ∆i(x) = j̸=i(xi−xj). Now notice that (1) can be
written
kkk
Q(x) = 2 yi∆i(x) + ∆i(x) = 2P (x) + ∆i(x), (2)
i=1 i=1 i=1
where we have noticed that the first sum is exactly the Lagrange interpolation formula for P itself. Finally, notice that the polynomial ki=1 ∆i(x) has degree at most k − 1 (since Q has), and takes the value 1 at all k points x1, . . . , xk (since at those points Q(xi) = 2P (xi) + 1). Hence this polynomial must be the constant polynomial 1. We can now deduce from (2) that Q(x) = 2P (x) + 1, from which the Bobs get the new secret Q(0) = 2s + 1.
(b) Eve replaces each point (xi, yi) with (2xi, yi). 4pts
The recovered secret is : Write the polynomial P (x) = ak−1xk−1 +ak−2xk−2 +· · ·+a1x+a0, and note that a0 = P (0) = s. Recall that this polynomial passes through the points (xi , yi ), so P (xi ) = yi . Now consider the polynomial Q(x) = 2−(k−1)ak−1xk−1 + 2−(k−2)ak−2xk−2 + · · · + 2−1a1x + a0, where all inverses are mod q. We claim that this polynomial passes through Eve’s new points (2xi, yi): to see this, just substitute x = 2xi to get Q(2xi) = P(xi) = yi. Hence this is the unique polynomial of the same degree as P through these points, and so it must be the polynomial reconstructed by the Bobs. The new secret value is then Q(0) = a0 = s.
Again, it is possible (but messier) to approach this via Lagrange interpolation. Unlike in part (a), where the basis polynomials ∆i are unchanged from those for the original polynomial P (x) (because the xi values are the same), now the Bobs are using new basis polynomials as follows:
j̸=i(x − 2xj ) ∆i(x) = j̸=i(2xi − 2xj).
j ̸=i (x−xj )
s
Page 6
Your SID Number:
These polynomials are quite complicated, but when they are evaluated at x = 0 (the secret point) they become much simpler:
j ̸=i (−2xj ) j ̸=i (−xj ) ∆i(0) = j̸=i(2xi − 2xj) = j̸=i(xi − xj).
And these are exactly the same as the basis polynomials for P (x) itself, when evaluated at x = 0! Moreover, the values yi are unchanged. Hence, at the point x = 0, the new polynomial Q(x) obtained by the Bobs will have exactly the same value as P (x), i.e., Q(0) = P (0) = s.
(c) Evereplaceseachpoint(xi,yi)with(xi−1,yi).[Youmayassumethatxi ̸=1foralli=1,…,n.] 4pts
The new secret is : We claim that now the polynomial reconstructed by the Bobs is Q(x) = P (x + 1). To see this, note that Q(x) is a polynomial of degree at most k − 1 (since P is), and that
it passes through k points of the form (xi − 1, yi) held by the Bobs, since Q(xi − 1) = P (xi) = yi. Hence this Q(x) must be the polynomial reconstructed by the Bobs, and so they evaluate the secret as Q(0) = P (1).
P (1)
Page 7
Your SID Number:
4. Breaking RSA [All parts to be briefly justified. Total of 16 points.]
(a) Alice sends the same message, m < N , to two friends, Bob and Carol using the standard RSA protocol 4pts discussed in class. Bob’s public key is (N, e1) and Carol’s is (N, e2), where gcd(e1, e2) = 1. Explain
how an eavesdropper, Eve, can decrypt m by observing the encrypted messages that Alice sends to
Bob and Carol. [Hint: Use the extended gcd algorithm.]
Since gcd(e1,e2) = 1, Eve can use the extended gcd algorithm to efficiently find a,b ∈ Z such that ae1 + be2 = 1. Observing me1 and me2 , she can then proceed to compute (me1 )a · (me2 )b ≡ mae1 · mbe2 ≡ mae1+be2 ≡ m (mod N).
(b) Dennis decides to simplify the RSA cryptosystem as follows. Instead of choosing the usual type of 4pts public key (N = pq, e), he instead chooses a key (N, e) where N is a prime and e is an integer in {2,...,N − 1} with gcd(N − 1,e) = 1. To send a message m to Dennis, Alice sends the encrypted messageme (modN).IsDennis’schemesecure?Explainyouranswer.
No, Dennis’ scheme is not secure. Since e is relatively prime to N − 1, Eve can efficiently com- pute the inverse e−1 mod (N − 1) (using the extended gcd algorithm). Furthermore, since ee−1 ≡ 1 (modN−1),itmustbethecasethatee−1 =k(N−1)+1forsomek∈Z,andconsequently Eve can compute (me)e−1 ≡ mee−1 ≡ mk(N−1)+1 ≡ mN−1k · m ≡ m (mod N), where the last congruence follows from Fermat’s Little Theorem.
[Q4 continued on next page]
Page 8
Your SID Number:
(c) Frank has published his RSA public key (N = pq, e). Gina wants to construct her own public key, and 4pts has found one large prime p′ ̸= p; being too lazy to find another one, she asks if she can use one of Frank’s; since Frank trusts Gina, he gives her his prime q. Gina then publishes her key (N′ = p′q,e′). Explain how Eve is able to break both Frank’s and Gina’s RSA schemes.
Since p′ ̸= p, Eve can run Euclid’s algorithm to compute gcd(N,N′) = q, and then obtain p = N/q and p′ = N′/q. Knowing p, p′ and q, she can then proceed to compute Frank’s and Gina’s private keys dandd′throughd≡e−1 (mod(p−1)(q−1))andd′≡(e′)−1 (mod(p′−1)(q−1))(againusing the extended gcd algorithm).
(d) Harry, Imogen and Jasper have RSA public keys (NH,3), (NI,3) and (NJ,3) respectively, where 4pts NH,NI,NJ arealldistinct. Alicesendsthesamemessagem(wheremislessthanallofNH,NI,NJ)
to all three of them using their respective keys. Explain how Eve is able to decrypt this message by observing the three encrypted messages. [Hints: You may use without proof the Chinese Remainder Theorem, which says the following: Let n be a natural number. Given the values ci = n mod ri, for
1 ≤ i ≤ k, where the ri are coprime, we can efficiently compute the value c = n mod (r1r2 ...rk). You may also use the fact that the cube root of an integer can be found efficiently.]
If NI,NH and NL are not pairwise coprime, then Eve can apply her results from part (c) to find m, so let us assume that NI,NH,NL are pairwise coprime. Letting mI,mH,mL denote the three encrypted messages Eve observes, she may apply the Chinese remainder theorem on
mI =m3 mH =m3 mL = m3
modNI, modNH, mod NL,
to efficiently obtain m3 mod (NI · NH · NL). Since we are given that m < min(NI , NH , NL), we knowthatm3 < NI ·NH ·NL,andhencem3 mod(NI ·NH ·NL)isactuallyequaltom3 (as integers—no mod!). So, all Eve needs to do is take a cube root over the integers, which we are told can be done efficiently. (This is actually not too hard to see: e.g., we can perform a binary search, at each iteration checking whether the current element cubed is m3 or not; the binary search takes at most log(NI NH NL) iterations, and each multiplication takes O(log2(NI NH NL)) steps. Note in contrast that computing cube roots mod p has no known efficient algorithm!)
Page 9
Your SID Number:
5. Counting Team Compositions [All parts to be briefly justified. Total of 16 points.]
UC Berkeley has n students who are interested in participating in both the CS Programming and the Putnam Mathematical competitions. In parts (a) and (b), count the number of ways to choose a CS team with c members and a Putnam team with p members under the specified constraint, assuming that n ≥ c + p.
Whenever possible, express your answers in terms of binomial coefficients and clearly indicate how each coefficient arises.
(a) No restriction; any student can be on both teams. 4pts There are exactly n ways of choosing the CS team, and n ways of choosing the Putnam team.
Since neither choice affects the other, we have an overall number of
nn cp
possibilities to choose both a CS team and a Putnam team.
cp
(b) No student can be on both teams. 4pts There are n possibilities to assemble the CS team. The Putnam team now has to be formed from
c n−c
the remaining n − c students, which we can do in p ways. Consequently, there are a total of
nn − c nn − p c p or equivalently p c
ways of choosing a CS team and a Putnam team without any overlap. Other correct solutions include n c+p and n c+p, which correspond to first selecting c + p students, and then dividing them
c+p c c+p p
into a CS team and a Putnam team.
(c) Let An,c,p denote the number of ways to choose the teams as in part (a), and let Bn,c,p denote the 4pts number of ways to choose the teams as in part (b). Fill in the blank in the equation below to produce a
valid combinatorial identity, and briefly explain your reasoning.
min(c,p) n
An,c,p = Bn−j,c−j,p−j
In order to choose CS and Putnam teams with overlap, we may first choose j students who should be on both teams, and then out of the remaining n − j students assign c − j and p − j to the respective teams without overlap.
(d) The CS team wins an international programming contest and receives k gold coins as a prize. How 4pts many ways are there to divide up the coins among the c team members, under the condition that each student should receive at least three coins? (Assume that k > 3c.)
After we have assigned each member 3 coins, we are left with k − 3c coins that we have to dis-
tribute among the students on the CS team. This is a balls and bins problem with n = k − 3c balls and
k = c bins, for which we know the answer to be k−2c−1. c−1
j=0 j
Page 10
Your SID Number:
6. Noisy Transmission on a Binary Tree [All parts to be justified. Total of 13 points.]
or
Consider a binary tree of depth D, which has 2D leaves; in the example shown above, D = 4. At the root of the tree is a single bit (0 or 1). This bit is transmitted separately to each of the two children of the root, but in each case the value of the bit is flipped (i.e., 0 → 1 or 1 → 0) independently with probability p. This process continues, with each vertex of the tree transmitting its bit value (flipped with probability p, independently of all other transmissions) to its two children. The process stops at the leaves.
Suppose two distinct leaves a, b are chosen uniformly at random. Let T denote the height of the lowest common ancestor (LCA) of a and b; in the example above, T = 1 for (a, b) = (1, 2), while T = 3 for (a, b) = (1, 8).
(a) Find a formula for the probability P[T = t], where t = 1, . . . , D, for a general binary tree of depth D. 5pts
LetΩbethesetofallpairsofleavesandEt ⊂ΩtheeventthatT =t. ThenP[T =t]=P[Et]= |Et|/|Ω|. Now in order for Et to happen, a and b must have an LCA at height t. Let us denote byHt thesetofverticesatheightt,andbyAv theeventthataandbhaveLCAv ∈ Ht. Then Et = ∪v∈Ht Av, and since the Av are mutually disjoint, |Et| = v∈Ht |Av| = |Ht||Aw| = 2D−t|Aw|, where w is any vertex in Ht and the second equality follows from the fact that |Av| = |Av′| for any v, v′ ∈ HD by symmetry. To compute |Aw| we note that w subtends two sub-trees of size 2t−1 each, from which it follows that there are exactly 2t−1 · 2t−1 = 22t−2 pairs of leaves whose LCA is w. So |Et| = 2D−t · 22t−2 = 2D+t−2, which combined with |Ω| = 2D−1 2D − 1 yields
2D−1 · 2t−1 2t−1 P[T =t]= 2D−1(2D −1) = 2D −1.
Alternative Solution: Instead of thinking of {a, b} as an unordered pair like we did above, we may think of it as the ordered pair (a,b). Then conditional on fixing a = i ∈ {1,…,2D}, looking at the unique vertex v ∈ Ht that subtends a, we see that in order for T = t, leaf b must be inside the sub-tree subtended by v that does not contain a. That sub-tree has exactly 2t−1 leaves, and so P[T =t|a=i]= 2t−1 .Thenbythelawoftotalprobability:
0
1
P[T =t]=
i=1
P[(T =t)∩(a=i)]=
i=1
2t−1
2D −1
2D 2D 2D
2t−1 P[a=i]= 2D −1.
P[T =t|a=i]P[a=i]= 2D −1
i=1
(b) Let M denote the total number of times the bit is flipped when traversing the tree from the LCA to 3pts leaf a plus the analogous number of bit flips from the LCA to b. Write down a formula for the condi-
tional probability P[M = m | T = t]. Be sure to specify what values of m are possible.
On the event Et, a and b are each connected to their LCA by a path of length exactly t. That is, there are a total of 2t distinct edges along which bit flips may contribute to M . Let us denote the set of these edges by Ea,b, and call Fe, e ∈ Ea,b the indicator variable that is 1 if a bit flip occurred across edge e and 0 otherwise. Then M = e∈Ea,b Fe, and since the Fe are independent Bernoulli(p) variables,
Page 11
Your SID Number:
the conditional distribution of M given T = t is Binomial(2t, p). So, 2t m 2t−m
P[M=m|T=t]= m p (1−p) , (3)
(c) Now let the random variables Ba and Bb respectively denote the bits observed at the sampled leaves a 2pts
for m = 0,1,…,2t.
and b. What condition on M guarantees that Ba = Bb?
If Ba = Bb, then either Ba and Bb both differ from the bit at LCA(a,b), or they are both equal to the bit at LCA(a, b). The former case can happen if only if there are an odd number of flips on the path between a and LCA(a, b), and also an odd number of flips on the path between b and LCA(a, b). The latter case occurs if and only if there are an even number of bit flips on both paths. Therefore Ba =Bb ifandonlyifM iseven.
(d) Find a formula for P[Ba = Bb]. You may leave your answer as an unevaluated expression. [Hints: 3pts Use parts (b) and (c) to compute P[Ba = Bb | T = t], then combine with part (a).]
By the law of total probability and part (c), we know that
D
P[Ba = Bb] = P[T = t] · P[M is even | T = t].
t=1
Plugging in our results from part (a) for P[T = t] and Equation (3) for P[M = m | T = t], we thus
obtain
Dt
2t−1 P[Ba=Bb]= 2D−1
t=1
2t 2k 2(t−k)
2k p (1−p) . (4) k=0
Aside (For interested students only; not needed to receive full credit): We can actually compute P[Ba = Bb] in closed form. First, noting
t 2t t−1 2t
[(1 − p) + p]2t = k=0
p2k(1 − p)2(t−k) + p2k+1(1 − p)2(t−k)−1, (5)
[(1 − p) − p]2t = k=0
2k
t 2t
2k + 1 t−1 2t
k=0
p2k(1 − p)2(t−k) − p2k+1(1 − p)2(t−k)−1, (6)
2k + 1
P[Miseven |T=t]=1[1+(1−2p)2t]. 2
Then, using this result, (4) can be simplified as
2k
we see that adding (5) and (6), and then dividing by 2 gives
x(xD −1)
where x := 2(1 − 2p)2. See Figure 1 for illustration of P[Ba = Bb] as a function of p. For all D, note
thatP[Ba =Bb]= 1 atp= 1,whileP[Ba =Bb]=1atp=0andp=1.AsDincreases,theinterior 22
1
P[Ba=Bb]=2 1+2(x−1)(2D−1) ,
k=0
Page 12
Your SID Number:
region with P[Ba = Bb] = 1 enlarges, and transitions from P[Ba = Bb] = 1 to P[Ba = Bb] = 1 near 22
p = 0 and p = 1 become sharper and sharper. This makes intuitive sense, since T grows linearly with D in expectation more precisely, E[T ] = D − 1 − D , and when tossing a coin sufficiently many
2D −1
times, regardless of how biased it is, the chance of observing an even number of heads is roughly the
same as the chance of observing an odd number of them.
1.0 0.8 0.6 0.4 0.2 0.0
0.0 0.2 0.4
1.0 0.8 0.6 0.4 0.2 0.0
0.0 0.2 0.4
D=2
0.6 0.8 1.0
D = 20
p
0.6 0.8 1.0
D = 200
1.0 0.8 0.6 0.4 0.2 0.0
0.0 0.2 0.4
Figure 1: Plots of P[Ba = Bb] as a function of p for D = 2,20, and 200.
p
p
0.6 0.8 1.0
Page 13
Pr[Ba =Bb ] Pr[Ba =Bb ] Pr[Ba =Bb ]