Great Theoretical Ideas In Computer Science Steven Rudich Anupam Gupta Lecture 24 CS 15 251 April 7 2005 Spring 2005 Carnegie Mellon University Random Walks on Graphs Random Walks Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability Random Walks on Graphs At any node go to one of the neighbors of the node with equal probability 1 Random Walks on Graphs Let s start simple We ll just walk in a straight line At any node go to one of the neighbors of the node with equal probability Random walk on a line Random walk on a line You go into a casino with k and at each time step you bet 1 on a fair game You leave when you are broke or have n 0 You go into a casino with k and at each time step you bet 1 on a fair game You leave when you are broke or have n n k Xt k 1 2 t 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 Let Xt be a R V for the amount of money at time t Random walk on a line Random walk on a line You go into a casino with k and at each time step you bet 1 on a fair game You leave when you are broke or have n Question 2 what is the probability that you leave with n n k Question 2 what is the probability that you leave with n n Xt Question 1 what is your expected amount of money at time t 0 0 E Xt k E Xt E Xt Xt 0 Pr Xt 0 E Xt Xt n Pr Xt n E Xt neither Pr neither 0 n Pr Xt n somethingt Pr neither As t Pr neither 0 also somethingt n Hence Pr Xt n k n 2 Another way of looking at it Random walks and electrical networks What is chance I reach green before red You go into a casino with k and at each time step you bet 1 on a fair game You leave when you are broke or have n 0 n k Question 2 what is the probability that you leave with n the probability that I hit green before I hit red Same as voltage if edges are resistors and we put 1 volt battery between green and red Random walks and electrical networks Electrical networks save the day You go into a casino with k and at each time step you bet 1 on a fair game You leave when you are broke or have n 0 px Pr reach green first starting from x pgreen 1 pred 0 and for the rest px Averagey2 Nbr x py Same as equations for voltage if edges all have same resistance 0 volts n k 1 volt Question 2 what is the probability that you leave with n voltage k k n Pr hitting n before 0 starting at k Random walks and electrical networks What is chance I reach green before red Let s move on to some other questions on general graphs Of course it holds for general graphs as well 3 Getting back home Getting back home Lost in a city you want to get back to your hotel How should you do this Lost 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 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 Furthermore Relax Bonzo Yes Pr will reach home 1 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 this 4 Cover times Let 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 Theorem If the graph G has n nodes and m edges then the cover time of G is C 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 that Pr eventually get home 1 We will eventually get home Look at the first n steps There is a non zero chance p1 that we get home Suppose we fail Then wherever we are there a chance p2 0 that 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 An averaging argument In fact Pr we don t get home by 2k C G steps k Recall C G cover time of G 2m n 1 Suppose 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 5 Markov s Inequality Random variable X has expectation A E X A E X E X X 2A Pr X 2A E X X 2A Pr X 2A E X X 2A Pr X 2A Also E X X 2A A 2A Pr X 2A An averaging argument Suppose 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 2A Pr X 2A Pr X exceeds k expectation 1 k 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 The power of independence It is like flipping a coin with tails probability q The probability that you get k tails is qk k because the trials are independent Pr haven t hit all vertices in 2C G more time start at v Hence Pr havent hit everyone in time k 2C G k Chance that you failed both times Exponential in k Hence if we know that Expected Cover Time C G 2m n 1 then Pr home by time 4km n 1 1 k Let us see a cute implication of the fact that we see all the vertices quickly 6 3 regular cities Think of graphs where every node has degree 3 …
View Full Document
Unlocking...