Parallel Algrthm&Arc CMPSCI 711
Popular in Course
Popular in ComputerScienence
This 6 page Class Notes was uploaded by Roman McCullough on Friday October 30, 2015. The Class Notes belongs to CMPSCI 711 at University of Massachusetts taught by Staff in Fall. Since its upload, it has received 8 views. For similar materials see /class/232278/cmpsci-711-university-of-massachusetts in ComputerScienence at University of Massachusetts.
Reviews for Parallel Algrthm&Arc
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/30/15
CMPSCI 711 Really Advanced Algorithms Spring 2003 Lecture 5 February 11th Lecturer Micah Adler Scribe Purushottam Puru Kulkarni 51 Recap 511 Azuma s Inequality Let X0 X1 X2 i H be a martingale sequence such that Vh le 7 Xk71l S c for some constant c then Vt gt 0 and gt 0 2 PrHXtiXol 2 A g 25 512 Method of bounded differences The method of bounded differences can be applied using the following steps i i De ne the random variable Z as Z fX1 X2 i i i Xn m i Consider the Doob martingale Z1 E Zle i i i X1 3 Show that Z does not change much as the random variables X s are incrementally revealed iiei VilZliZz1l Sc u i Apply Azuma s inequality to show that the probability of the nal value of Z deviating from it expec tation is very sma i Example 51 From last lecture Throw n balls uniformly and independently at random into n bins De ne random variables Z Number of empty bins after all balls are thrown and X1 Location of the ith ball De ne the Doob martingale Zt as follows Zt EZ Location of first t balls EZlX1X2HiXt Claim 51 As we reveal X1 lZl 7 Z1431 Proof Informal proof discussed last time After each ball is thrown it either lands in a nonempty bin in which case the expectation increases by less than 1 and if the ball lands in an empty bin it decreases by at most I 52 Lecture 5 February ll h 52 Lipschitz s condition General technique to show a martingale sequence has the bounded property is as follows Let f D1 l l l D7 8 9 be a realivalued function from possibly different domains Then we say that f satis es Lipschitz s condition if VXl E Dhuan E D7 and Vi such that l S i S n and VX E D lfX1H XllanEfX1u X lanH S 1 ie if we take any input to the function f and then change one of the inputs to an arbitrary value the absolute difference with the value of the original function is at most 1 Claim 52 If the function f satis es Lipschitz s condition then V i lZl E Zkll S 1 Referring to Example 51 we can de ne the random variable Z as a function f of all the Xl s which denote the location of the n balls The function f satis es the Lipschitz s conditionl Given a certain set of values for all Xl s if we change the the location of any arbitrary ith ball we can at most change the value of Z by 1 The new placement can place the ball from a noniempty bin to a empty bin or from from a noniempty bin to a noniempty binl Both the cases result in the total number of empty bins to vary by at most 1 Example 52 Graph coloring Problem Consider a graph G assign each vertex a color so that no edge in the graph is monochromatic yG Minimum number of colors required to color G as de ned above Speci cally consider a random graph G n 5 where n 39 number of oertices of graph G and is the probability of each possible edge being present in the graph total lt 3 gt edges possible in the graph Claim 53 7 2 Pr we 7 Ema gt W s 2wquot ie Expected number of colors required to color a graph is concentrated close to it s expectation Proof The rst step of the proof is to de ne a martingale Try 1 Edge exposure martingale 1 n Let X1 1 edge i of the lt 2 0 otherwise gt total edges is present The corresponding Doob martingale does satisfy Lipschitz s condition and Azuma s inequality can be applied But this is not an e lcient method as a total number of lt 3 gt edges possible can exist in the graph and X for all edges has to be revealed to get to the nal value of yG Which meanst lt Z gt m n2 where t is from the Azuma s inequality Using t m n2 and applying Azuma s inequality Pr W0 7 Ema gt W m 2 Lecture 5 February 11th 53 Therefore m n for the above probability to be small Thus MAC 7 E yG 2 n which is not a very tight bound on the nal value of 40 and it s expectation EVGl Try 2 Vertex exposure martingale 1 Let X be the description of the edges from vertex i to all smaller numbered vertices i 7 1i 7 2 l l l 1 the vertices are numbered randomly and uniquely Example 53 A example random graph and it s X descriptions X1 X2 1 X3 12 X4 13 PW De ne the Doob martingale as follows Z E39yG X1X2H X where Z0 E g and Zn Z 93 Claim 54 Vi Z 7 Zkll S 1 as f satis es Lipschitz s condition ie fX1lHX l Xn7fX1ulXlanl S 1 ie de ne Z fX1X2 l lan and changing an arbitrary X in input of function f changes the value of Z by at most 1 Changing X means changing the description of edges from vertex i to all smaller numbered edges If more edges are added to vertex i since we have already colored all small numbered vertices non7monochromatically adding edges to any number of small7numbered vertices will increase the number of required colors by at most 1 Also deleting edges from the description can only decrease the required number of colors by 1 or keep the number unchanged 4 As we have bounded the di erence between the values of Z and Z171 we can now apply Azuma s inequality Substituting E in the original inequality gives the required probability inequality 2 Pr we 7 BMW gt W 2eT 5 Note We have not used the fact that in a random graph the probability of an edge from all possible edges being present is Any probability distribution function will have the same property Nothing has been said about the expectation E yG of the number of colors required to color the graph The proof just states that the actual number of colors required will be very close the the expectation with a very high probability Also note that this an existential proof and not a constructive proof The expression for the expected number of colors is given y 1 Ewan 7 9 E 54 Lecture 5 February 11 Example 54 Cliques in a random graphs Consider a random graph G described by Cn p where p is the probability of any edge being present in G from the set of all possible edges 00 39 maximum number of vertices in a clique of the graph G Also the probability that we generate a speci c random graph 9 is given by PrlG9l10E1710ltZ E where E is the number of edges in G 53 Second Moment Method Consider a random variable X with some associated probability distributions EX2 is the second moment of Xi The second moment is used to say something about the random variable and in particular used to bound the probability that a certain property exists Referring to Example 54 we want to bound the probability of having a clique of some size and will use the Second Moment method to bound this value with a high probability Fix a positive integer h Y Number of cliques of size h in G N Gnp Y is a noninegative integer valued random variables Properties of noninegative random variable my 0 g EY VarY lt PrY 0 7 EDP A slightly stronger inequality is VarY lt PrY 0 7 EDQ this is due to the fact VarY EY2 7 EY2 and since VarY is noninegative EY2 2 EY2i Refer Problem 36 in MR95 Bounds on value of h PrY y 0 small for some value of h gives an upper bound on the maximum number of vertices in a cliquesi This probability states that with a very small probability a clique of size h exists in graph Gs Finding a minimum value of such h will give the upper bound on the value of 10 PrY 0 small for another value of h gives a lower bound on the maximum number of vertices in a cliquesi This probability states that with a very small probability a clique of size h does not exist in graph G ie at least one clique of of size h existsi Finding a maximum value of such h will give a lower bound on the value of wG i Lecture 5 February ll h 55 Upper bound on the value of k For a given value of k the expected number of cliques of that size is given by lt k gt n EY X p 2 k W probabzlzty of all edges bezng present clzques of sue 1c 77 1c Jeri Em We 1 m C S a p 2 gt What is the value of k that makes this expectation very small Jeri ingt S 1 Let b to get n S bk S1 Therefore EY is very small for k 210g 71 ll Conclusion A clique of size k 2 2 logb n l is very unlikely and it is very likely that Y 0 Lower bound on the value of k me EY2 7 EY2 Ell2 7 Ell2 Need to calculate EY2 as expression for EY already known from previous steps De ne random variable X as fol ows l the ith k 7 set has a k 7 clique X1 0 otherwzse Then the number of cliques of size k 56 Lecture 5 February 11th rap2 2X1le by symmetry Eh lt Z gt EX1Xj EX1Xj depends on l Which is the number of elements in common With X1 and in k l lt l l 2 PrClique on both sides When l elements in common p lt 2 2 Where 2lt I gt is the total number of edges possible in k clique and lt gt is the number of shared edges Number of k sets that have exactly l elements in common With X1 is k X n 7 k l k 7 l W Choosing l elements Other elements Emltzgtiltsgtlt27gtltpflt gtlt5gt 0 End result Substituting b 1 1 With probability 7 1 as n 7gt 0 and With a xed value of p size of the largest clique differs by at most 1 from 2 logb n 7 2 logb logb n constant Example 55 For n 1000 andp 05 With probability 2 value ofw is 15 or 16 The result is useful as it a good way to test new heuristics as the second moment method gives a very tight bound on the measured value With a high probability References MRQS R MOTWANI and P RAGHAVAN Randomized Algorithms Cambridge University Press 1995
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'