Algorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne13. Randomized Algorithms2RandomizationAlgorithmic design patterns.! Greed.! Divide-and-conquer.! Dynamic programming.! Network flow.! Randomization.Randomization. Allow fair coin flip in unit time.Why randomize? Can lead to simplest, fastest, or only knownalgorithm for a particular problem.Ex. Symmetry breaking protocols, graph algorithms, quicksort,hashing, load balancing, Monte Carlo integration, cryptography.in practice, access to a pseudo-random number generatorAlgorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne13.1 Contention Resolution4Contention Resolution in a Distributed SystemContention resolution. Given n processes P1, …, Pn, each competing foraccess to a shared database. If two or more processes access thedatabase simultaneously, all processes are locked out. Devise protocolto ensure all processes get through on a regular basis.Restriction. Processes can't communicate.Challenge. Need symmetry-breaking paradigm.P1P2Pn...5Contention Resolution: Randomized ProtocolProtocol. Each process requests access to the database at time t withprobability p = 1/n.Claim. Let S[i, t] = event that process i succeeds in accessing thedatabase at time t. Then 1/(e ! n) $ Pr[S(i, t)] $ 1/(2n).Pf. By independence, Pr[S(i, t)] = p (1-p)n-1.! Setting p = 1/n, we have Pr[S(i, t)] = 1/n (1 - 1/n) n-1. !Useful fact. As n increases from 2, the function:! (1 - 1/n)n-1 converges monotonically from 1/4 up to 1/e! (1 - 1/n)n-1 converges monotonically from 1/2 down to 1/e.process i requests accessnone of remaining n-1 processes request accessvalue that maximizes Pr[S(i, t)]between 1/e and 1/26Contention Resolution: Randomized ProtocolClaim. The probability that process i fails to access the database inen rounds is at most 1/e. After e!n(c ln n) rounds, the probability is atmost n-c.Pf. Let F[i, t] = event that process i fails to access database in rounds1 through t. By independence and previous claim, we havePr[F(i, t)] $ (1 - 1/(en)) t.! Choose t = "e ! n#:! Choose t = "e ! n# "c ln n#: ! Pr[F (i, t)] " 1#1en( )en$ % " 1#1en( )en " 1e ! Pr[F (i, t)] " 1e( )c ln n = n#c7Contention Resolution: Randomized ProtocolClaim. The probability that all processes succeed within 2e ! n ln nrounds is at least 1 - 1/n.Pf. Let F[t] = event that at least one of the n processes fails toaccess database in any of the rounds 1 through t.! Choosing t = 2 "en# "c ln n# yields Pr[F[t]] $ n · n-2 = 1/n. ! Union bound. Given events E1, …, En, ! Pr Eii=1nU" # $ % & ' ( Pr[ Ei]i=1n) ! Pr F [t][ ] = Pr F [i , t ]i=1nU" # $ % & ' ( Pr[ F [i, t]]i=1n) ( n 1*1en( )tunion bound previous slideAlgorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne13.2 Global Minimum Cut9Global Minimum CutGlobal min cut. Given an undirected graph G = (V, E) find a cut (A, B)of minimum cardinality.Applications. Partitioning items in a database, identify clusters ofrelated documents, network reliability, network design, circuit design,TSP solvers.Network flow solution.! Replace every edge (u, v) with two antiparallel edges (u, v) and (v, u).! Pick some vertex s and compute min s-v cut separating s from eachother vertex v ' V.False intuition. Global min-cut is harder than min s-t cut.10Contraction AlgorithmContraction algorithm. [Karger 1995]! Pick an edge e = (u, v) uniformly at random.! Contract edge e.– replace u and v by single new super-node w– preserve edges, updating endpoints of u and v to w– keep parallel edges, but delete self-loops! Repeat until graph has just two nodes v1 and v2.! Return the cut (all nodes that were contracted to form v1).u v w%contract u-vab cefcabfd11Contraction AlgorithmClaim. The contraction algorithm returns a min cut with prob & 2/n2.Pf. Consider a global min-cut (A*, B*) of G. Let F* be edges with oneendpoint in A* and the other in B*. Let k = |F*| = size of min cut.! In first step, algorithm contracts an edge in F* probability k / |E|.! Every node has degree & k since otherwise (A*, B*) would not bemin-cut. % |E| & !kn.! Thus, algorithm contracts an edge in F* with probability $ 2/n.A*B*F*12Contraction AlgorithmClaim. The contraction algorithm returns a min cut with prob & 2/n2.Pf. Consider a global min-cut (A*, B*) of G. Let F* be edges with oneendpoint in A* and the other in B*. Let k = |F*| = size of min cut.! Let G' be graph after j iterations. There are n' = n-j supernodes.! Suppose no edge in F* has been contracted. The min-cut in G' is still k.! Since value of min-cut is k, |E'| & !kn'.! Thus, algorithm contracts an edge in F* with probability $ 2/n'.! Let Ej = event that an edge in F* is not contracted in iteration j. ! Pr[E1 " E2L " En#2 ] = Pr[E1] $ Pr[E2 | E1] $ L $ Pr[En#2 | E1" E2L " En#3]% 1#2n( )1#2n#1( )L 1#24( )1#23( )=n #2n( )n # 3n #1( )L24( )13( )=2n(n#1)%2n213Contraction AlgorithmAmplification. To amplify the probability of success, run thecontraction algorithm many times.Claim. If we repeat the contraction algorithm n2 ln n times withindependent random choices, the probability of failing to find theglobal min-cut is at most 1/n2.Pf. By independence, the probability of failure is at most! 1"2n2# $ % & ' ( n2ln n= 1"2n2# $ % & ' ( 12n2) * + + , - . . 2ln n/ e"1( )2ln n= 1n2(1 - 1/x)x $ 1/e14Global Min Cut: ContextRemark. Overall running time is slow since we perform ((n2 log n)iterations and each takes )(m) time.Improvement. [Karger-Stein 1996] O(n2 log3n).! Early iterations are less risky than later ones: probability ofcontracting an edge in min cut hits 50% when n / " 2 nodes remain.! Run contraction algorithm until n / " 2 nodes remain.! Run contraction algorithm twice on resulting graph, and return bestof two cuts.Extensions. Naturally generalizes to handles positive weights.Best known. [Karger 2000] O(m log3n).faster than best known max flow algorithm ordeterministic global min cut algorithmAlgorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin Wayne13.3 Linearity of Expectation16ExpectationExpectation. Given a discrete random variables X, its expectation E[X]is defined by:Linearity of expectation. Given two random variables X and Y definedover the same probability space,