### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 711 at UMass(1)

### View Full Document

## 12

## 0

## Popular in Course

## Popular in Department

This 6 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 12 views.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 711 at UMass(1)

### 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: 02/06/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 ll De ne the random variable Z as Z fX1 X2 i i i Xn 2 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 4 Apply Azuma s inequality to show that the probability of the nal value of Z deviating from it expec tation is very small 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 EZlLocation 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 1 I 51 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 ED and Vi suchthat l Signand VXED lfX1H Xllan7fX1u 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 7 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 a 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 Pr W0 7 Ema gt Am 3 25 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 l edge i of the lt gt total edges is present n Let X 2 0 otherwise 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 7 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 EMGH39 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 2 De ne the Doob martingale as follows Z E39yG X1X2H X where Z0 E g and Zn Z 5 Claim 54 Vi Z 7 Zkll S 1 as f satis es Lipschitz s condition ie fX1mXan7fX1MXQHXM 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 MG 7 Ema gt W5 3 2e 2 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 by 1 log n Ewan 7 3x 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 00 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 EY gtlt plt gt W probabzlzty of all edges bezng present clzques of sue 1c k n n USE nk 1c Icil SH 7 WW What is the value of k that makes this expectation very small mp 1 EY A Let b to get 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 follows 0 otherwise X 7 l ifthei hkiset hasakiclique Then the number of cliques of size k n n k k W 2X1 2X1 Y2 ZZXlXj j 56 Lecture 5 February 11 rap2 2X1le by symmetry Eh lt Z gt EX1Xj EX1Xj depends on l Which is the number of elements in common With X1 and Xj 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 Choosing l elements Other elements Thus k k l 2 n k n 7 k 2 2 2 0 XXX z X w W End result Substituting b 1 17 With probability A l as n A 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.