6.856 — Randomized Algorithms David Karger Handout #16, October 27, 2002 — Homework 7 Solutions Problem 1 (a) We let each machine broadcast independently with probability 1/n. Then the probability that exactly one machine tries to broadcast in a given timeslot is equal to � 1 �n−1 � � 1 1 n · n · n = Θ ,1 − e i.e. larger than some constant independent of n. (b) From (a) we know that the expected time until some machine is successful is Θ(e). Since the problem is symmetric in all n machines, the successful machine is equally likely to be any of the machines. This is also true for the next successful machine, and so on. So the question is how long it takes for all machines to be successful, if every Θ(e) steps, a random machine is successful. This is just the coupon collectors problem: we expect Θ(n ln n) successful broadcasts before every machine actually sent their first packet. So the expected time for all machines to be successful is Θ(ne ln n). (c) The probability that a machine is successful in a particular slot is equal to the probability that a) the machine tries to broadcast, and b) nobody else tries to broadcast. Since the machines decide on broadcasts independently, there probabilities are also independent, and therefore � 1 �n−1 � � 1 1 Pr[machine successful] = n · 1 − n = Θ ne So over s time slots, the expected number of successful broadcasts is Θ(s/ne) = c · s/ne (for some c > 0). Using Chernoff, we can estimate the probability that the machine is successful less than half that number of times: Pr[sucessful ≤ cs/(2ne) times out of s] ≤ exp(−cs/(8ne)) = αs/n for some α < 1. This shows high probability in terms of increasing s. (d) We use 2-point-sampling to determine when a machine gets to go. For simplicity, assume that m is prime (all of the following is still true if we replace m by some prime in the 1� interval [m, 2m]). Assume that Aethernet broadcasts 2�log m� bits that encode two random numbers a, b ∈ Zm. Then every machine takes its serial number s, and computes as + b mod m. If that quantity falls in the interval [0, m/2n], the machine broadcasts, otherwise it stays silent. Let’s analyze the probability that some particular machine broadcasts successfully. This is equal to Pr[our machine tries to broadcast] Pr[no other machine tries to broadcast | our machine tries to broadcast]. · The first probability is obviously 1/2n, since as + b mod m is equally likely to be any number between 0 and m−1. But since 2-point-sampling generates pairwise independent samples for two different machines, the probability that any other given machine tries to broadcast given that our machine tries to broadcast, is also 1/2n. Therefore the expected number of other machines that tries to broadcast is ≤ (n − 1)/2n ≤ 1/2. By Markov’s inequality, that implies that the probability that at least one machine tries to broadcast (given that our machine tries to broadcast) is at most 1/2. This show that our machine successfully broadcast with probability at least 1/2n · 1/2 = 1/4n. Since the events of a successful broadcast are disjoint for different machines, the probability that some machine successfully broadcasts is n · 1/4n = 1/4 = Ω(1). (e) We just saw that if we pick the 2-point-sampling pair (a, b) at random, we obtain a pair that allows for a successful broadcast with probability 1/4. But suppose we now generate those pairs (a, b) using two point sampling. This can be done by picking a prime p slightly larger than m2, picking two seeds u, v ∈ Zp, and generating pairs as (ai, bi) = (�αi/m�, αi mod m), where αi = (ui + v mod p). We set i = 0 at the beginning of the protocol and then increase its value by one at every time slot (i.e. every machine keeps track of the current i). So the pairs (ai, bi) can be generated by each machine just given the initial broadcast of u and v, which uses about 4 log m bits. Since the (ai, bi) are chosen pairwise independently, we can use Chebyshev to determine the number of times a successful broadcast occurs over time. Consider one particular machine, and assume it wants to transmit during s time slots. In part (d) we determined, that it succeeds with probability 1/4n in each time slot, so the expected number of transmissions is s/4n. The variance of that distribution is n(1/4n)(1 − 1/4n) < 1/2. Using Chebyshev, we see that the probability of sending out at least s/8n broadcasts can be bounded by 1 16n2 Pr[ #broadcasts − s/4n ≥ s/8n] =(s/4n)2 = . 2| | sThis is a high probability is terms of growing s. 2Problem 2 (a) Every vertex gets deleted with probability 1/d, so we expect n/d vertices to remain. An edge does not get deleted if both endpoints do not get deleted, which happens with probability 1/d2 . Obviously, the events of edges getting deleted are not independent, but by linearity of expectation, be expect (1/d2) · (nd/2) = n/2d edges to remain. (b) After applying this sampling, we create an independent set as follows: for each edge in the resulting graph, delete one of the endpoints. After doing this for each edge, none of the remaining vertices are connected by any edges, i.e. form an independent set. If G� is the graph we obtain after sampling, we the expect the size of the independent set to be E[size of independent set] = E[# vertices in G� − # edges in G�] = E[# vertices in G�] − E[# edges in G�] = n/d− n/2d = n/2d. Since there will be at least one outcome with a value equal to (or greater than) the expectation, there must be an independent set of size ≥ n/2d. (c) Suppose the vertices are labeled 1, 2, . . . , n. Then we go through the vertices in this order, and compute the expected sizes of the independent set depending on whether we pick vertex i or not, given the choices we already made for vertices 1, 2, . . . , i− 1. If we always choose the higher of the two values, then the method of conditional expectations guarantees that the independent set we finally end up with has size at least n/2d – the expected value. As seen above, to compute the expected size of the independent set, we have to compute the expected number of nodes and edges in our final sample – the size of the independent set is equal to their difference. The expected number of nodes is easy to determine: suppose we picked k nodes among the set {1,