### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Note 9 for CMPSCI 711 at UMass

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Department

This 40 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 20 views.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Note 9 for CMPSCI 711 at UMass

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

CMPSCI 711 Really Advanced Algorithms Lecture 9 Markov Chains and Random Walks Andrew McGregor Last Comp ed February 24 2009 Outline Markov Chains Motivating Example gt An algorithm for 2 SAT 1 Pick arbitrary assignment 2 Pick an unsatisfied clause randomly flip the value assigned to one of the two variables 3 Repeat Step 2 until there are no unsatisfied clauses Motivating Example gt An algorithm for 2 SAT 1 Pick arbitrary assignment 2 Pick an unsatisfied clause randomly flip the value assigned to one of the two variables 3 Repeat Step 2 until there are no unsatisfied clauses gt Let X be the assignment at time t Motivating Example gt An algorithm for 2 SAT 1 Pick arbitrary assignment 2 Pick an unsatisfied clause randomly flip the value assigned to one of the two variables 3 Repeat Step 2 until there are no unsatisfied clauses gt Let X be the assignment at time t gt Consider X n 7 AXty for a fixed satisfying assignment y ie the number of variables that are set the same in both Xf and y Motivating Example gt An algorithm for 2 SAT 1 Pick arbitrary assignment 2 Pick an unsatisfied clause randomly flip the value assigned to one of the two variables 3 Repeat Step 2 until there are no unsatisfied clauses gt Let X be the assignment at time t gt Consider X n 7 AXty for a fixed satisfying assignment y ie the number of variables that are set the same in both Xf and y gt Xt1 X i 1 and PXt1 x 1 2 12 Motivating Example gt An algorithm for 2 SAT 1 Pick arbitrary assignment 2 Pick an unsatisfied clause randomly flip the value assigned to one of the two variables 3 Repeat Step 2 until there are no unsatisfied clauses gt Let X be the assignment at time t gt Consider X n 7 AXty for a fixed satisfying assignment y ie the number of variables that are set the same in both Xf and y gt Xt1 X i 1 and PXt1 x 1 2 12 gt How long until we terminate Markov Chain A Markov chain is a discretetime stochastic process that defines a sequence of random variables X07X17X27 and is defined by gt State space eg Xt E 17 7 n gt Transition probabilities PU l Xt leFl i gt Initial distribution for X0 Markov Chain A Markov chain is a discretetime stochastic process that defines a sequence of random variables X07X17X27 and is defined by gt State space eg Xt E 17 7 n gt Transition probabilities PU l Xt leFl i gt Initial distribution for X0 Memoryless Xt only depends on Xt1 Pix ithtA E717 7X1 13917X0 i0 Pix ithtA E71 PI rid State Probability Vector and Stationary Distribution Definition Let qgt 1PXt i The distribution of the chain at time t is the t t 397 710 row vector ql q2 State Probability Vector and Stationary Distribution Definition Let qgt 1PXt i The distribution of the chain at time t is the row vector q7 qgt 7 79 Lemma q 70F t Where P be the matrix Whose ij th entry is PU State Probability Vector and Stationary Distribution Definition Let qgt 1PXt i The distribution of the chain at time t is the row vector q7 qgt 7 79 Lemma q 70F t Where P be the matrix Whose ij th entry is PU Definition A stationary distribution for a Markov chain with transition matrix P is a probability distribution 7139 such that 7139 7rP Underlying Graphs and Irreducible Markov Chains Definition The underlying graph of a Markov chain is a directed graph G V7 E where V n and i7j E E ifF PU gt O Underlying Graphs and Irreducible Markov Chains Definition The underlying graph of a Markov chain is a directed graph G V7 E where V n and i7j E E ifF PU gt 0 Definition A Markov chain is irreducible if its underlying graph consists of a single strong component Recall that a strong component of a directed graph is a maximal subgraph C of G such that for any vertices i and j in C there is a directed path from to j Transient States and Persistent States Probability that t is the first time that the chain visits statej if it starts at state i rgtipxtjandxs jforan1gslttiX0 Transient States and Persistent States Probability that t is the first time that the chain visits statej if it starts at state i rgtipxtjandxs jforan1gslttiX0 Probability that the chain ever visits statej if is starts at state i Transient States and Persistent States Probability that t is the first time that the chain visits statej if it starts at state i rgtipxtjandxs jforan1gslttiX0 Probability that the chain ever visits statej if is starts at state 139 Expected time to until a visit to statej if is starts at state i hij Z trigt if f0 1 and hij oo otherwise tgt0 Transient States and Persistent States Probability that t is the first time that the chain visits statej if it starts at state i roltIPXtjandX57 jforall1 sltth0 Probability that the chain ever visits statej if is starts at state 139 Expected time to until a visit to statej if is starts at state i hij Z trigt if f0 1 and hij oo otherwise tgt0 Definition If 15 lt 1 then state i is transient If 15 1 then state i is persistent Those persitent states 139 for which h 00 are said to be null peristent and those for which hi 7 00 are said to be non null persistent Periodicity and Ergodicity Definition The periodicity of state i is the maximum integer T for which there exists an initial distribution 70 and positive integer a such that for all t we have q gt 0 implies t 6 3 Ti i 0 If T gt 1 then state is periodic and aperiodic otherwise If every state is aperiodic then the Markov chain is aperiodic Periodicity and Ergodicity Definition The periodicity of state i is the maximum integer T for which there exists an initial distribution 70 and positive integer a such that for all t we have q gt 0 implies t 6 3 Ti i 0 If T gt 1 then state is periodic and aperiodic otherwise If every state is aperiodic then the Markov chain is aperiodic Definition An ergodic state is one that is aperiodic and non null persistent A Markov chain is ergodic if all states are ergodic Fundamental Theorem of Markov Chains Theorem Any irreducible finite and aperiodic Markov chain has the following properties 1 All states are ergodic 2 There is a unique stationary distribution 7139 With 7139 gt 0 3 167 and hi 1717 4 Let Ni7 t be the number of times the Markov chain visits state i in t steps Then Iim Nut ta 0 f 7rl Outline Random Walks on Graphs Random Walks on Graphs A connected non bipartite undirected graph G V7 E defines Markov Chain MG with states V and transition matrix PW 1du if u7v E E 0 otherwise where iVi n and iEi in Lemma MG is irreducible amp aperiodic because it39s connected amp bipartite Random Walks on Graphs A connected non bipartite undirected graph G V7 E defines Markov Chain MG with states V and transition matrix 1du if u7v E E Puv O otherWIse where iVi n and iEi in Lemma MG is irreducible amp aperiodic because it39s connected amp bipartite Lemma Stationary Distribution of Mg For all v E V 71quot dv2m Random Walks on Graphs A connected non bipartite undirected graph G V7 E defines Markov Chain MG with states V and transition matrix 1du if u7v E E Puv O otherWIse where iVi n and iEi in Lemma MG is irreducible amp aperiodic because it39s connected amp bipartite Lemma Stationary Distribution of Mg For all v E V 71quot dv2m Proof Let 39v denote the graph neighborhood of v du 1 dv g 39upuy 2 2m mi7rv u6Fv Hitting Time Definition The hitting time hm is the expected time taken by a random walk starting at node u until it arrives at v Hitting Time Definition The hitting time hm is the expected time taken by a random walk starting at node u until it arrives at v Theorem For any edge u7 v E E hvu lt 2m Hitting Time Definition The hitting time hm is the expected time taken by a random walk starting at node u until it arrives at v Theorem For any edge u7 v E E hvu lt 2m Proof gt By Fundamental Theorem huu 71171 2mdu Hitting Time Definition The hitting time hm is the expected time taken by a random walk starting at node u until it arrives at v Theorem For any edge u7 v E E hvu lt 2m Proof gt By Fundamental Theorem huu 7ru 1 2mdu gt But we can also write huu as l huu l l hWu du WEE Hitting Time Definition The hitting time hm is the expected time taken by a random walk starting at node u until it arrives at v Theorem For any edge u7 v E E hvu lt 2m Proof gt By Fundamental Theorem huu 7ru 1 2mdu gt But we can also write huu as 1 huu l l hWu du WEE gt Hence 2m 2 1 hwu gt hvu WEFu Cover Time 12 Definition CuG denote the expected time to visit every node after starting at u The cover time of G is CG maXuCuG Cover Time 12 Definition CuG denote the expected time to visit every node after starting at u The cover time of G is CG maXuCuG Theorem CG lt 4mn Where iVi n and iEi m Cover Time 12 Definition CuG denote the expected time to visit every node after starting at u The cover time of G is CG maXuCuG Theorem CG lt 4mn Where iVi n and iEi m Corollary Expected time of at 2 5AT algorithm is 0n2 Cover Time 22 Proof Cover Time 22 Proof gt Let T be a spanning tree of G and v0 6 V Cover Time 22 Proof gt Let T be a spanning tree of G and v0 6 V gt Let v07 v17 v2n4 v0 be the vertices visited in a traversal of T that traverses each edge exactly once Cover Time 22 Proof gt Let T be a spanning tree of G and v0 6 V gt Let v07 v17 v2n4 v0 be the vertices visited in a traversal of T that traverses each edge exactly once gt Then 2n73 CV0G S 2 hwy1 j0 Cover Time 22 Proof gt Let T be a spanning tree of G and v0 6 V gt Let v07 v17 v2n4 v0 be the vertices visited in a traversal of T that traverses each edge exactly once gt Then 2n73 CV0G S 2 hwy1 j0 gt We know thVH 2m because u7 v is an edge Cover Time 22 Proof gt Let T be a spanning tree of G and v0 6 V gt Let v07 v17 v2n4 v0 be the vertices visited in a traversal of T that traverses each edge exactly once gt Then 2n73 CV0G S 2 hwy1 j0 gt We know thVH 2m because u7 v is an edge gt Hence CV0G 2n7 12m for all v0 Readings For next time please make sure you39ve read gt Chapter 4 43 4 pages gt Chapter 5 51 52 55 12 pages

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.