Ancient Wisdom: Primes, Continued Fractions, The Golden Ratio, and Euclid’s GCDCarnegie Mellon UniversityOct 5, 2005Lecture 12CS 15-251 Fall 2006John LaffertyGreat Theoretical Ideas In Computer Science3 13 13123131313131313133 ....+= ++++++++++1. Recap, and finishing up probability2. 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 nboxes and m > nobjects, 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 aletters. (Similarly, some box has at most a.)Independent SetsAn independent setin 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/d2. 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)3HMUHMUHMUHMUTheorem: 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 verticesthat survive the first step: E[X] = n/d. Let Y be the number of edgesthat 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/4mAn easy questionA: 2.0 1 1.5 2But 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 mean limn→ ∞∑i=0f(i).[if this is undefined, so is the sum]In this case, the partial sum is 2-(½)nwhich goes to 2.∞nA related questionA related questionSuppose 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)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,A related questionA related questionPictorial viewPictorial viewSample 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→∞.p 1-p...ppp1-p1-pPr(x|A)=product of edges on path from A to x.E[X] = ∑xPr(x)X(x).E[X|A] = ∑x∈ APr(x|A)X(x). I.e., it is as if we started the game at A.p 1-p...ppp1-p1-pUse to reason about expectations tooUse to reason about expectations tooUse to reason about expectations tooUse to reason about expectations tooFlip bias-p coin until heads. What is expected number of flips?p 1-p...ppp1-p1-pUse to reason about expectations tooUse to reason about expectations tooLet X = # flips.Let A = event that 1stflip 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.p 1-p...ppp1-p1-p1234Infinite Probability spacesInfinite Probability spacesNotice 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 pictureGeneral pictureLet S be a sample space we can view as leaves of a choice tree.Let Sn= {leaves at depth n}.For event A, let An= A∩Sn.If limn→∞Pr(Sn)=1, can define:Pr(A)=limn→∞Pr(An).p 1-p...ppp1-p1-pSetting that doesnSetting that doesn’’t fit our modelt fit our modelFlip coin until #heads > 2*#tails.There’s a reasonable chance this will never stop...Random walk on a lineRandom walk on a lineYou 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?Let Xtbe a R.V. for the amount of money at time t.0 nRandom walk on a lineRandom walk on a lineYou 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 δiis 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 lineRandom walk on a lineYou 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 lineRandom walk on a lineYou 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 can be factored into primes in a unique way. [Euclid]Theorem: Each natural has a unique factorization into primes written in non-decreasing order.Definition: A number > 1 is prime if it has no other factors, besides 1 and itself. Primes: 2, 3, 5, 7, 11, 13, 17, …Factorizations:42 = 2 * 3 * 784 = 2 * 2 * 3 * 713 = 13Multiplicationmight just be a “one-way” functionMultiplication is fast to computeReverse multiplication is apparently slowWe have a feasible method to multiply 1000 bit numbers [Egyptian multiplication]Factoring the product of two random 1000 bit primes has no known feasible
View Full Document
Unlocking...