Great Theoretical Ideas In Computer Science John Lafferty Lecture 12 CS 15 251 Oct 5 2005 Fall 2006 Carnegie Mellon University Ancient Wisdom Primes Continued Fractions The Golden Ratio and Euclid s GCD 3 13 3 2 3 1 1 1 3 1 3 1 3 1 3 1 3 1 3 3 1 3 1 Recap and finishing up probability 2 Something completely different 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 Show E X v Conclude it must be possible to have X v Pigeonhole principle Given n boxes and m n objects at least one box must contain more than one object Letterbox principle If the average number of letters per box is a then some box will have at least a letters Similarly some box has at most a Independent Sets An independent set in a graph is a set of vertices with no edges between them All of the vertices in such a set can be given the same color so the size of the largest independent set i X gives a bound on the number of colors required c G c G i X n A coloring divides up the graph into independence sets and each one is no bigger than i X in size Theorem If a graph G has n vertices and m edges then it has an independent set with at least n2 4m vertices Let d 2m n be the average degree Randomly take away vertices and edges 1 Delete each vertex of G together with its incident edges with probability 1 1 d 2 For each remaining edge remove it and one of its vertices The remaining vertices form an independent set How big is it expected to be Expectatus Linearitus 3 HMU Theorem If a graph G has n vertices and m edges then it has an independent set with at least n2 2m vertices Let X be the number of vertices that survive the first step E X n d Let Y be the number of edges that survive the first step E Y m 1 d 2 nd 2 1 d 2 n 2d The second step removes all the remaining edges and at most Y vertices So size of final set of vertices is at least X Y and E X Y n d n 2d n 2d n2 4m An easy question A 2 0 1 1 5 2 But it never actually gets to 2 Is that a problem But it never actually gets to 2 Is that a problem No by i 0 f i we really n mean limn i 0 f i if this is undefined so is the sum In this case the partial sum is 2 n which goes to 2 A related question Suppose I flip a coin of bias p stopping when I first get heads What s the chance that I Flip exactly once Ans p Flip exactly two times Ans 1 p p Flip exactly k times Ans 1 p k 1p Eventually stop Ans 1 assuming p 0 A related question Pr flip once Pr flip 2 times Pr flip 3 times 1 p 1 p p 1 p 2p 1 p 3p 1 Or using q 1 p Pictorial view p 1 p p 1 p p 1 p p Sample space S leaves in this tree Pr x product of edges on path to x If p 0 prob of not halting by time n goes to 0 as n Use to reason about expectations too p 1 p p 1 p p 1 p p Pr x A product of edges on path from A to x E X x Pr x X x E X A x A Pr x A X x I e it is as if we started the game at A Use to reason about expectations too p 1 p p 1 p p 1 p p Flip bias p coin until heads What is expected number of flips Use to reason about expectations too p 1 p p 1 2 1 p p p 3 1 p Let X flips 4 Let A event that 1st flip is heads E X E X A Pr A E X A Pr A 1 p 1 E X 1 p Solving pE X p 1 p so E X 1 p Infinite Probability spaces Notice we are using infinite probability spaces here but we really only defined things for finite spaces so far Infinite probability spaces can sometimes be weird Luckily in CS we will almost always be looking at spaces that can be viewed as choice trees where Pr haven t halted by time t 0 as t General picture Let S be a sample space we can view as leaves of a choice tree p Let Sn leaves at depth n For event A let An A Sn Pr A limn Pr An p 1 p p 1 p p If limn Pr Sn 1 can define 1 p Setting that doesn t fit our model Flip coin until heads 2 tails There s a reasonable chance this will never stop Random walk on a line You go into a casino with k and at each time step you bet 1 on a fair game Leave when you are broke or have n 0 Question 1 what is your expected amount of money at time t Let Xt be a R V for the amount of money at time t n Random walk on a line You go into a casino with k and at each time step you bet 1 on a fair game Leave when you are broke or have n Question 1 what is your expected amount of money at time t Xt k 1 2 t where i is a RV for the change in your money at time i E i 0 since E i A 0 for all situations A at time i So E Xt k Random walk on a line You go into a casino with k and at each time step you bet 1 on a fair game Leave when you are broke or have n Question 2 what is the probability you leave with n Random walk on a line You go into a casino with k and at each time step you bet 1 on a fair game Leave when you are broke or have n Question 2 what is the probability you leave with n One way to analyze E Xt k E Xt E Xt Xt 0 Pr Xt 0 E Xt Xt n Pr Xt n E Xt neither Pr neither So E Xt 0 n Pr Xt n something Pr neither As t Pr neither 0 Also 0 something n So limt Pr Xt n k n So Pr leave with n k n And now for something completely different Definition A number 1 is prime if it has no other factors besides 1 and itself Each number …
View Full Document
Unlocking...