Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 23 CS 15 251 April 5 2005 Spring 2005 Carnegie Mellon University Probability III The probabilistic method infinite probability spaces Recap Random Variables An event is a subset of S A Random Variable RV is a realx P x valued function on S Example Event A the first die came up 1 Random Variable X the value of the first die E g X 3 5 3 X 1 6 1 1 1 1 2 1 3 1 4 1 5 1 6 2 1 M M 6 5 6 6 1 36 1 36 1 36 1 36 1 36 1 36 1 36 1 36 1 36 It s a floor wax and a dessert topping It s a function on the sample space S It s a variable with a probability distribution on its values HMU You should be comfortable with both views Definition expectation The expectation or expected value of a random variable X is E g 2 coin flips X heads What is E X 1 HT 2 HH 0 TT 1 TH Thinking about expectation D S TT TH HT HH X Distrib on X 0 1 2 E X 0 1 1 2 1 E X 0 1 2 1 Linearity of Expectation If Z X Y then E Z E X E Y HMU Even if X and Y are not independent New topic The probabilistic method Use a probabilistic argument to prove a nonprobabilistic mathematical theorem Definition A cut in a graph A cut is a partition of the nodes of a graph into two sets U and V We say that an edge crosses the cut if it goes from a node is U to a node in V Cut U V Theorem In any graph there exists a cut such that at least half the edges cross the cut Theorem In any graph there exists a cut such that at least half the edges cross the cut How are we going to prove this Will show that if we pick a cut at random random the expected number of edges crossing is edges What might be is surely possible Goal show exists object of value at least v Proof strategy Define distribution D over objects Define RV X object value of object Theorem In any graph there exists a cut such that at least half the edges cross the cut Proof Pick a cut uniformly at random I e for each node flip a fair coin to determine if it is in U or V Let Xe be the indicator RV for the event that edge e crosses the cut Ans What is E Xe Theorem In any graph there exists a cut such that at least half the edges cross the cut Proof Pick random cut Let Xe 1 if e crosses else Let Xe 0 Let X total edges crossing So X e Xe Also E X Also Pick a cut uniformly at random I e for each node flip a fair coin to see if it should be in U E of edges crossing cut of edges 2 The sample space of all possible cuts must contain at least one cut that at least half the edges cross if not the average number of edges would be less than half Another example of prob method What you did on hwk 8 If you color nodes at random Pr every v has a neighbor of a different color 0 So must exist coloring where every v has a neighbor of a different color This then implied existence of evenlength cycle Back to cuts Can you use this argument to also find such a cut In this case you can through a neat strategy called the conditional expectation method HMU Idea make decisions in greedy manner to maximize expectation togo First a few more facts For any partition of the sample space S into disjoint events A1 A2 An and any event B Pr B i Pr B Ai i Pr B Ai Pr Ai B A1 A2 A3 An Def Conditional Expectation For a random variable X and event A the conditional expectation of X given A is defined as E g roll two dice X sum of dice E X 7 Let A be the event that the first die is 5 E X A 8 5 Def Conditional Expectation For a random variable X and event A the conditional expectation of X given A is defined as Useful formula for any partition of S into A1 A2 we have E X i E X Ai Pr Ai Proof just plug in Pr X k i Pr X k Recap of cut argument Pick random cut Let Xe 1 if e crosses else Xe 0 Let X total edges crossing So X e Xe Also E Xe By linearity of expectation E X total edges Conditional expectation method Say we have already decided fate of nodes 1 2 i 1 Let X number of edges crossing cut if we place rest of nodes into U or V at random Let A event that node i is put into U So E X E X A E X A It can t be the case that both terms on the RHS are smaller than the LHS So just put node i into side whose C E is larger Pictorial view important View S as leaves of choice tree ith choice is where to put node i Label leaf by value of X E X avg leaf value G U U V 1 3 2 V U U V U V U V 0 1 2 1 1 2 V U 1 V 0 Pictorial view important If A is some node the event that we reach that node then E X A avg value of leaves below A Alg greedily follow path to maximize G avg 1 U U V 3 2 V U U V U V U V 0 1 2 1 1 2 V U 1 V 0 Pictorial view important Linearity of expectation gives us a way of magically computing E X A for any node A Even though the tree has 2n leaves G U U V 1 3 2 V U U V U V U V 0 1 2 1 1 2 V U 1 V 0 Pictorial view important In particular E X A edges crossing so far edges not yet determined G U U V 1 3 2 V U U V U V U V 0 1 2 1 1 2 V U 1 V 0 Conditional expectation method In fact our algorithm is just put node i into the side that has the fewest of its neighbors so far The side that causes the most of the edges determined so far to cross the cut But the probabilistic view was useful for proving that this works In many cases though we can t get an exact handle on these expectation Probabilistic method can often give us proof of existence without an algorithm for finding the thing In …
View Full Document
Unlocking...