Today’s topicsGetting back homeSlide 3PowerPoint PresentationSlide 5Slide 6Slide 7Cover timesSlide 9Slide 10We will eventually get homeSlide 12An averaging argumentSlide 14so let’s walk some more!The power of independenceSlide 17Slide 18Slide 19Random Walk on a lineUnbiased Random WalkSlide 22Slide 23Simple ClaimWe will return…How about a 2-d grid?Slide 27Slide 28Slide 29Slide 30in the 2-d walkWe will return (again!)…But in 3-dThe Mathematics Of 1950’s TV-style Dating: Who wins the battle of the sexes?Slide 35Dating ScenarioSlide 37Slide 38Rogue CouplesWhy be with them when we can be with each other?Stable PairingsWhat use is fairness, if it is not stable?The study of stability will be the subject of the entire lecture.The Traditional Marriage AlgorithmSlide 45Traditional Marriage AlgorithmDoes the Traditional Marriage Algorithm always produce a stable pairing?Slide 48Does TMA always terminate?Slide 50Improvement Lemma: If a girl has a boy on a string, then she will always have someone at least as good on a string, (or for a husband).Theorem: Let T be the pairing produced by TMA. T is stable.Opinion PollForget TMA for a momentThe Optimal GirlThe Pessimal GirlDating Heaven and HellSlide 58Slide 59The Naked Mathematical Truth!Theorem: TMA produces a male-optimal pairingSome boy b got rejected by his optimal girl g because she said “maybe” to a preferred b*. b* likes g at least as much as his optimal girl.Slide 63Theorem: The TMA pairing, T, is female-pessimal.Final ExamCompSci 102 18.1Today’s topics•Impaired wanderingImpaired wandering•Instant InsanityInstant Insanity•1950s TV Dating1950s TV Dating•Final Exam reviewFinal Exam reviewGetting back homeLost in a city, you want to get back to your hotel.How should you do this?Depth First Search: requires a good memory and a piece of chalk-Getting back homeLost in a city, you want to get back to your hotel.How should you do this?How about walking randomly? no memory, no chalk, just coins… -Will this work?When will I get home?I have a curfew of 10 PM!Will this work?Is Pr[ reach home ] = 1?When will I get home?What is E[ time to reach home ]?I have a curfew of 10 PM!Relax, Bonzo!Yes,Pr[ will reach home ] = 1Furthermore:If the graph has n nodes and m edges, then E[ time to visit all nodes ] ≤ 2m × (n-1)E[ time to reach home ] is at most thisCover timesLet us define a couple of useful things:Cover time (from u) Cu = E [ time to visit all vertices | start at u ]Cover time of the graph: C(G) = maxu { Cu }Cover Time TheoremIf the graph G has n nodes and m edges, then the cover time of G isC(G) ≤ 2m (n – 1)Any graph on n vertices has < n2/2 edges.Hence C(G) < n3 for all graphs G.First, let’s prove thatPr[ eventually get home ] = 1We will eventually get homeLook at the first n steps.There is a non-zero chance p1 that we get home.Suppose we fail.Then, wherever we are, there is a chance p2 > 0that we hit home in the next n steps from there.Probability of failing to reach home by time kn = (1 – p1)(1- p2) … (1 – pk) 0 as k ∞In factPr[ we don’t get home by 2k C(G) steps ] ≤ (½)kRecall: C(G) = cover time of G ≤ 2m(n-1)An averaging argumentSuppose I start at u. E[ time to hit all vertices | start at u ] ≤ C(G)Hence, Pr[ time to hit all vertices > 2C(G) | start at u ] ≤ ½.Why? Else this average would be higher. (called Markov’s inequality.)An averaging argumentSuppose I start at u. E[ time to hit all vertices | start at u ] ≤ C(G)Hence, by Markov’s Inequality Pr[ time to hit all vertices > 2C(G) | start at u ] ≤ ½.so let’s walk some more!Pr [ time to hit all vertices > 2C(G) | start at u ] ≤ ½.Suppose at time 2C(G), am at some node v, with more nodes still to visit.Pr [ haven’t hit all vertices in 2C(G) more time | start at v ] ≤ ½.Chance that you failed both times ≤ ¼ !The power of independenceIt is like flipping a coin with tails probability q ≤ ½.The probability that you get k tails is qk ≤ (½)k.(because the trials are independent!)Hence, Pr[ havent hit everyone in time k × 2C(G) ] ≤ (½)kExponential in k!Hence, if we know that Expected Cover TimeC(G) < 2m(n-1)then Pr[ home by time 4km(n-1) ] ≥ 1 – (½)kRandom walks on infinite graphsA drunk man will find his way home, but a drunk bird may get lost forever- Shizuo KakutaniRandom Walk on a lineFlip an unbiased coin and go left/right. Let Xt be the position at time tPr[ Xt = i ] = Pr[ #heads - #tails = i] = Pr[ #heads – (t - #heads) = i] = /2t0 t (t-i)/2 iUnbiased Random WalkPr[ X2t = 0 ] = /22t Stirling’s approximation: n! = Θ((n/e)n × √n)Hence: (2n)!/(n!)2 = = Θ(22n/n½)0 2t t £ ((2ne)2np2n)£ ((ne)npn)Unbiased Random WalkPr[ X2t = 0 ] = /22t ≤ Θ(1/√t)Y2t = indicator for (X2t = 0) E[ Y2t ] = Θ(1/√t)Z2n = number of visits to origin in 2n steps. E[ Z2n ] = E[ t = 1…n Y2t ] = Θ(1/√1 + 1/√2 +…+ 1/√n) = Θ(√n)0Sterling’sapprox. 2t t In n steps, you expect to return to the origin Θ(√n) times!Simple ClaimRecall: if we repeatedly flip coin with bias pE[ # of flips till heads ] = 1/p.Claim: If Pr[ not return to origin ] = p, thenE[ number of times at origin ] = 1/p.Proof: H = never return to origin. T = we do.Hence returning to origin is like getting a tails.E[ # of returns ] = E[ # tails before a head] = 1/p – 1. (But we started at the origin too!)We will return…Claim: If Pr[ not return to origin ] = p, thenE[ number of times at origin ] = 1/p.Theorem: Pr[ we return to origin ] = 1.Proof: Suppose not. Hence p = Pr[ never return ] > 0. E [ #times at origin ] = 1/p = constant.But we showed that E[ Zn ] = Θ(√n) ∞How about a 2-d grid?Let us simplify our 2-d random walk: move in both the x-direction and y-direction…How about a 2-d grid?Let us simplify our 2-d random walk: move in both the x-direction and y-direction…How about a 2-d grid?Let us simplify our 2-d random walk: move in both the x-direction and y-direction…How about a 2-d grid?Let us simplify our 2-d random walk: move in both the x-direction and y-direction…How about a 2-d grid?Let us simplify our 2-d random walk: move in both the x-direction and y-direction…in the 2-d walkReturning to the origin in the grid both “line” random walks return to their originsPr[ visit origin at time t ] = Θ(1/√t) × Θ(1/√t) = Θ(1/t)E[ # of
View Full Document
Unlocking...