1Random WalksCarnegie Mellon UniversityApril 7, 2005Lecture 24CS 15-251 Spring 2005Steven Rudich, Anupam GuptaGreat Theoretical Ideas In Computer ScienceRandom Walks on Graphs -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.-2Random Walks on Graphs At any node, go to one of the neighbors of the node with equal probability.-Let’s start simple…We’ll just walk in a straight line.Random walk on a lineYou 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 1:what is your expected amount of money at time t?Let Xtbe a R.V. for the amount of money at time t.0nkXt= k + δ1+ δ2+ ... + δt,(δ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 lineYou 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.0nXtRandom walk on a lineYou 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 ?0nkRandom walk on a lineQuestion 2:what is the probability that you leave with $n ?E[Xt] = k.E[Xt] = E[Xt| Xt= 0] × Pr(Xt= 0) + E[Xt| Xt= n] × Pr(Xt= n) + E[ Xt| neither] × Pr(neither)As t →∞, Pr(neither) → 0, also somethingt< nHence Pr(Xt= n) → k/n.0+ n × Pr(Xt= n) + (somethingt× Pr(neither))3Another way of looking at itYou 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 ?= the probability that I hit green before I hit red.0nkRandom walks and electrical networks-What is chance I reach green before red?Same as voltage if edges are resistors and we put 1-volt battery between green and red.Random walks and electrical networks-•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!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.Question 2:what is the probability that you leave with $n ?voltage(k) = k/n = Pr[ hitting n before 0 starting at k] !!!0nk1 volt0 voltsRandom walks and electrical networks-Of course, it holds for general graphs as well…What is chance I reach green before red?Let’s move on tosome other questions on general graphs4Getting 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 allnodes ] ≤ 2m × (n-1)E[ time to reach home ] is at most this5Cover 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, thenthe cover time of G isC(G) ≤ 2m (n – 1)Any graph on n vertices has < n2/2 edges.Hence C(G) < n3for 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 p1that we get home.Suppose we fail.Then, wherever we are, there 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.)6Markov’s InequalityRandom 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] > 2A⇒ A ≥ 2A × Pr[X > 2A] ⇒ ½ ≥ Pr[X > 2A]Pr[ X exceeds k × expectation ] ≤ 1/k.An averaging argumentSuppose I start at u.E[ time to hit all vertices | start at u ] ≤ C(G)Hence, by Markov’s InequalityPr[ 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 bothtimes ≤ ¼!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 – (½)kLet us see a cute implication of the fact that we seeall the verticesquickly!7“3-regular” citiesThink of graphs where every node has degree 3.(i.e., our cities only have 3-way crossings)And edges at any node are numbered with 1,2,3.113223123123GuidebookImagine a sequence of 1’s, 2’s and 3’s12323113212131…Use this to tell you which edge to take out of a vertex.113223123123Guidebook113223123123Imagine a sequence of 1’s, 2’s and 3’s12323113212131…Use this to tell you which edge to take out of a vertex.Guidebook113223123123Imagine a sequence of 1’s, 2’s and 3’s12323113212131…Use this to tell you which edge to take out of a vertex.Guidebook113223123123Imagine a sequence of 1’s, 2’s and 3’s12323113212131…Use this to tell you which edge to take out of a vertex.Universal
View Full Document